7-1 数据结构实验三 图的深度优先搜索 分数 50 作者 王群芳 单位 合肥师范学院 以邻接矩阵作存储结构,编写程序对给定的无向图(图中包含n个顶点,编号为0至n-1)进行深度优先遍历,并在遍历的过程中计算图G的连通

性分量数目，输出图的深度优先遍历序列和连通分量数目。

算法思路：

深度优先遍历算法（DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时已发现节点w，则回溯到节点v的前一个节点，再寻找未被探寻过的边。重复此过程，直到已访问到图的所有节点。

算法步骤：

1.定义一个visited数组，记录每个节点是否被访问过；

2.从任意一个节点开始，进行递归遍历，并将visited数组中对应的节点设为已访问；

3.遍历所有未被访问的节点，直到所有节点都被访问过。

代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int n, e;  // n：节点数，e：边数
int graph[MAX][MAX];  // 邻接矩阵表示的图
int visited[MAX];  // 记录每个节点是否被访问过

// 深度优先遍历函数
void DFS(int node) {
    visited[node] = 1;  // 将节点设为已访问

    // 输出节点编号
    printf("%d ", node);

    // 遍历与该节点相邻的未被访问过的节点
    for (int i = 0; i < n; i++) {
        if (graph[node][i] == 1 && visited[i] == 0) {
            DFS(i);
        }
    }
}

int main() {
    scanf("%d %d", &n, &e);

    // 初始化邻接矩阵为0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    // 读入边信息，更新邻接矩阵
    for (int i = 0; i < e; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;
    }

    // 初始化visited数组为0
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

    int count = 0;  // 记录连通分量数目

    // 遍历所有未被访问的节点
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            count++;  // 连通分量数目加1
            DFS(i);
        }
    }

    printf("\n连通分量数目：%d\n", count);

    return 0;
}

运行示例：

输入：

9 10
0 1
0 2
1 2
1 3
2 3
2 4
3 4
5 6
6 7
7 8

输出：

0 1 2 3 4 5 6 7 8 
连通分量数目：2

说明：输入的图有两个连通分量，分别为{0,1,2,3,4}和{5,6,7,8}。