图的遍历及连通性DFSc语言代码

以下是一个使用深度优先搜索（DFS）算法遍历图并检查其连通性的C语言代码：

#include <stdio.h>
#include <stdbool.h>

// 定义图的最大大小
#define MAX_SIZE 100

// 定义图的结构体
typedef struct Graph {
    int num_vertices;  // 图的顶点数
    int num_edges;     // 图的边数
    int adj_matrix[MAX_SIZE][MAX_SIZE];  // 图的邻接矩阵
} Graph;

// 定义全局变量visited，用于记录节点是否已被访问
bool visited[MAX_SIZE];

// DFS函数，用于遍历图
void DFS(Graph *G, int v) {
    int i;
    visited[v] = true;
    for (i = 0; i < G->num_vertices; i++) {
        if (G->adj_matrix[v][i] == 1 && !visited[i]) {
            DFS(G, i);
        }
    }
}

// 检查图的连通性
bool is_connected(Graph *G) {
    int i;
    // 初始化visited数组
    for (i = 0; i < G->num_vertices; i++) {
        visited[i] = false;
    }
    // DFS遍历图
    DFS(G, 0);
    // 检查visited数组是否全部为true，如果是则说明图是连通的
    for (i = 0; i < G->num_vertices; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    Graph G;
    int i, j;
    // 读入图的顶点数和边数
    scanf("%d %d", &G.num_vertices, &G.num_edges);
    // 初始化邻接矩阵
    for (i = 0; i < G.num_vertices; i++) {
        for (j = 0; j < G.num_vertices; j++) {
            G.adj_matrix[i][j] = 0;
        }
    }
    // 读入图的边
    for (i = 0; i < G.num_edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        // 在邻接矩阵中标记两个节点之间有边
        G.adj_matrix[u][v] = 1;
        G.adj_matrix[v][u] = 1;
    }
    // 检查图的连通性
    if (is_connected(&G)) {
        printf("The graph is connected.\n");
    } else {
        printf("The graph is not connected.\n");
    }
    return 0;
}

该代码中定义了一个Graph结构体，表示图的基本信息，包括顶点数、边数和邻接矩阵等。DFS函数使用DFS算法遍历图，在遍历过程中标记visited数组，用于记录节点是否已被访问。is_connected函数用于检查图的连通性，通过调用DFS函数实现遍历，并检查visited数组是否全部为true，以确定图是否连通。最后，在main函数中读入图的基本信息，并调用is_connected函数检查图的连通性。