c语言用邻接矩阵存储图并判断图的连通性

邻接矩阵是一种存储图的方式，可以用一个二维数组表示图的连接情况。对于一个无向图，如果i和j之间有边相连，则邻接矩阵中的第i行第j列和第j行第i列都为1，否则为0。对于一个有向图，如果从i到j有一条有向边，则邻接矩阵中的第i行第j列为1，否则为0。

判断无向图是否连通，可以使用深度优先遍历或广度优先遍历。具体思路是：从任意一个节点开始遍历整个图，如果能够遍历到所有节点，则说明该无向图是连通的。

以下是使用深度优先遍历来实现判断无向图连通性的代码：

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

#define MAX_VERTEX_NUM 100

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

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

void dfs(Graph G, int v) {
    visited[v] = 1;  // 标记节点v已经被访问过
    for (int i = 0; i < G.vertex_num; i++) {
        if (G.edge[v][i] && !visited[i]) {  // 如果v和i之间有边相连且i未被访问过
            dfs(G, i);  // 递归访问节点i
        }
    }
}

int is_connected(Graph G) {
    for (int i = 0; i < G.vertex_num; i++) {
        visited[i] = 0;  // 初始化visited数组
    }
    dfs(G, 0);  // 从任意一个节点开始遍历
    for (int i = 0; i < G.vertex_num; i++) {
        if (!visited[i]) {  // 如果存在未被访问的节点，则说明该无向图不连通
            return 0;
        }
    }
    return 1;  // 否则说明该无向图是连通的
}

int main() {
    Graph G;
    scanf("%d %d", &G.vertex_num, &G.edge_num);
    for (int i = 0; i < G.vertex_num; i++) {
        scanf("%d", &G.vertex[i]);
    }
    for (int i = 0; i < G.vertex_num; i++) {
        for (int j = 0; j < G.vertex_num; j++) {
            G.edge[i][j] = 0;  // 初始化邻接矩阵
        }
    }
    for (int i = 0; i < G.edge_num; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G.edge[u][v] = G.edge[v][u] = 1;  // 无向图的边是双向的，因此需要同时设置i和j之间的边
    }
    if (is_connected(G)) {
        printf("The graph is connected.\n");
    } else {
        printf("The graph is not connected.\n");
    }
    return 0;
}

对于有向图的连通性判断，可以使用类似的方法，只需要将深度优先遍历改为拓扑排序即可。