【数据结构】图的遍历--深度优先搜索

r囧r小猫 2022-06-17 06:52 202阅读 0赞

**深度优先搜索（Depth First Search,DFS）**类似于树的先序遍历，是树的先序遍历的推广。  
假设初始状态是图中所有顶点未被访问，则深度优先搜索可以从图的某个顶点i出发，访问此结点，然后依次从i的未被访问的邻接点出发递归地进行同样的深度优先搜索，直至图中所有和i有路径相通的顶点都被访问到；若此时图中尚有未被访问的顶点（非连通图），则另选一个未被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到。

![这里写图片描述][SouthEast]  
以上图所示的无向图为例，A作为起始点，以字母序选择邻接点（理论上可以选择任意一个邻接点，但是在实际情况下算法是在一个确定的数据结构上运行的，所以会以一种确定的顺序选择邻接点，这里选择字母序），给出遍历结果如下：

A B D C E F G H I

![这里写图片描述][SouthEast 1]

再给出有向图的例子，以A作为起始点，仍以字母序选择邻接点，遍历结果如下：

A B C D E F

下面分别给出对用邻接矩阵和邻接表存储的图的深度优先搜索算法的代码描述。  
两种存储结构的代码描述参见之前的博文。

邻接矩阵的深度优先搜索

void DFS_M(MGraph G)
    {
        for(int i = 0; i < G->n; i++)
            G->Visited[i] = 0;  //初始化标志数组，这一步也可以在对图进行初始化操作时执行
        for(int i = 0; i < G->n; i++)
            if(!G->Visited[i]){
                DFS(G,i);
                printf("\n");
            }
    }
    
    void DFS(MGraph G, int i)
    {
        visit(G,i);
        for(int j = 0; j < G->n; j++){
            if(G->Edges[i][j] != INFINITY && !G->Visited[j])
                DFS(G,j);
        }
    }
    
    void visit(MGraph G, int i)
    {
        printf("%c ", G->Vertices[i]);
        G->Visited[i] = 1;
    }

邻接表的深度优先搜索

void DFS_ALG(ALGraph G)
    {
        for(int i = 0; i < G->n; i++)
            G->Visited[i] = 0; //初始化标志数组
        for(int i = 0; i < G->n; i++)
            if(!G->Visited[i]){
                DFS(G,i);     //如果顶点i没被访问，则从i开始搜索一个连通分量
                printf("\n");
            }
    }
    
    void DFS(ALGraph G, int i)
    {
        EdgeNode *p;
        printf("%c ", G->AdjList[i].Vertex); //访问顶点i
        G->Visited[i] = 1;                   //标记i已被访问
        for(p = G->AdjList[i].FirstEdge; p; p = p->Next)
            if(!G->Visited[p->AdjV])         //遍历顶点i的边表，如果有邻接点未被访问，则从这个顶点开始搜索
                DFS(G,p->AdjV);
    }

[SouthEast]: /images/20220617/acf14c40d41d400d86e82864ccad69a8.png
[SouthEast 1]: /images/20220617/19ae85bc3d964d639215e45f93b50f32.png