[图](6)图的遍历

图的遍历

和树得遍历类似,在此,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问依次,这一过程就叫做图得遍历(Traversing Graph)。图得遍历算法是求解图的 [连通性] [拓扑排序] 和求 [关键路径] 等算法的基础

然而,图的遍历要比树的遍历复杂的多,因为图的任一顶点都可能和其余的顶点相邻接,所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该顶点上,例如下图中:

image-20210126114029618

G2中由于存在回路,因此在访问了[v1,v2,v3,v4]之后,沿着边<v4,v1>又可以访问到 v1 为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点

为此,我们可以设一个辅助数组 Visited[0....n-1],它的初始值置为“假”或者零,一旦访问了顶点vi,便置visited[i] 为“真” 或者为被访问时的次序号

通常有两条遍历图的路径:深度优先搜索广度优先搜索,它们对无向图和有向图都适用

深度优先搜索

深度优先搜索(Depth_First Search)遍历类似于树的先根遍历,是树的先根遍历的推广

假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点 v 出发,访问此顶点,然后依次从 v 的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;

若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止

image-20210126172113986

如上所示[ 黑色虚线为递归序列,红色虚线为回溯序列 ],我们从V1出发,选择的是V1->V2这条边,然后以此类推访问到V5,这个时候V5只与V2,V8相邻接,但V2,V8,已经存在于已访问的路径中,则不能选取,这个时候我们需要回溯,到V1的时候,才有未曾访问的邻接点V3

由此,得到的顶点访问序列为:v1->v2->v4->v8->v5->v4->v6->v7

显然,这是一个递归的过程,为了在遍历过程中便于区分顶点是否被访问,需附设一个访问标志数组visited[0...n-1],其初值为“false”,一旦某个顶点被访问,则其相应的分量置为“true”,整个图的遍历如下列算法所示,其中 w >=0表示存在邻接点

//作用于邻接表
#define MAX 100//访问标志数组
BOOL visited[MAX];
Status(*VisitFunc)(int v);//函数变量

void DFS(Graph G, int v) {
    //从第v个顶点出发递归的深度优先遍历图G
    visited[v] = TRUE;
    VisitFunc(v);//访问第v个顶点

    for (w = FirstAdjvex(G, v); w >= 0; w = NextAdjVex(G, v, w))
        if (!visited[w]) DFS(G, w);//对尚未访问的顶点调用DFS;
    return;
}

void DFSTraverse(Graph G, Status(*Visit)(int v)) {
    //对图G作深度优先遍历
    
    VisitFunc = Visit;//使用全局变量VisitFunc,使DFS不必设函数指针参数
    for (int v = 0; v < G.vexnum; v++) 
        visited[v] = FALSE;//访问标志数组初始化
    
    for (int v = 0; v < G.vexnum; v++) if (!visited[v]) 
        DFS(G, v);//对未访问过的顶点调用DFS
    return;
}

分析上述算法,在遍历图时,对图中每个顶点之多调用一次DFS函数,因为一旦某个顶点被标志成已被访问,就不再从它出发进行搜索,因此,遍历图的过程实质上是对每个顶点查找其邻接点的过程

其耗费的时间则取决于所采用的存储结构,当用二维数组表示邻接矩阵作图的存储结构时,查找每个顶点的邻接点所需时间为O(n²),其中n为图中顶点数

而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e为无向图中边的数或有向图中弧的数,由此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)

我们来整理一下算法思路:

  1. 在访问图中某一起点顶点 v 后,由 v 出发,访问它的任一邻接顶点w1
  2. 再从w1出发,访问与 w1邻接但还未被访问过的顶点w2
  3. 然后再从w2出发,进行类似的访问,...
  4. 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止
  5. 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其他没有被访问的邻接顶点

    1. 如果有,则访问此顶点,之后再从顶点出发,进行与前述类似的访问
    2. 如果没有,就再退回前一步进行搜索,重复上述过程,直到连通图中所有顶点都被访问过为止

广度优先搜素

广度优先搜索(Broadth_First Search)遍历类似于树的按层次遍历的过程,假设从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的邻接点”先于“后被访问的顶点的邻接点”被访问

直至图中所有已被访问的顶点都被访问到,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述操作,直至图中所有顶点都被访问到为止

换句话说,广度优先搜索遍历图的过程是以v为起始点,由近至远,依次访问和v有路径相通且路径长度为1,2,...,n的顶点如下图所示:

请输入图片描述

首先访问v1和v1的邻接点v2和v3,然后访问v2的邻接点v4和v5以及v3的邻接点v6和v7,最后访问v4的邻接点v8,此时由于这些顶点均以被访问,并且图中所有顶点都被访问,由此完成了图的遍历,得到的顶点访问序列为:v1->v2->v3->v4->v5->v6->v7->v8

和深度优先搜索类似,在遍历的过程中也需要一个访问标志数组,并且,为了顺次访问路径长度为2、3、...的顶点,需附设队列以存储已被访问的路径长度为1,2,...的顶点,广度优先遍历的算法如下所示:

void BFSTraverse(Graph G, Status(*Visit)(int v)) {
    //按广度优先非递归的遍历图G,使用辅助队列Q和访问标志数组visited
    for (int v = 0; v < G.vexnum; v++) 
        visited[v] = FALSE;

    InitQueue(Q);//置空辅助数组
    for (int v = 0; v < G.vexnum; v++) {
        if (!visited[v]) {//v尚未访问
            visited[v] = TRUE;
            Visit(v);
            EnQueue(Q, v);//v入队列
            while (!QueueEmpty(Q)) {
                DeQueue(Q, u);//队头元素出队并置为u
                for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, v)) {
                    if (!visited[w]) {//w为u的尚未访问的邻接顶点
                        visited[w] = TRUE;
                        Visit(w);
                        EnQueue(Q, W);
                    }
                }
            }
        }
    }
    return;
}

分析上述算法,每个顶点至多进依次队列,遍历图的过程实质上是通过边或弧找邻接点的过程,因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同,两者不同指出仅仅在于对顶点访问顺序的不同

时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无关

本文链接:

https://nullcode.fun/129.html
1 + 8 =
快来做第一个评论的人吧~