柳江企业网站建设公司,免费的php网站模板,蓬莱市住房和规划建设管理局网站,南宁公司注册网上核名文章目录一、邻接矩阵存储图的深度优先遍历过程分析二、结果分析三、C语言编程实现图的深度优先遍历四、图的遍历及其应用一、邻接矩阵存储图的深度优先遍历过程分析
对图1这样的无向图#xff0c;要写成邻接矩阵#xff0c;则就是下面的式子#xff1a; 一般要计算这样的问…
文章目录一、邻接矩阵存储图的深度优先遍历过程分析二、结果分析三、C语言编程实现图的深度优先遍历四、图的遍历及其应用一、邻接矩阵存储图的深度优先遍历过程分析
对图1这样的无向图要写成邻接矩阵则就是下面的式子 一般要计算这样的问题画成表格来处理是相当方便的事情实际中计算机处理问题也根本不知道所谓矩阵是什么所以画成表格很容易帮助我们完成后面的编程任务。在我们前面介绍的内容中有不少是借助着表格完成计算任务的如Huffman树。 为了记录那些顶点是已经走过的还要设计一个表来标记已经走过的顶点在开始我们假设未走过的是0走过的是1于是有 深度优先遍历过程如下
1从第1行开始寻找和V1相连的第1个顶点首先在Visited表中标记V1被访问到就是 在该行我们找到的第一个连接顶点是V2找到V2顶点后记录V1-V2意味着我们已经抵达V2注意修改邻接矩阵表 2然后则转向V2顶点所在的行意味着我们已经抵达V2再次在Visited表中标记V2顶点已经被访问就是 然后寻找连接V2的、并且是未被访问过的第一个顶点就是V4记录V2-V4 3然后则转向V4顶点所在的行意味着我们已经抵达V4再次在Visited表中标记V4顶点已经被访问就是 然后则转向V4顶点所在的行寻找连接V4的、并且是未被访问过的第一个顶点就是V8记录V4-V8 4然后则转向V8顶点所在的行意味着我们已经抵达V8再次在Visited表中标记V8顶点已经被访问就是 然后则转向V8顶点所在的行寻找连接V8的、并且是未被访问过的第一个顶点就是V5记录V8-V5 5然后则转向V5顶点所在的行意味着我们已经抵达V5再次在Visited表中标记V5顶点已经被访问就是 寻找连接V5的、并且是未被访问过的第一个顶点此处未找到注意V2、V8顶点已经在Visited表中标记已访问过。 5这个地方一定注意V5上找不到未访问过的顶点说明此路到此就算走死了。
此时看Visited表其中还有顶点没有抵达过于是要按原路返回所谓原路就是从表12、表10、表9走过的路线返回、然后逐个查找这些顶点上有无未抵达过的顶点。过程如下再次从V5返回到V8查找V8上有无未抵达过的顶点结果是无 再次从V8返回到V4查找V4上有无未抵达过的顶点结果是无 再次从V4返回到V2查找V2上有无未抵达过的顶点结果是无 再次从V2返回到V1查找V1上有无未抵达的顶点结果是V3于是重复第(1)步首先标记V3访问到 标记V1-V3标记Visited表V3被访问 到V3就是这样的情况 6到达V3后寻找第一个未被访问过的顶点V6首先标记Visited表说明已经抵达V6就是 再从V6开始找下一个顶点就是V7 7在Visited表中标注V7已经访问到就是 至此图1的深度优先遍历完成。
二、结果分析
从上面的过程可以看出仅仅就顶点访问到的次序而言图1的深度优先遍历结果是
V1-V2-V4-V8-V5-V3-6-V7但实际执行过程中我们可以发现所谓图的遍历、其结果应该是一个树 在C语言中显示这个结果并不容易所以大多教材中并不会给出这样的结果。
三、C语言编程实现图的深度优先遍历
图1只有8个顶点可在实际中一个图的顶点个数是不确定的在编程中要保存顶点数据、邻接矩阵首先就要考虑动态数组其次为了方便邻接矩阵的输入和修改最好是把数据保存在文本文件中。在我们的教材中、程序使用了键盘输入的方式而在实际操作中、在图的顶点个数比较多的情况下手工无差错输入很多数据、几乎是无法办到的事情为此我们在文件p176G719.txt中保存了图1的邻接矩阵数据。这个文件的名称含义是教材176页图7.19的顶点名称和邻接矩阵数据。有了这样的数据文件在记事本程序中可以很方便的修改和补充数据。这个文件的内容如下 8 V1 V2 V3 V4 V5 V6 V7 V8 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 这个文件第一行是8说明这个图有8个顶点随后在第2行到第9行则是图的顶点名称第10行到末尾则是该图的邻接矩阵。
根据不同的图在记事本程序中完成这样的数据是非常简单的事情哪怕错了再修改也是很容易做到。
1 设计图的存储结构以及数据文件读取
图的存储、无论哪种方法都是由两部分组成的一个是顶点名称集合一个是顶点关系集合在邻接矩阵方式中顶点名称是一个字符串数组而顶点关系则是一个矩阵、这个矩阵在C语言中是一个二维数组。于是图的结构可以是
struct Graph
{int A[100][100]; //邻接矩阵char V[100][20]; //顶点名称矩阵100行每个名称字符串不超过20字节int num; //顶点个数int Visited[100]; //访问记录表
};但这样的定义很死板它假设程序最大是100个顶点实际我们的教材中就是这么定义的。但幸好我们前面已经知道该怎么处理二维数组于是这里我们可以动态申请内存以保证在很多顶点的情况也能使用对二维数组则上述定义变为
struct Graph
{int **pA; //邻接矩阵指针char **pV; //顶点名称指针int num; //顶点个数int *Visited;//访问记录表指针
};对这样数组的构造参见第5部分数组好在我们前面有过介绍。
回忆一下如有数组
int A[3][3]{{1,2,3},{4,5,6},{7,8,9}};则A[0]、A[1]、A[2]则代表每一行的地址一般称为行首地址比如这三行行首地址分别是[100]、[200]、[300]这三个地址数据分别存储在地址[2000]、[2001]、[2002]的存储空间里则地址[2000]就是这个数组A的含义就是所谓行首地址数组的首地址。 反过来如:
int *p[3];
p[0]A[0];p[1]A[1];p[2]A[2];上面的式子里如p[0]地址为[3000]、[3001]、[3002]其中的内容保存的是100、200、300这样就相当于保存了A数组的行首地址所以p就是个二维数组行首指针数组只不过它仅仅是三行的二维数组。如把p[0]的地址给另外一个指针变量pA则pA就是
int **pA;假如这个变量的地址在[5000]给这个变量赋值
pAp[0];于是地址[5000]中将存储3000这里pA和A的含义是一致的。实际数组A本身就是地址[5000]如有以下语句
XA[1][2];就是从A的地址[5000] 、读到内容3000、再从3001读到200、再从200后取第1个数过程如下图3所示 针对n个顶点则初始化一个图的函数就是
#define VLENGTH 20 //定义每个顶点名称不超过20字节
struct Graph *GraphInit(int n)
{int i;struct Graph *g;if(n0) return NULL;g(struct Graph *)malloc(sizeof(struct Graph));g-numn;g-pA(int **)malloc(sizeof(int )*n);g-pV(char **)malloc(sizeof(char)*n); for(i0;in;i){g-pA[i](int *)malloc(sizeof(int)*n);g-pV[i](char *)malloc(sizeof(char)*VLENGTH);}g-Visited(int *)malloc(sizeof(int )*n); for(i0;in;i)g-Visited[i]0; return g;
}
注意第9行是为行首地址数组申请内存
注意第13行是为每行数据申请存储空间
注意第14行前面定义每个顶点的名称是VLENGTH长度这里是20字节。
由于C语言的指针可以用下标法读写内容所以完全可以把pA、pV当做普通的二维数组来处理此处不再叙述。
2 从文件中读数据到邻接矩阵和顶点名称矩阵
这个过程在链表的处理中已经介绍过了只不过数据格式有差异而已。针对我们前面介绍的数据格式读数据文件并构造图的函数如下
struct Graph * GraphCreat(char FileName[20])
{int i,j,n;FILE *fp,*fopen();struct Graph *G;fpfopen(FileName,r);if(fpNULL) return NULL;fscanf(fp,%d,n);GGraphInit(n);for(i0;in;i)fscanf(fp,%s,G-pV[i]);for(i0;in;i)for(j0;jn;j)fscanf(fp,%d,G-pA[i][j]);fclose(fp);return G;
}
第8行首先读文件中顶点个数然后根据顶点个数、使用GraphInit()申请内存并构造这个图的存储空间然后在第10行读n个顶点名称、在第12行按二维数组的组织读邻接矩阵。最后返回G就是包含有顶点名称、邻接矩阵的图的存储空间。
有了这两个函数后就可以编写main()来测试它们就是
main()
{int i,j;struct Graph *G;GGraphCreat(p176G719.txt);//打印顶点名称for(i0;iG-num;i)printf(%s ,G-pV[i]);printf(\n);//打印邻接矩阵for(i0;iG-num;i) {for(j0;jG-num;j)printf(%d ,G-pA[i][j]);printf(\n);}
}
这个程序第5行你可以修改成用scanf()来读到一个文件名称字符串然后就可以使用任何格式符合要求的数据文件了。 G0.C中还包含有GraphFirstAdj()、GraphNextAdj()、GraphDestory()三个函数这些函数的意义你能看懂么
2 深度优先遍历的编程实现
从前面算法分析过程可知对一个图的深度优先遍历实际就是从第n个顶点开始、标记该顶点已被访问然后查找该顶点上第一个和它相连、并且未被访问到的顶点、比如是第i个顶点再去第i个顶点如此繁琐的说这些实际就是
void DFS(struct Graph *G,int n)
{int i;if(GNULL) return;if(n0||nG-num) return;G-Visited[n]1;printf(%s ,G-pV[n]); for(i0;iG-num;i)if(G-pA[n][i]!0G-Visited[i]!1) DFS(G,i);
}
第6行是标记该顶点被访问
第9行就是查找第n个顶点上、未被访问到的顶点如找到该顶点、且顶点编号是i则再次DSF(G,i)
有了这个函数后构造main()开始从第0个顶点遍历图1就是
main()
{int i,j;struct Graph *G;GGraphCreat(p176G719.txt);for(i0;iG-num;i)printf(%s ,G-pV[i]);printf(\n);for(i0;iG-num;i) {for(j0;jG-num;j)printf(%d ,G-pA[i][j]);printf(\n);}DFS(G,0);printf(\n);
}
进一步测试该函数按图1的数据仔细分析下它的执行过程如有图的连接分量不为1则会在第一个连接分量遍历完成后终止。如下图4在G1.C中是无法全部遍历完成的。这个图的文件在G4.TXT修改表23中第5行从G4.TXT中读数据则会发现这个程序仅仅遍历了A、B、C、D而没有到达过E、F、G这三个顶点。 为确保多个分量的图都能顺利遍历完成则该函数退出后还需要判断是有顶点是否确保全部遍历完成、并确保每次遍历开始的时候、其访问数组Visited[]中全部是0就是
void DFSTraverse(struct Graph *G)
{int i;if(GNULL) return;for(i0;iG-num;i)G-Visited[i]0;for(i0;iG-num;i)if(G-Visited[i]0) DFS(G,i);
}
表24中函数很容易修改成计算图的连接分量的函数这个工作就由同学们自己完成。如果你遇到困难无法完成参见G3.C 略加修改main()函数补充
DFSTraverse(G);即可完成图4的深度优先遍历。到此C语言的深度优先遍历到此结束。
四、图的遍历及其应用
1 图的关节点
图的关节点、在图上或许仅仅是个理论或者方法但对GIS而言却绝对是个重要意义的理论、尽管目前还没见到这类应用。 求解图的关节点、是典型的深度优先遍历应用首先我们从教材中找到G5的图其邻接矩阵如下 从A点开始、进入A点后由邻接矩阵右端向左遍历其结果就是ALMJBHKGIDECF
仔细根据上述结果、可以得到图5这样的深度遍历生成树。
注意图5每个结点上标注的数字是在深度优先遍历上抵达的次序。
对这个邻接矩阵我们从右向左做了深度优先遍历这代表着一个方向然后我们要从左到右、在遍历的时候、逐个结点寻找与当前结点相连的最小次序结点这里一直没想好个比较恰当的措辞来描述这个概念而这个结点、则构成了所谓的回边路径如图5中虚线所指的线路如J-L、B-A等线路。这种线路很关键它的物理意义是你可以通过B直接抵达A、或者C直接抵达A、G直接抵达B等等这些回边路径则立刻喻示着你炸毁K点、对I点则没什么影响。
从右向左深度优先遍历这里的现实意义就是说从其他各个顶点回到A的情况。
相连最小次序结点序号通常用Low[ ]数组来表示比如J结点这个值就是2它代表着J可以抵达第2个遍历到的结点L这就是所谓的回边路径。同理对于C这个值是1它代表着在C点可以直接到A。
如果当前结点下标是v而在Visited[v]代表这个结点深度遍历中的次序w代表v顶点在生成树上的孩子结点下标k代表v的祖先结点下标则
Low[v]min{Visited[v],Low[w],Visited[k]}当然这个式子很简洁要真正计算出来Low[ ]的值、显然要在程序上说了算。而要在编程中体现这些还要首先是能手工计算出这个值来。
2 关节点的计算
首先我们设计表格如下 (1) 顶点A步骤1
对于A它就是来自步骤1就是A于是Low为1。
(2) 顶点L步骤2
现在根据遍历的次序我们抵达L这个顶点注意L的邻接矩阵 从表27可知深度优先遍历经过的顶点里有A、J、M其中只有A是深度优先遍历访问过的顶点、所以最小次序号是1也就是A是L能直接抵达的回边路径上的顶点所以表26就是以下结果 (3) 顶点M步骤3
现在我们根据表28抵达顶点M这个顶点的邻接矩阵表如下
这个地方可以看到M可以和B、J、L相连但B、J尚未被访问过而M又从L而来所以此时M的回边就是L的回边于是有 (4) 顶点J步骤4
根据遍历的次序我们进入顶点J此时邻接矩阵如下 对于顶点J这里可知与L、M相连从表30知道L是步骤2到达、M是步骤3到达取步骤次序最小、即为2它意味着在顶点J上可以抵达深度遍历次序为2的顶点、就是L于是有 从这个表第4步我们回头看图5就相当于J与L之间的连接虚线。在L、M之间找最小连接次序的意义是把M炸掉、J依然能回到L。
(5) 顶点B步骤5
依然要看邻接矩阵B顶点是 在这里我们发现B与A、C、D、G、H、M相连其中A、M是深度优先遍历已经遍历过得顶点找最小次序的、就是A也就是第一步就抵达的顶点所以有 (6) 顶点H步骤6
再次看邻接矩阵表H顶点就是 可以发现H与B、G、K连接其中B是深度优先遍历访问过的顶点注意到B的是在第5步访问的所以有 对于顶点H该顶点是由邻接矩阵这种硬性连接造成的回边路径只能是5、就是说它只能通过B回到A这就非常麻烦立刻喻示着B是一个关节点。
(7) 顶点K步骤7
同样要仔细看邻接矩阵K就是 我们看到K与G、H相连但这两个顶点目前都没有被深度优先遍历访问到此时的情况、立刻说明从邻接矩阵中无法得到Low同表28的顶点M情况一致就是说从H顶点来而H顶点又来自B所以K的Low也是5。 这现实意义也很明确如果把B炸毁了、K就是受害者当然H也是。
(8) 顶点G步骤8
还是看G的邻接矩阵 在这个表中可知G连接有B、H、I、K其中B、H、K是深度优先遍历都访问过的这3个顶点里以访问B的步骤最小就是5于是 对这个结果还能说什么意味着B炸掉后又多了个受害者。
(9) 顶点I步骤9 同样要看邻接矩阵对于I就是 这个顶点更不幸它仅仅与G相连对于这样的顶点我们知道访问到G的步骤8就是这个顶点的Low就是 回忆我们对B-H路径的分析我们知道此时的G同样是I的关节点I回到A必须经过G。如果炸掉G、B这样的顶点I城市就算没救了。
(10) 顶点D步骤10
还是先看邻接矩阵对于D就是 可知顶点D与B、E相连对于D此时最先抵达的顶点是B在步骤5所以有 这个结果说明B依然是控制着D的生命线。
(11) 顶点E步骤11
还是看E的邻接矩阵就是 可以知道E与D直接相连于是回边上另一个顶点D、也就是在步骤D于是 总结下设当前顶点为v下一个顶点是w其步骤都在Visited[ ]中保存则
Low[w] Visited[v]则v必然是关节点比如此时v是顶点D而w代表E或者v是顶点B而w代表H、K等顶点。
从图5中我们不难发现炸掉D确实能孤立E。
(12) 顶点C步骤12
还是看邻接矩阵在顶点C有 从这个地方可知C与A、B相连这两个顶点都在第1、5步骤访问过显然回到A最直接于是此时Low为1。 由于有这个回边线路所以看图5我们就知道炸掉B对这个结点不起任何作用。
最后一个顶点F看邻接矩阵表可知与A相连所以表46中自行写入1即可不再重复计算。
到此G5图中各个顶点回到A顶点路径上、各个回边和关节点计算完毕我们回顾这个过程不难发现A、B、G、D是这个图的关节点。
在关节点上分割图立刻可以将一个图分割成若干个不相连的子图这就是图论中对关节点的要求。
2 关节点计算的编程实现
根据上面计算的过程我们可以总结如下
关节点的计算首先要获得Low[ ]如设图为G则计算过程分两种情况
1 深度遍历过程中如到当前顶点v如该顶点邻接顶点没有被深度优先遍历访问过如前面的M、K这两个顶点则此时该顶点最早回边顶点值(Low)等同前一节点值也就是G-Low[v]G-Low[w]
2 在遍历过程中如到当前顶点v该结点邻接矩阵中可以找到已经遍历过的邻接顶点则G-Low[v] min(G-Visited[w]);如B、J等。
而关节点的判断条件则是
遍历过程中如当前顶点为v邻接顶点为w如满足
G-Low[w]G-Visited[v]如v是顶点B、w是顶点H则v是关节点。
为了满足上述计算要求我们首先修改Graph的定义补充内容如下
struct Graph
{int **pA;char **pV;int num;int *Visited;int Count;int *Low;
};
新补充的变量Count是一个计数器用来计算深度优先遍历的步骤有这个步骤我们才能在图5上标注每个结点在深度优先遍历中是在哪一步到达的。而对于Low[ ]我们知道这里是最小回边的次序号定义为指针是准备按顶点个数来动态申请内存由此我们图的初始化函数就是表27。
同表19的程序实际没什么差别仅仅是初始化了Low[ ]这个数组。 深度优先遍历的过程同前面的过程实际完全一致但此时Visited[ ]中将不是简单的把已经访问过得顶点如v设置成1而是要标记步骤标记步骤就是让深度优先遍历的过程中每次都要进行
G-Count;然后把这个结果赋值给
G-Visited[v]Count;其中v是遍历到当前结点的下标。
所以能标记步骤的深度优先遍历就是表28运行下这个程序你会看到遍历结果逐个将Visited[ ]中的值打印出来就有了深度优先遍历到每个顶点的步骤。
struct Graph *GraphInit(int n)
{int i;struct Graph *g;if(n0) return NULL;g(struct Graph *)malloc(sizeof(struct Graph));g-numn;g-pA(int **)malloc(sizeof(int )*n);g-pV(char **)malloc(sizeof(char)*n); for(i0;in;i){g-pA[i](int *)malloc(sizeof(int)*n);g-pV[i](char *)malloc(sizeof(char)*VLENGTH);}g-Visited(int *)malloc(sizeof(int )*n); g-Low(int *)malloc(sizeof(int )*n); for(i0;in;i){g-Visited[i]0; g-Low[i]0;}g-Count0;return g;
}
表48补充了Low[ ]空间申请、Low[ ]构造初始值的语句基本是表19程序的补充。
void DFS(struct Graph *G,int v)
{int w;if(GNULL) return;if(v0||vG-num) return;G-Count; G-Visited[v]G-Count; printf(%3s,G-pV[v]);for(wG-num-1;w0;w--)if(G-pA[v][w]!0) {if(G-Visited[w]0)DFS(G,w);}
}
同原来的DFS()相比就是加了个计数器并能记录步骤补充如G4.c的main()读进文件P719G5.txt的数据来计算这样你就获得了深度优先遍历的结果和步骤。注意表49第9行我们是从邻接矩阵右边向左开始遍历。
有了遍历步骤计数下面就准备计算Low[ ]回顾第18页对Low[ ]计算的总结先设定min是我们要计算的值并假设在开始、这个值就是当前顶点v被遍历到的步骤也就是有这样的假设
minG-Visited[v]Count;注意(1)的结果如果进入第v个顶点后、如果该顶点邻接顶点没有一个被深度优先遍历访问过也就是该情况在表49第13行所在位置于是修改这里为
if(G-Visited[w]0)
{DFS(G,w);if(G-Low[w]min) minG-Low[w];
}此种情况下如M、K这两个顶点该情况下就是说只能原路返回、其Low[v]值是前一个的Low[w]的值。注意这里w是一个循环变量逐个寻找没找到与v相连的、被深度优先遍历访问过的。
另外一种情况则是说假如当前结点v的邻接顶点里、其中有被深度优先遍历访问过的这种情况下要把访问过的顶点次序依次排列、找到最小的值。这样就是在上述代码下添加一下内容
if(G-Visited[w]0){DFS(G,w);if(G-Low[w]min) minG-Low[w];}
else if(G-Visited[w]min) minG-Visited[w];同样w作为循环变量是逐个计算着其中最小的值。如此计算的min、其值就是Low[v]的值现在深度优先遍历的代码就是
void DFS(struct Graph *G,int v)
{int w,min;if(GNULL) return;if(v0||vG-num) return;G-Visited[v]minG-Count; //设置当前顶点步骤假设min就是当前步骤printf(%3s,G-pV[v]);for(wG-num-1;w0;w--)if(G-pA[v][w]!0) {if(G-Visited[w]0) //没有顶点被访问过{DFS(G,w);if(G-Low[w]min) minG-Low[w];}else if(G-Visited[w]min) minG-Visited[w]; //有被访问的顶点}G-Low[v]min;
}
在循环体外第18行则将min赋值给当前顶点Low[ ]到此Low[ ]计算完毕。 如果要显示关节点根据我们前面分析的结果则在第14行下加入
if(G-Low[w]G-Visited[v]) printf(%3s\n,G-pV[v]); 为了让显示明了表50中第7行关于遍历的结果、就不要显示了最好注释掉。到这里有关关节点的计算全部完成。
关节点的含义是从这里分割一个图将会得到互相不连的若干子图此种情况下又涉及到图的另一个问题有向图的强连通分量的计算简述就是顶点之间可以两两抵达。以下图有3个连通分量{1,2,3,4},{5},{6}过去求连通分量要两次DFS后来产生了Tarjan算法从而可以快速获得连通分量。 实际说起来关节点的计算方法、是来自Tarjan算法是在先能计算连通分量后、才发展到去计算关节点的有了上面关节点的计算你能计算图6的连通分量么这个图的邻接矩阵数据见G10.TXT。
