c语言判断有向图的连通性

判断有向图的连通性可以通过深度优先搜索或拓扑排序来实现。具体做法是从图中任选一个顶点开始搜索，标记已经访问过的顶点，并继续搜索该节点的出边指向的顶点，直到搜索完所有与该节点直接或间接相连的顶点。如果所有顶点都被标记过，则说明该图是连通的；否则，说明该图不连通。

以下是一个简单的 C 语言代码实现：

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

#define MAX_VERTICES 100 // 最大顶点数

int graph[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵表示
bool visited[MAX_VERTICES]; // 标记顶点是否被访问过

// 深度优先搜索
void dfs(int v, int n) {
    visited[v] = true;
    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {
            dfs(i, n);
        }
    }
}

// 判断图的连通性
bool is_connected(int n) {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    dfs(0, n);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, m; // n 为顶点数，m 为边数
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v; // 边的起点和终点
        scanf("%d%d", &u, &v);
        graph[u][v] = 1; // 标记邻接矩阵
    }
    if (is_connected(n)) {
        printf("The graph is connected.\n");
    } else {
        printf("The graph is not connected.\n");
    }
    return 0;
}

该程序首先读入图的顶点数和边数，然后读入每条边的起点和终点，标记邻接矩阵。之后调用 `is_connected` 函数判断图的连通性，最后输出结果。