c语言图独立路径计算

计算图中的独立路径可以使用深度优先搜索（DFS）算法来解决。具体步骤如下：

1. 对于给定的图，从任意一个起点开始进行深度优先搜索。
2. 在搜索过程中，记录每个节点的访问状态。如果节点已经被访问过，则跳过该节点。
3. 对于每个找到的独立路径，记录其长度。
4. 当所有路径都被找到后，返回所有路径的长度。

下面是使用C语言实现的示例代码：

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

#define MAX_NODE 100

// 定义邻接矩阵结构体
struct Graph {
    int matrix[MAX_NODE][MAX_NODE]; // 邻接矩阵
    int num_nodes;                  // 节点数目
};

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

// 深度优先搜索函数
void dfs(struct Graph* g, int node, int depth, int* count) {
    int i;
    visited[node] = 1; // 标记节点已访问
    for (i = 0; i < g->num_nodes; i++) {
        // 如果邻接矩阵中该节点与当前节点有边，并且该节点未被访问，则继续深度优先搜索
        if (g->matrix[node][i] == 1 && visited[i] == 0) {
            dfs(g, i, depth+1, count);
        }
    }
    // 如果当前节点没有邻居节点，则说明该节点为独立路径的末尾，记录该路径的长度
    if (depth > 0 && i == g->num_nodes) {
        (*count)++;
    }
    visited[node] = 0; // 恢复节点为未访问状态
}

// 计算独立路径数目
int count_paths(struct Graph* g) {
    int i, count = 0;
    // 对每个节点进行深度优先搜索
    for (i = 0; i < g->num_nodes; i++) {
        dfs(g, i, 0, &count);
    }
    return count;
}

int main() {
    struct Graph g;
    int i, j, num_edges, start, end;

    // 读入图的节点数目和边数
    scanf("%d %d", &g.num_nodes, &num_edges);

    // 初始化邻接矩阵
    for (i = 0; i < g.num_nodes; i++) {
        for (j = 0; j < g.num_nodes; j++) {
            g.matrix[i][j] = 0;
        }
    }

    // 读入边信息，并在邻接矩阵中标记相应的位置
    for (i = 0; i < num_edges; i++) {
        scanf("%d %d", &start, &end);
        g.matrix[start][end] = 1;
    }

    // 计算独立路径数目并输出结果
    printf("%d", count_paths(&g));

    return 0;
}