图的深度遍历

秒速五厘米 2021-11-16 14:46 286阅读 0赞

> 深度优先搜索类似于树的**前序遍历**

同样以如下连通图为例：  
![连通图][SouthEast]  
**构建其对应的邻接表：**  
![对应邻接表][SouthEast 1]  
采用深度优先搜素的遍历顺序如下：  
![1][]  
![2][]  
![3][]  
![4][]  
![5][]  
![6][]

**邻接表深度遍历结果：**

**范例输入：**

5 7  
1 2 3 4 5  
1 4  
1 3  
1 2  
2 4  
2 3  
3 5  
4 5

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

**邻接表深度遍历：**

void DFS(AdjList *G,int v)
    {
        //因为采用头插法创建邻接表，所以需要用栈进行逆序输出
        //如果用尾插法则不必如此
        int Stack[MaxSize],top = -1;    //创建栈
        ArcNode *p;
        visit[v] = 1;
        Stack[++top] = G->adjList[v].data;
    //    printf("%d\t",G->adjList[v].data);
        p = G->adjList[v].first;        //p指向G的第一条边
        while(p)
        {
            if(visit[p->adjvex] == 0)   //如果p所指向的边未被访问，则深度遍历并以p为顶点
                DFS(G,p->adjvex);
            p = p->next;
        }
        while(top!=-1)
            printf("%d\t",Stack[top--]);
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    #define MaxSize 20
    typedef struct node
    {
        int adjvex;
        node* next;
    }ArcNode;
    typedef struct
    {
        int data;
        ArcNode* first;
    }VerNode;
    typedef struct
    {
        VerNode adjList[MaxVertices];
        int n,e;
    }AdjList;
    void CreateGraph(AdjList *G)                //生成邻接表
    {
        int i,a,b;
        ArcNode *s;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&G->n,&G->e);
        printf("创建顶点表:\n");
        for(i=0;i<G->n;i++)
        {
            scanf("%d",&G->adjList[i].data);
            G->adjList[i].first = NULL;
        }
        printf("创建边表:\n");
        for(i=0;i<G->e;i++)
        {
            scanf("%d %d",&a,&b);
            a-=1;
            b-=1;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = b;
            s->next = G->adjList[a].first;
            G->adjList[a].first = s;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = a;
            s->next = G->adjList[b].first;
            G->adjList[b].first = s;
        }
    }
    int visit[MaxVertices];             //辅助数组，标记顶点是否已被访问
    void DFS(AdjList *G,int v)
    {
        //因为采用头插法创建邻接表，所以需要用栈进行逆序输出
        //如果用尾插法则不必如此
        int Stack[MaxSize],top = -1;    //创建栈
        ArcNode *p;
        visit[v] = 1;
        Stack[++top] = G->adjList[v].data;
    //    printf("%d\t",G->adjList[v].data);
        p = G->adjList[v].first;        //p指向G的第一条边
        while(p)
        {
            if(visit[p->adjvex] == 0)   //如果p所指向的边未被访问，则深度遍历并以p为顶点
                DFS(G,p->adjvex);
            p = p->next;
        }
        while(top!=-1)
            printf("%d\t",Stack[top--]);
    }
    int main()
    {
        AdjList *G = (AdjList*)malloc(sizeof(AdjList));
        CreateGraph(G);
        DFS(G,G->adjList[0].data);
    }

**邻接矩阵深度遍历（输入从0开始）：**

**范例输入：**

5 7  
0 1 2 3 4  
0 3  
0 2  
0 1  
1 3  
1 2  
2 4  
3 4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

**代码：**

int visit[MaxVertices];
    void DFS(AMGraph G,int v)
    {
        int i;
        visit[v] = 1;                       //设置当前顶点已被访问
        printf("%d\t",G.vexs[v]);
        for(i=0;i<G.n;i++)
            if(G.arcs[v][i]!=0&&!visit[i])  //这点的权值不为0说明v与该点有连接
                DFS(G,i);
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    typedef struct
    {
        int vexs[MaxVertices];
        int arcs[MaxVertices][MaxVertices];
        int n,e;
    }AMGraph;
    void CreateGraph(AMGraph &G)
    {
        int i,j,vi,vj;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&G.n,&G.e);
        printf("创建顶点表:\n");
        for(i=0;i<G.n;i++)
            scanf("%d",&G.vexs[i]);
        for(i=0;i<G.n;i++)      //初始化边表
        {
            for(j=0;j<G.n;j++)
            {
                G.arcs[i][j] = 0;  //每个顶点的权值初始化为0
            }
        }
        printf("创建边表:\n");
        for(i=0;i<G.e;i++)
        {
            scanf("%d %d",&vi,&vj);
            G.arcs[vi][vj] = 1;
            G.arcs[vj][vi] = 1;
        }
    }
    int visit[MaxVertices];
    void DFS(AMGraph G,int v)
    {
        int i;
        visit[v] = 1;                       //设置当前顶点已被访问
        printf("%d\t",G.vexs[v]);
        for(i=0;i<G.n;i++)
            if(G.arcs[v][i]!=0&&!visit[i])  //这点的权值不为0说明v与该点有连接
                DFS(G,i);
    }
    int main()
    {
        AMGraph G;
        CreateGraph(G);
        DFS(G,G.vexs[0]);
    }

[SouthEast]: /images/20211116/fbf9e7c8ddbb45eaaf73b293db7d90b0.png
[SouthEast 1]: /images/20211116/d0bd9e32df1f4177bf68e8d830d4a94b.png
[1]: /images/20211116/25a8907bdaeb43c3b242120ff0199fb4.png
[2]: /images/20211116/0c5c16ab8d944df1b34ebc7d131cd52d.png
[3]: /images/20211116/dfc7f1783bec463299986bc297b8f35a.png
[4]: /images/20211116/c26466fd85444fdf89435fb2ff766a17.png
[5]: /images/20211116/5323994d79e3496db69ac7ca2adaf8cc.png
[6]: /images/20211116/e33279835bc3469abc8b93f863d0facb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211116/435cf63073924c7ea4530b9ad5ed50aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20211116/94e53c5473fd4d5789d7b3dfe1dfb923.png