假设图G采用邻接表存储,用C语言设计一个算法,判断顶点u到顶点v之间是否有路径,并对以下有向图G判断从顶点0到顶点5、从顶点0到顶点2是否有路径。
时间: 2023-07-14 11:12:35 浏览: 86
采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径.doc
邻接表存储的图可以用结构体和指针来实现。我们可以定义一个结构体`Node`表示每个顶点,其中包含一个指向邻接点的指针和一个顶点编号。然后用一个数组`adjList`来存储所有的顶点,数组中每个元素是一个指向`Node`结构体的指针。
下面是判断顶点u到顶点v之间是否有路径的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 邻接点结构体
typedef struct Node {
int vertex; // 邻接点编号
struct Node* next; // 指向下一个邻接点的指针
} Node;
// 图结构体
typedef struct {
Node* adjList[MAX_VERTEX_NUM]; // 邻接表
int vertexNum; // 顶点数
int edgeNum; // 边数
} Graph;
// 初始化图
void initGraph(Graph* g, int vertexNum) {
g->vertexNum = vertexNum;
g->edgeNum = 0;
for (int i = 0; i < vertexNum; ++i) {
g->adjList[i] = NULL;
}
}
// 添加边
void addEdge(Graph* g, int u, int v) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = g->adjList[u];
g->adjList[u] = newNode;
g->edgeNum++;
}
// 判断是否有路径
int hasPath(Graph* g, int u, int v) {
int visited[MAX_VERTEX_NUM] = {0};
visited[u] = 1;
for (Node* p = g->adjList[u]; p != NULL; p = p->next) {
if (p->vertex == v) {
return 1;
}
if (!visited[p->vertex]) {
visited[p->vertex] = 1;
if (hasPath(g, p->vertex, v)) {
return 1;
}
}
}
return 0;
}
int main() {
Graph g;
initGraph(&g, 6);
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 2, 3);
addEdge(&g, 2, 4);
addEdge(&g, 3, 5);
printf("0到5是否有路径: %s\n", hasPath(&g, 0, 5) ? "是" : "否");
printf("0到2是否有路径: %s\n", hasPath(&g, 0, 2) ? "是" : "否");
return 0;
}
```
在上面的代码中,我们首先定义了`Node`结构体表示邻接点,其中包含一个顶点编号和指向下一个邻接点的指针。然后定义了`Graph`结构体表示图,其中包含了邻接表和顶点数、边数等信息。初始化图使用`initGraph`函数实现,添加边使用`addEdge`函数实现。
判断顶点u到顶点v之间是否有路径的函数是`hasPath`。该函数使用一个数组`visited`记录已经访问过的顶点,如果顶点v已经被访问过,则说明存在一条从顶点u到顶点v的路径,直接返回1。否则,遍历顶点u的所有邻接点,如果邻接点未被访问,则递归调用`hasPath`函数进行搜索。
在`main`函数中,我们构造了一个有向图,并分别判断从顶点0到顶点5和从顶点0到顶点2是否有路径。
阅读全文