图的遍历

数据结构与算法

四、图的遍历

图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

图的遍历要比树的遍历复杂的多，因为它的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1。

4.1 深度优先遍历

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS。

遍历过程

    首先从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F，可以定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看上图的右图。此时发现有三条分支，分别通向顶点C、I、G，右手通行原则，使得我们走到了C顶点。就这样一直顺着右手通道走，一直走到F顶点。当依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时退回到顶点F，走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H，当面对通向H的两条通道D和E时，会发现都已经走过了。

    此时是否已经遍历了所有顶点呢？没有。可能还有很多分支的顶点没有走到，所以按原路返回。在顶点H处，再无通道没走过，返回到G，也无未走过通道，返回到F，没有通道，返回到E，有一条通道通往H的通道，验证后也是走过的，再返回到顶点D，此时还有三条道未走过，一条条来，H走过了，G走过了，I，哦，这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A，确认已经完成遍历任务，找到了所有的9个顶点。

深度优先遍历其实就是一个递归的过程，就像是一棵树的前序遍历。从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

如果用邻接矩阵的方式，代码如下：

/* Boolean是布尔类型，其值是TRUE或FALSE */
typedef int Boolean;             
/* 访问标志的数组 */
Boolean visited[MAX];            
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i)
{
    int j;
    visited[i] = TRUE;
    /* 打印顶点，也可以其他操作 */
    printf("%c ", G.vexs[i]);    
    for (j = 0; j < G.numVertexes; j++)
        if (G.arc[i][j] == 1 && !visited[j])
            /* 对为访问的邻接顶点递归调用 */
            DFS(G, j);           
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
    int i;
    for (i = 0; i < G.numVertexes; i++)
        /* 初始所有顶点状态都是未访问过状态 */
        visited[i] = FALSE;      
    for (i = 0; i < G.numVertexes; i++)
        /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */
        if (!visited[i])         
            DFS(G, i);
}

果图结构是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下:

/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
    EdgeNode *p;
    visited[i] = TRUE;
    /* 打印顶点，也可以其他操作 */
    printf("%c ", GL->adjList[i].data);    
    p = GL->adjList[i].firstedge;
    while (p)
    {
        if (!visited[p->adjvex])
            /* 对为访问的邻接顶点递归调用 */
            DFS(GL, p->adjvex);            
        p = p->next;
    }
}
/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
    int i;
    for (i = 0; i < GL->numVertexes; i++)
        /* 初始所有顶点状态都是未访问过状态 */
        visited[i] = FALSE;                
    for (i = 0; i < GL->numVertexes; i++)
        /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */
        if (!visited[i])                   
            DFS(GL, i);
}

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要$O(n^2)$的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

4.2 广度优先遍历

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。如下图，把深度优先遍历图形案例变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层，此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。

邻接矩阵结构的广度优先遍历算法：

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
    int i, j;
    Queue Q;
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = FALSE;
    /* 初始化一辅助用的队列 */
    InitQueue(&Q);                                   
    /* 对每一个顶点做循环 */
    for (i = 0; i < G.numVertexes; i++)              
    {
        /* 若是未访问过就处理 */
        if (!visited[i])                             
        {
            /* 设置当前顶点访问过 */
            visited[i]=TRUE;                         
            /* 打印顶点，也可以其他操作 */
            printf("%c ", G.vexs[i]);                
            /* 将此顶点入队列 */
            EnQueue(&Q,i);                           
            /* 若当前队列不为空 */
            while (!QueueEmpty(Q))                   
            {
                /* 将队中元素出队列，赋值给i */
                DeQueue(&Q, &i);                     
                for (j = 0; j < G.numVertexes; j++)
                {
                    /* 判断其他顶点若与当前顶点存在边且未访问过 */
                    if (G.arc[i][j] == 1 && !visited[j])
                    {
                        /* 将找到的此顶点标记为已访问 */
                        visited[j]=TRUE;             
                        /* 打印顶点 */
                        printf("%c ", G.vexs[j]);    
                        /* 将找到的此顶点入队列 */
                        EnQueue(&Q,j);               
                    }
                }
            }
        }
    }
}

对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下:

/* 邻接表的广度遍历算法 */
void BFSTraverse(GraphAdjList GL)
{
    int i;
    EdgeNode *p;
    Queue Q;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = FALSE;
    InitQueue(&Q);
    for (i = 0; i < GL->numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i] = TRUE;
            /* 打印顶点，也可以其他操作 */
            printf("%c ", GL->adjList[i].data);    
            EnQueue(&Q, i);
            while (!QueueEmpty(Q))
            {
                DeQueue(&Q, &i);
                /* 找到当前顶点边表链表头指针 */
                p = GL->adjList[i].firstedge;      
                while (p)
                {
                    /* 若此顶点未被访问 */
                    if (!visited[p->adjvex])       
                    {
                        visited[p->adjvex] = TRUE;
                        printf("%c ", GL->adjList[p->adjvex].data);
                        /* 将此顶点入队列 */
                        EnQueue(&Q, p->adjvex);    
                    }
                    /* 指针指向下一个邻接点 */
                    p = p->next;                   
                }
            }
        }
    }
}

对比图的深度优先遍历与广度优先遍历算法可知，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的，只是视不同的情况选择不同的算法。
深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。