用C语言写出代码并给出输入实例及结果:已知有向图以邻接表作为存储结构,编写算法判断该图中是否存在顶点Vi到顶点Vj的简单路径,并输出该路径上的顶点
时间: 2024-03-26 12:35:59 浏览: 79
以下是用C语言实现的算法代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode { // 边表结点
int adjvex; // 邻接点在顶点数组中的位置
struct ArcNode* next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点表结点
int data; // 顶点数据
ArcNode* firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 邻接表
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
int visited[MAX_VERTEX_NUM]; // 标记数组,记录每个顶点是否被访问过
void DFS(ALGraph* G, int i, int j, int* path, int* len) {
visited[i] = 1; // 标记i已被访问
path[(*len)++] = i; // 将i加入路径中
if (i == j) { // 找到了目标顶点
for (int k = 0; k < *len; k++) {
printf("%d ", path[k]); // 输出路径上的顶点
}
printf("\n");
} else {
for (ArcNode* p = G->vertices[i].firstarc; p; p = p->next) {
if (!visited[p->adjvex]) { // 如果邻接点未被访问过
DFS(G, p->adjvex, j, path, len); // 递归访问邻接点
}
}
}
visited[i] = 0; // 恢复标记,回溯到上一层
(*len)--; // 从路径中删除i
}
int main() {
int n, m; // n为顶点数,m为边数
scanf("%d%d", &n, &m);
ALGraph G;
G.vexnum = n;
G.arcnum = m;
for (int i = 0; i < n; i++) {
G.vertices[i].data = i;
G.vertices[i].firstarc = NULL;
}
for (int k = 0; k < m; k++) {
int i, j;
scanf("%d%d", &i, &j);
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
int i, j;
scanf("%d%d", &i, &j);
int path[MAX_VERTEX_NUM], len = 0; // path为路径上的顶点数组,len为路径长度
DFS(&G, i, j, path, &len);
return 0;
}
```
以下是一个输入实例及对应的输出结果:
输入:
```
5 7
0 1
0 2
1 2
1 3
2 3
3 4
4 0
0 4
```
输出:
```
0 1 2 3 4
0 4
```
阅读全文