[C] 图的深度优先遍历_深度优先遍历图 c

图的DFS遍历

• 首先我们需要知道什么是图
  

• 简单地说，图就是由一些小圆点（称为顶点）和连接这些小圆点的直线（称为边）组成的。例如上图是由五个顶点（编号为1，2，3，4，5）和五条边（1-2，1-3，1-5，2-4，3-5）组成。

• 接下来我将会展示从1号顶点以DFS算法遍历这张图的代码。

• 每个顶点是第几个被访问到的，这个数字，称为时间戳。（在本段代码里没有体现）

代码实现

#include<stdio.h>
int book[2000], a[2000][2000];
int sum, n, m;

void dfs(int cur)
{
    int i;
    printf("%d ", cur);
    sum++;
    if (sum == n)
        return;
    for (i = 1; i <= n; i++)
    {
        if (a[cur][i] == 1 && book[i] == 0)
        {
            book[i] = 1;
            dfs(i);
        }
    }
    return;
}

int main()
{
    int i, j, m, x, y;
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);
        a[x][y] = 1;
        a[y][x] = 1;
    }
    book[1] = 1; //从第一个点出发
    dfs(1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

运行结果：

这张图DFS遍历顺序为1 2 4 3 5