使用完整的c语言实现:所有可能的路径 Description 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序) graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。 Input 整数n,表示 n 个节点 n * n个整数,表示有向无环图 若 a[i][j] 为0,说明两点无通路,若 a[i][j] 为1,说明从点 i 到点 j 有通路 Output 有多少条路径 Sample Input 1 4 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 Sample Output 1 2 Sample Input 2 5 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 Sample Output 2 5
时间: 2023-12-03 19:43:37 浏览: 28
这道题可以使用深度优先搜索(DFS)来遍历所有可能的路径。具体实现过程如下:
1. 定义一个全局变量 count,用于记录路径数量。
2. 定义一个数组 visited,用于记录每个节点是否被访问过。
3. 定义一个函数 dfs,用于遍历从当前节点到终点节点的所有路径。在函数中,首先将当前节点标记为已访问,然后遍历当前节点可以到达的所有节点,对于每个未被访问过的节点,递归调用 dfs 函数。当遍历到终点节点时,将 count 加 1,并返回。
4. 在主函数中调用 dfs 函数遍历从起点节点到终点节点的所有路径,并输出 count。
下面是完整的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
int n, count = 0;
int graph[MAXN][MAXN];
int visited[MAXN];
void dfs(int node) {
visited[node] = 1;
if (node == n - 1) {
count++;
visited[node] = 0;
return;
}
for (int i = 0; i < n; i++) {
if (graph[node][i] && !visited[i]) {
dfs(i);
}
}
visited[node] = 0;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
dfs(0);
printf("%d\n", count);
return 0;
}
```
输入格式:
第一行包含一个整数 n,表示节点的数量。
接下来 n 行,每行包含 n 个整数,表示有向无环图的邻接矩阵。
输出格式:
输出一个整数,表示从起点节点到终点节点的所有路径数量。
输入样例:
```
4
0 1 1 0
0 0 0 1
0 0 0 1
0 0 0 0
```
输出样例:
```
2
```