用c语言编程判断一个图是否为连通图

在C语言中，可以使用邻接矩阵或邻接表来存储图的信息，然后使用深度优先搜索（DFS）或广度优先搜索（BFS）来进行遍历，判断图是否连通。下面是一个使用邻接矩阵和DFS来判断图是否连通的示例代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过

// 邻接矩阵存储图的结构体
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

// 深度优先搜索遍历图
void DFS(Graph *G, int v) {
    visited[v] = 1; // 标记该顶点已被访问
    for (int i = 0; i < G->vertex_num; i++) {
        if (G->edge[v][i] && !visited[i]) { // 如果该顶点的邻接顶点未被访问，则以该邻接顶点为起点进行遍历
            DFS(G, i);
        }
    }
}

// 判断图是否连通
int isConnected(Graph *G) {
    // 初始化visited数组
    for (int i = 0; i < G->vertex_num; i++) {
        visited[i] = 0;
    }

    // 从第一个顶点开始遍历
    DFS(G, 0);

    // 判断是否所有顶点都被访问过
    for (int i = 0; i < G->vertex_num; i++) {
        if (!visited[i]) {
            return 0; // 如果存在未被访问的顶点，则说明图不连通
        }
    }

    return 1; // 所有顶点都被访问过，则说明图连通
}

int main() {
    Graph G;
    G.vertex_num = 5;
    G.edge_num = 7;
    int vertex[] = {0, 1, 2, 3, 4};
    int edge[][2] = {{0, 1}, {0, 2}, {1, 2}, {2, 3}, {3, 4}, {4, 2}, {4, 1}};
    for (int i = 0; i < G.vertex_num; i++) {
        G.vertex[i] = vertex[i];
    }
    for (int i = 0; i < G.edge_num; i++) {
        int v1 = edge[i][0];
        int v2 = edge[i][1];
        G.edge[v1][v2] = G.edge[v2][v1] = 1;
    }

    if (isConnected(&G)) {
        printf("The graph is connected.\n");
    } else {
        printf("The graph is not connected.\n");
    }

    return 0;
}

在这个例子中，我们使用邻接矩阵存储图的信息，使用DFS遍历图，并使用visited数组记录顶点是否被访问过。最后判断visited数组中是否所有元素都为1，来判断图是否连通。