C语言 采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法代码。
时间: 2023-12-14 15:11:48 浏览: 153
采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k得简单路径的算法
4星 · 用户满意度95%
以下是基于邻接表存储结构的无向图判别算法,用于判断任意给定的两个顶点之间是否存在一条长度为k的简单路径。其中,k为输入的参数。
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXV 1000
// 边表结构体
typedef struct EdgeNode {
int adjvex; // 邻接点在顶点数组中的下标
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点表结构体
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode;
// 图结构体
typedef struct Graph {
VertexNode adjlist[MAXV]; // 顶点数组
int n, e; // 顶点数和边数
} Graph;
// 初始化图
void initGraph(Graph *G) {
G->n = G->e = 0;
for (int i = 0; i < MAXV; i++) {
G->adjlist[i].data = 0;
G->adjlist[i].firstedge = NULL;
}
}
// 添加边
void addEdge(Graph *G, int u, int v) {
EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = v;
e->next = G->adjlist[u].firstedge;
G->adjlist[u].firstedge = e;
G->e++;
}
// 判断是否存在长度为k的简单路径
bool hasSimplePath(Graph *G, int u, int v, int k) {
if (k == 0 && u == v) { // 起点和终点相同,路径长度为0,返回真
return true;
}
if (k == 1 && G->adjlist[u].firstedge != NULL) { // 直接相邻,路径长度为1,返回真
EdgeNode *p = G->adjlist[u].firstedge;
while (p != NULL) {
if (p->adjvex == v) {
return true;
}
p = p->next;
}
}
if (k > 1) { // 中间有一个或多个顶点
EdgeNode *p = G->adjlist[u].firstedge;
while (p != NULL) {
if (hasSimplePath(G, p->adjvex, v, k-1)) {
return true;
}
p = p->next;
}
}
return false;
}
int main() {
Graph G;
initGraph(&G);
// 读入图
int n, m;
scanf("%d%d", &n, &m);
G.n = n;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(&G, u, v);
addEdge(&G, v, u);
}
// 输入查询
int u, v, k;
scanf("%d%d%d", &u, &v, &k);
bool ans = hasSimplePath(&G, u, v, k);
printf("%s\n", ans ? "yes" : "no");
return 0;
}
```
在上述代码中,我们使用了递归的方式判断是否存在长度为k的简单路径。当k为0时,判断起点和终点是否相同;当k为1时,判断起点的邻接点是否为终点;当k大于1时,分别判断起点的邻接点是否存在长度为k-1的简单路径。
阅读全文