假设图G采用邻接表存储,设计一个算法,判断顶点u到顶点v之间是否有路径,并对以下有向图G判断从顶点0到顶点5、从顶点0到顶点2是否有路径用C语言编译
时间: 2024-04-30 09:25:16 浏览: 77
采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法
4星 · 用户满意度95%
以下是判断从顶点u到顶点v之间是否有路径的算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct EdgeNode {
int adjvex;
struct EdgeNode *next;
} EdgeNode;
typedef struct VertexNode {
int data;
EdgeNode *firstedge;
} VertexNode;
VertexNode adjList[MAX_VERTICES];
int visited[MAX_VERTICES];
void addEdge(int u, int v) {
EdgeNode *newNode = (EdgeNode *) malloc(sizeof(EdgeNode));
newNode->adjvex = v;
newNode->next = adjList[u].firstedge;
adjList[u].firstedge = newNode;
}
void dfs(int v) {
visited[v] = 1;
EdgeNode *p = adjList[v].firstedge;
while (p != NULL) {
int adjvex = p->adjvex;
if (!visited[adjvex]) {
dfs(adjvex);
}
p = p->next;
}
}
int hasPath(int u, int v) {
for (int i = 0; i < MAX_VERTICES; i++) {
visited[i] = 0;
}
dfs(u);
return visited[v];
}
int main() {
// 初始化邻接表
for (int i = 0; i < MAX_VERTICES; i++) {
adjList[i].data = i;
adjList[i].firstedge = NULL;
}
// 添加边
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 3);
addEdge(3, 4);
addEdge(3, 5);
addEdge(4, 5);
// 判断是否有路径
if (hasPath(0, 5)) {
printf("There is a path from 0 to 5.\n");
} else {
printf("There is no path from 0 to 5.\n");
}
if (hasPath(0, 2)) {
printf("There is a path from 0 to 2.\n");
} else {
printf("There is no path from 0 to 2.\n");
}
return 0;
}
```
对于以下有向图G,输出结果为:
```
There is a path from 0 to 5.
There is a path from 0 to 2.
```
其中,第一次判断从顶点0到顶点5是否有路径,结果为true;第二次判断从顶点0到顶点2是否有路径,结果也为true。
阅读全文