已知有向图和图中两个顶点,u和v,试编写C语言算法求有向图中从u到v的所有简单路径
时间: 2023-06-14 12:05:25 浏览: 203
已知有向图和图中两个顶点u和v,试编写算法求有向图中从u到v的所有简单路径。
5星 · 资源好评率100%
以下是使用深度优先搜索(DFS)算法实现的C语言代码,可以求解有向图中从u到v的所有简单路径:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100 // 最大顶点数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int visited[MAX_VERTICES]; // 标记已访问的顶点
int path[MAX_VERTICES]; // 记录路径
int path_len = 0; // 当前路径长度
void dfs(int cur, int end) {
visited[cur] = 1;
path[path_len++] = cur;
if (cur == end) { // 找到一条路径
for (int i = 0; i < path_len; i++) {
printf("%d ", path[i]);
}
printf("\n");
} else {
for (int i = 0; i < MAX_VERTICES; i++) {
if (adj_matrix[cur][i] && !visited[i]) { // 如果存在边且未访问过
dfs(i, end);
}
}
}
visited[cur] = 0;
path_len--;
}
int main() {
int n; // 顶点数
int u, v; // 起点和终点
printf("请输入顶点数:");
scanf("%d", &n);
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
adj_matrix[i][j] = 0;
}
}
printf("请输入边数:");
int m;
scanf("%d", &m);
printf("请输入各边的起点和终点:\n");
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
adj_matrix[u][v] = 1; // 有向边
}
printf("请输入起点和终点:");
scanf("%d%d", &u, &v);
dfs(u, v);
return 0;
}
```
该算法的基本思路是深度优先搜索,从起点u开始遍历,如果遇到终点v则输出路径。如果当前顶点不是终点,就继续遍历它的邻接顶点,直到遇到终点或者所有路径都被遍历完。在遍历过程中,需要记录已访问的顶点和当前路径,以避免重复访问和形成环路。
阅读全文