C语言入门——DFS图的深度优先遍历

本博客为考试服务。

（虽然我也不知道为什么C语言入门要考这些东西）

一、简单地认识图

图是什么？

好吧我也不知道。具体参见这个网站：

 图（图论术语）_百度百科 (baidu.com)

通俗来讲，图就是由若干节点和若干边组成的一种数据结构。节点代表着元素，而边就代表着节点之间的某种关系。如果你觉得这个概念太抽象，还是听不懂，那么我在这里举个栗子：

假设某地区有5个村，分别叫做A,B,C,D,E，其中，一些村庄之间会有道路连通。于是我们便可以画出这个：

 这就是一个图。其中，五个村庄就是图的节点，而道路就是图的边，表示它们相互连通的关系。

二、怎样表示图

图可以用两种方式表示，一种是邻接矩阵（Adjacency Matrix）表示法，一种是邻接表（Adjacency List）表示法。邻接矩阵就是一个二维数组，如果第i，第j个元素存在边的关系，那么就可以将数组第i行第j列的元素赋值为1，否则赋值为0. 邻接表涉及到链表的知识，这里不再涉及，大家只需要掌握邻接矩阵表示法即可。

所以我们可以这样定义表的结构：

typedef struct GraphNode* Graph;
struct GraphNode{
    Elementtype* element;//各个节点对应的元素值
    int NodesSize;//节点的数量
    bool** Adjacency_Matrix;//邻接矩阵
}GraphNode;

三、图的深度优先遍历

“深度优先”，通俗来讲就是找准一条路一直往下走，直到不能走了为止。

比如拿上面的图来说，假设我们从A村出发，我们面前有3条路，我们选择其中的一条，比如这里我们选择去往B。

到达B村之后，我们有两条路可走，一条去往A村，一条去往D村。A村我们已经访问过了，所以我们去往D村。

到达D村之后，可以去往A,B,C村。但是A和B都已经去过了，所以我们选择访问C村。

到达C村之后，我们发现，与C村连通的所有村庄我们都去过了。这时原路返回，回到D村。

到达D村之后，我们发现，与D村连通的所有村庄我们都去过了。我们原路返回，回到B村。

B村也是一样的情况，我们回到A村后发现，还有一个E村没有去，我们去往E村。

到达E村之后，我们发现，与E村连通的所有村庄我们都去过了。我们返回A村。

这时，与起点A村连通的所有村庄我们都去过了，说明我们已经遍历完所有能够访问的村落，遍历结束。

在上述描述中，我们可以发现，“去过”还是“没去过”这个词频繁出现。当一个村子已经被访问了，我们为了避免重复就不能去了。所以我们需要开一个数组，来记录每个村子去没去过。

bool visited[G->NodesSize];

在遍历开始之前，所有的村庄我们都没去过，所以，visited的初始值应全为false。

memset(visited,0,NodesSize);

我们在选择去哪一个村庄时，我们应当考察这个村庄有没有路与我们目前所在的村庄连通。并且还要考察这个村庄是否已经被访问过。如果有路连通且尚未访问，我们便可以进行递归调用，访问下一个村庄。这里我将这个过程抽象成一段“伪码”：

void DFS(传入图，visited，目前所在的村庄三个参数)
{
    将目前所在的村庄标记为“已经访问”;
    for(所有的村庄）{
        if(该村庄与目前的村庄有路相通且该村未被访问){
           DFS(该村庄);
        }
    }
}         

现在，深度优先搜索的所有细节问题都已经处理完了。

下面给出代码实现：

注意：图的节点可以是任意数据类型的，这里为了编译通过，我们用int代替。

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
typedef struct GraphNode* Graph;
struct GraphNode{
    int* element;
    bool** Adjacency_Matrix;
    int Capacity;
}GraphNode;//图的三个数据域：节点个数，节点的值，图的边
Graph NewGraph(int NodesSize){
    if(NodesSize<=0) return NULL;//输入限制
    Graph G=(Graph)malloc(sizeof(GraphNode));
    G->Adjacency_Matrix=(bool**)malloc(sizeof(bool*)*NodesSize);
    for(int i=0;i<NodesSize;i++){
        G->Adjacency_Matrix[i]=(bool*)malloc(sizeof(bool)*NodesSize);
    }//构建邻接矩阵
    for(int i=0;i<NodesSize;i++){
        for(int j=0;j<NodesSize;j++){
            G->Adjacency_Matrix[i][j]=0;
        }
    }
    G->element=(int*)malloc(sizeof(int)*NodesSize);
    for(int i=0;i<NodesSize;i++){
        scanf("%d",&G->element[i]);
    }//输入数据域（节点对应的值，这里用int类型）
    G->Capacity=NodesSize;//节点的个数
    return G;
}
Graph DFS(Graph G,int Nodesth,bool* visited){
    if(visited[Nodesth]==0){//递归入口，第一个数据没有被访问，先访问第一个
        visited[Nodesth]=1;
        printf("%d ",G->element[Nodesth]);
    }
    for(int i=0;i<G->Capacity;i++){
        if(G->Adjacency_Matrix[Nodesth][i]==1){
            if(visited[i]==0){
                visited[i]=1;
                printf("%d ",G->element[i]);
                DFS(G,i,visited);
            }
        }
    }//递归的主体
}
int main(){
    int numsSize;
    scanf("%d",&numsSize);
    if(numsSize<=1) return 0;
    bool visited[numsSize];
    memset(visited,0,numsSize*sizeof(bool));
    Graph G=NewGraph(numsSize);
    int relationshipSize;
    scanf("%d",&relationshipSize);
    for(int i=0;i<relationshipSize;i++){
        int t1,t2;
        scanf("%d",&t1);scanf("%d",&t2);
        if(t1!=t2&&t1>=0&&t2>=0&&t1<G->Capacity&&t2<G->Capacity){
            G->Adjacency_Matrix[t1][t2]=1;
            G->Adjacency_Matrix[t2][t1]=1;
        }
    }//添加边的关系
    DFS(G,0,visited);
    //请在这里自行补充释放内存空间的命令。
}

四、练习

独立编写DFS的程序，并提交从0号节点深度优先遍历这幅图的运行结果。

在这幅图中，节点中的数字代表着节点的编号。在访问到每个节点的时候，直接打印该节点的编号即可。