20.图的遍历

目录

一. 深度优先遍历

二. 广度优先遍历

---

图的遍历算法和二叉树不同的是，图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，我们的解决思路是：设置辅助数组visited[n]，用来标记每个被访问过的顶点。初始状态visited[i]都为0，当顶点i被访问，改visited[i]为1，防止被多次访问。

图的遍历算法主要有深度优先搜索(Depth_First Search——DFS)和广度优先搜索（Breadth_Frist Search———BFS)两种。

一. 深度优先遍历

基本思想：“一条道走到黑”，直到走不了往回退。

• 在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w_1（所以深度优先搜索操作实现可以不唯一）；
• 再从w_1出发，访问与w_1邻接但还未被访问过的顶点w_2；
• 然后再从w_2出发，进行类似的访问，...
• 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。
• 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
• 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

观察上面的访问路径，连通图的深度优先遍历类似于树的先根遍历。

下面讨论邻接矩阵表示的无向图深度优先遍历的实现：对无向图，邻接矩阵的每一行代表了这个点与其他点的连接情况。我们从左向右看哪一个元素不为零，且这个结点没被访问过（visited=0），就优先访问哪个结点，这样给定起点就能唯一确定一条深度优先的遍历路径。

void DFS(AMGraph G, int v){  //图G为邻接矩阵类型，v是起点cout<<v; visited[v] = true;  //访问第v个顶点for(w = 0; w < G.vexnum; w++)  //依次检查邻接矩阵v所在的行if((G.arcs[v][w]!=0)&&(!visited[w]))  //路径存在，且w未被访问DFS(G, w);  //w是v的邻接点，如果w未访问，则递归调用DFS
}

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在的行，时间复杂度为O(n^2)。
用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。
结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。

二. 广度优先遍历

方法：从图的某一结点出发，首先依次访问该结点的所有邻接点Vi1, Vi2 ... Vin,再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点。重复此过程，直至所有顶点均被访问为止。

void BFS(Graph G, int v){  //按广度优先非递归遍历连通图G，起始点为vcout<<v; visited[v] = true;  //访问第v个顶点InitQueue(Q);  //辅助队列Q初始化，置空EnQueue(Q, v);  //v进队while(!QueueEmpty(Q)){  //队列非空DeQueue(Q, u);  //队头元素出队并置为ufor(w = FirstAdjVex(G,u); w>=0; w = NextAdjVex(G, u, w))if(!visited[w]){  //w为u的尚未访问的邻接顶点cout<<w; visited[w] = true;EnQueue(Q, w);  //w进队}//if}  //while
}  //BFS

上述代码实现了广度优先搜索（Breadth First Search，BFS）算法。BFS是一种用于图的遍历算法，通过队列的方式依次访问图中的每个节点。

该代码中的BFS函数接受两个参数：图G和起始节点v。首先输出当前节点v的值，然后将该节点标记为已访问。接着，初始化一个队列Q，并将节点v入队。进入循环，直到队列Q为空为止。在循环中，从队列Q中出队一个节点u，然后遍历节点u的邻接节点w。如果节点w未被访问过，则输出节点w的值，将节点w标记为已访问，并将节点w入队。

在BFS函数中，visited数组用于记录每个节点是否已经被访问过。InitQueue(Q)用于初始化队列Q，EnQueue(Q, v)用于将节点v入队，DeQueue(Q, u)用于从队列Q中出队一个节点u。

FirstAdjVex(G,u)函数用于获取节点u的第一个邻接节点。它接受两个参数：图G和节点u。该函数会返回节点u的第一个邻接节点的索引值（或编号）。如果节点u没有邻接节点，则返回一个特定的标识值（比如-1）。而NextAdjVex(G, u, w)函数用于获取节点u在节点w之后的下一个邻接节点。它接受三个参数：图G、节点u和当前节点w。该函数会返回节点u在节点w之后的下一个邻接节点的索引值（或编号）。如果节点u在节点w之后没有更多的邻接节点，则返回一个特定的标识值（比如-1）。这两个函数的作用是帮助遍历节点u的邻接节点。通过调用FirstAdjVex(G,u)函数，可以获取节点u的第一个邻接节点，然后通过调用NextAdjVex(G, u, w)函数，可以获取节点u在当前邻接节点w之后的下一个邻接节点，以此类推，直到遍历完所有的邻接节点。

通过调用BFS函数，可以遍历图中所有与起始节点v连通的节点，且按照广度优先的顺序进行访问。