图的矩阵深度和广度遍历算法

[八阵图的诗意]八阵图的诗意《八阵图》作者：杜甫原文：功盖三分国，名高八阵图。江流石不转，遗恨失吞吴。注释： 1、八阵图：由八种阵势组成的图形，用来操练军队或作战。 2、三分国：指三国时魏、...+阅读

图的遍历是指从图中任一给定顶点出发，依次访问图中的其余顶点。如果给定的图是连通图，则从图中的任意一点出发，按照一个指定的顺序就可以访问到图中的所有顶点，且每个顶点只访问一次。这个过程称为图的遍历。图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的G1，在访问了V1,V2和V3之后，有可能沿着边（V3,V1）访问到V1。为了避免一顶点被多次访问，可以设立一个集合Visited，用来记录已被访问过的顶点。它的初值为空集。一旦V1被访问过，即把V1加到集合Visited中。图的遍厉通常有两种：图的深度优先搜索和图的广度优先搜索。 1）图的深度优先搜索从图G=(V,E)的一个顶点V0出发，在访问了任意一个与V0相邻且未被访问过的顶点W1之后，再从W1出发，访问和W1相邻且未被访问过的顶点W2，然后再从W2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点V1出发对图3.3.5进行深度优先搜索，遍历的顺序为 V1,V2,V5,V10,V6,V7,V3,V12,V1 1,V8,V4,V9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历顺序有影响）例25.(p194.c)图的深度优先搜索。从图G的顶点V0 发进行深度优先搜索，打印出各个顶点的遍历顺序。解：图的深度优先搜索法为：

（1）首先访问V0并把V0加到集合visited中；

（2）找到与V0相邻的顶点W，若W未进入 visited中，则以深度优先方法从W开始搜索。

（3）重复过程

（2）直到所有于V0相邻的顶点都被访问过为止。下面是对用邻接表表示的图G进行深度优先搜索的程序 int rear=0; /*Visit和rear都为全局变量*/ int visit[500]; depth_first_search(g,v0) /*从V0开始对图G进行深度优先搜索*/ graphptr g[ ]； /*指针数组，为邻接表表头顶点指针 g[vi]...g[vn]*/ int v0； /*这里V0和W都是顶点标号，如V0=0或1*/ { /*g[v0]是顶点V0的表头指针*/ int w; graphptr p； /*链表的结点指针*/ visit [++rear]=v0; printf(＂%d\n＂,v0); p=g[v0]；/*指定一个顶点，通过邻接表表头指针，访问v0的邻接顶点*/ while (p!=NULL) { w=p->vertex ；/*这里W是与V0相邻的一个顶点*/ if (!visited(w)）/*当V0的相邻结点，W未被访问时，从W开始遍厉*/ depth_first_search(g,w); p=p->next；/*接着访问另一个相邻顶点*/ } } int visited(w) /*检查顶点w是否进入visited(w)*/ int w ; { int i; for (i=1;inext；/*再考虑该结点的下一个相邻顶点*/ } } } visited (q,tail,v)/*判断顶点是否被访问过，访问过时，返回1，否则返回0*/ int q[ ],tail,v；/*进入队列的顶点，在front之前的顶点已被访问过打印输出，在front和tail之间的顶点是即将要访问顶点*/ { int i; for(i=1;i