请选择 进入手机版 | 继续访问电脑版
    查看: 600|回复: 0

    8.3 图的遍历

    [复制链接]

    1015

    主题

    1073

    帖子

    3705

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3705
    基情
    1841
    发表于 2016-9-9 23:28:22 | 显示全部楼层 |阅读模式
    图的遍历是指从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作,图的许多其它操作都是建立在遍历操作的基础之上。

    由于图结构本身的复杂性,所以图的遍历操作也较复杂,主要表现在以下四个方面:

    ① 在图结构中,没有一个“自然”的首结点,图中任意一个顶点都可作为第一个被访问的结点。
    ② 在非连通图中,从一个顶点出发,只能够访问它所在的连通分量上的所有顶点,因此,还需考虑如何选取下一个出发点以访问图中其余的连通分量。
    ③ 在图结构中,如果有回路存在,那么一个顶点被访问之后,有可能沿回路又回到该顶点。
    ④ 在图结构中,一个顶点可以和其它多个顶点相连,当这样的顶点访问过后,存在如何选取下一个要访问的顶点的问题。

    图的遍历通常有深度优先搜索和广度优先搜索两种方式,下面分别介绍。

    8.3.1 深度优先搜索


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

    假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点发v 出发,访问此顶点,然后依次从v 的未被访问的邻接点出发深度优先遍历图,直至图中所有和v 有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    以图8.17 的无向图G5 为例,进行图的深度优先搜索。假设从顶点v1 出发进行搜索,在访问了顶点v1 之后,选择邻接点v2。因为v2 未曾访问,则从v2 出发进行搜索。依次类推,接着从v4 、v8 、v5 出发进行搜索。在访问了v5 之后,由于v5 的邻接点都已被访问,则搜索回到v8。由于同样的理由,搜索继续回到v4,v2 直至v1,此时由于v1 的另一个邻接点未被访问,则搜索又从v1 到v3,再继续进行下去由此,得到的顶点访问序列为:

    8.3 图的遍历

    8.3 图的遍历

    显然,这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问,需附设访问标志数组visited[0:n-1], ,其初值为FALSE ,一旦某个顶点被访问,则其相应的分量置为TRUE。

    从图的某一点v 出发,递归地进行深度优先遍历的过程如算法8.4 所示。
    void DFS(Graph G,int v )
    { /*从第v 个顶点出发递归地深度优先遍历图G*/
    visited[v]=TRUE;VisitFunc(v); /*访问第v 个顶点*/
    for(w=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w))
    if (!visited[w]) DFS(G,w); /*对v 的尚未访问的邻接顶点w 递归调用DFS*/
    }
    算法8.4

    算法8.5 和算法8.6 给出了对以邻接表为存储结构的整个图G 进行深度优先遍历实现的C 语言描述。

    void DFSTraverseAL(ALGraph *G)
    {/*深度优先遍历以邻接表存储的图G*/
    int i;
    for (i=0;i<G->n;i++)
    visited=FALSE; /*标志向量初始化*/
    for (i=0;i<G->n;i++)
    if (!visited) DFSAL(G,i); /*vi 未访问过,从vi 开始DFS 搜索*/
    }/*DFSTraveseAL*/
    算法8.5

    void DFSAL(ALGraph *G,int i)
    {/*以Vi 为出发点对邻接表存储的图G 进行DFS 搜索*/
    EdgeNode *p;
    printf("visit vertex:V%c\n",G->adjlist.vertex);/*访问顶点Vi*/
    visited=TRUE; /*标记Vi 已访问*/
    p=G->adjlist.firstedge; /*取Vi 边表的头指针*/
    while(p) /*依次搜索Vi 的邻接点Vj,j=p->adjva*/
    {if (!visited[p->adjvex]) /*若Vj 尚未访问,则以Vj 为出发点向纵深搜索*/
    DFSAL(G,p->adjvex);
    p=p->next; /*找Vi 的下一个邻接点*/
    }
    }/*DFSAL*/
    算法8.6

    分析上述算法,在遍历时,对图中每个顶点至多调用一次DFS 函数,因为一旦某个顶点被标志成已被访问,就不再从它出发进行搜索。因此,遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,查找每个顶点的邻接点所需时间为O(n2) ,其中n 为图中顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e 为无向图中边的数或有向图中弧的数。由此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e) 。

    8.3.2 广度优先搜索


    广度优先搜索(Breadth_First Search) 遍历类似于树的按层次遍历的过程。假设从图中某顶点v 出发,在访问了v 之后依次访问v 的各个未曾访问过和邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程中以v 为起始点,由近至远,依次访问和v 有路径相通且路径长度为1,2,…的顶点。

    例如,对图8.17 所示无向图G5 进行广度优先搜索遍历,首先访问v1 和v1 的邻接点v2 和v3,然后依次访问v2 的邻接点v4 和v5 及v3 的邻接点v6 和v7,最后访问v4 的邻接点v8。由于这些顶点的邻接点均已被访问,并且图中所有顶点都被访问,由些完成了图的遍历。得到的顶点访问序列为:
    v1→v2 →v3 →v4→ v5→ v6→ v7 →v8

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

    从图的某一点v 出发,递归地进行广度优先遍历的过程如算法8.7 所示。
    void BFSTraverse(Graph G, Status(*Visit)(int v))
    {/*按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited*/
    for (v=0;v<G,vexnum;++v)
    visited[v]=FALSE
    InitQueue(Q); /*置空的国债队列Q*/
    if (!visited[v]) /*v 尚未访问*/
    {EnQucue(Q,v); /*v 入队列*/
    while (!QueueEmpty(Q))
    { DeQueue(Q,u); /*队头元素出队并置为u*/
    visited=TRUE; visit(u); /*访问u*/
    for(w=FistAdjVex(G,u); w; w=NextAdjVex(G,u,w))
    if (!visited[w]) EnQueue(Q,w); /*u 的尚未访问的邻接顶点w 入队列Q*/
    }
    }
    }/*BFSTraverse*/
    算法8.7

    算法8.8 和算法8.9 给出了对以邻接矩阵为存储结构的整个图G 进行深度优先遍历实现的C 语言描述。
    void BFSTraverseAL(MGraph *G)
    {/*广度优先遍历以邻接矩阵存储的图G*/
    int i;
    for (i=0;i<G->n;i++)
    visited=FALSE; /*标志向量初始化*/
    for (i=0;i<G->n;i++)
    if (!visited) BFSM(G,i); /* vi 未访问过,从vi 开始BFS 搜索*/
    }/*BFSTraverseAL*/
    算法8.8

    void BFSM(MGraph *G,int k)
    {/*以Vi 为出发点,对邻接矩阵存储的图G 进行BFS 搜索*/
    int i,j;
    CirQueue Q;
    InitQueue(&Q);
    printf("visit vertex:V%c\n",G->vexs[k]); /*访问原点Vk*/
    visited[k]=TRUE;
    EnQueue(&Q,k); /*原点Vk 入队列*/
    while (!QueueEmpty(&Q))
    {i=DeQueue(&Q); /*Vi 出队列*/
    for (j=0;j<G->n;j++) /*依次搜索Vi 的邻接点Vj*/
    if (G->edges[j]==1 && !visited[j]) /*若Vj 未访问*/
    {printf("visit vertex:V%c\n",G->vexs[j]); /*访问Vj */
    visited[j]=TRUE;
    EnQueue(&Q,j); /*访问过的Vj 入队列*/
    }
    }
    }/*BFSM*/
    算法8.9

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


    上一篇:8.2 图的存储表示—邻接多重表
    下一篇:8.4 图的连通性—无向图的连通性
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|小黑屋|网站地图|DZ商业模板|VR福利资源|嵌入式Linux论坛 ( 粤ICP备15085165号-2

    GMT+8, 2017-1-19 22:54 , Processed in 0.978466 second(s), 50 queries .

    Powered by 深嵌论坛 X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表