数据结构——图的两种遍历方法

2023-11-16

遍历定义：从已给的图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历。

遍历实质：找每个顶点的邻接点的过程。

图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

解决思路：可设置一个辅助数组 visited [n ]，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即改 visited [i]为1，防止它被多次访问。

图常用的遍历：深度优先搜索
广度优先搜索

图的深度优先遍历（Depth_First Search:DFS）：

遍历步骤：从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

详细归纳：

在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；
再从 w1出发，访问与 w1邻接但还未被访问过的顶点 w2；
然后再从 w2 出发，进行类似的访问， …
如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。
如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶
点都被访问过为止。

如图所示，例1：

具体实现过程，例2：

深度优先遍历编程算法：（邻接矩阵）

void DFS( Mgraph g,int v,int visited[])
{
    /* 邻接矩阵存储，从顶点v出发，对图g进行深度优先搜索*/
    int j;
    printf("%d ",g.vexs[v]);
    visited[v]=1; /*标识v被访问过*/
    for(j=0;j<g.vexnum;j++); /* */
    {
        if( g.arcs[v][j]==1&&visited[j]==0)/*j为v的邻接点,未被访问过*/
        DFS(g,j,visited); /*从j出发递归调用DFS*/
    }/*for*/
}/*DFS*/

void DFSTraverse(Mgraph g)
{ 
    /*邻接矩阵 深度优先搜索*/
    int v;
    int visited[MAX_VERTEX_NUM];
    for(v=0;v<g.vexnum;v++)
    visited[v]=0; /*初始化visited数组*/
    for(v=0;v<g.vexnum;v++)
        if(visited[v]==0) 
            DFS(g,v,visited);
    /*从未被访问过的v出发， DFS搜索*/
}

深度优先遍历编程算法：（邻接表）

void DFS(ALGraph g,int v,int visited[])
{
    /*从顶点v出发，对图g进行深度优先搜索*/
    ArcNode *p;
    int w;
    printf("%d ",g.adjlist[v].data);
    visited[v]=1; /*标识v被访问过*/
    p=g.adjlist[v].firstarc; /*p指向第v个单链表的头指针*/
    while(p)
    {
        w=p->adjvex; /*w为v的邻接点*/
        if(visited[w]==0) /*若w未被访问*/
            DFS(g,w,visited); /*从w出发递归调用DFS*/
        p=p->nextarc; /*找v的下一个邻接点*/
    }/*while*/
}/*DFS*/

void DFSTraverse(ALGraph g)
{ 
    /*邻接表 深度优先搜索*/
    int v;
    int visited[MAX_VERTEX_NUM];
    for(v=0;v<g.vexnum;v++)
        visited[v]=0; /*初始化visited数组*/
    for(v=0;v<g.vexnum;v++)
        if(visited[v]==0) 
            DFS(g,v,visited);
    /*从未被访问过的v出发， DFS搜索*/
}

图的广度优先遍历（Breadth_First Search:BFS）：

基本思想：— 模仿树的层次遍历过程。

遍历步骤：在访问了起始点v之后，依次访问 v的邻接点；然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；直到所有顶点都被访问过为止

具体实现过程，例2：

广度优先遍历编程算法：（邻接表）

BFSTraverse(ALGraph g)
{ 
    // 邻接表存储 BFS 算法
    QElemType v,w,u;
    SqQueue Q; ArcNode *p;
    for(v=0;v<g.vexnum;v++) 
        visited[v]=0； //初始化visited数组
    InitQueue(&Q); //队列Q初始化
    for(v=0;v<g.vexnum ;v++) //从v出发广度优先搜索
    { 
        if (!visited[v])
        {
            visited[v]=1;
            printf("%d ",v); //输出v
            EnQueue(&Q,v); //v入队
            while(!EmptyQueue(Q)) //队列Q不空
            {
                DeQueue(&Q,&u); // u出队
                p=g.adjlist[u].firstarc ;
                while(p) //依次访问u的邻接点
                { 
                    w=p->adjvex;
                    if(!visited[w])
                    { 
                        visited[w]=1;
                        printf("%d ",w);
                        EnQueue(&Q,w); //w 入队
                    }
                    p=p->nextarc ; //p指向下一个邻接点
                }//end of while
            }//end of while
        }//end of if
    }//end of for
}//end of BFSTravers

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

c语言