采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的c语言算法。
时间: 2023-12-14 16:13:03 浏览: 209
无向图的邻接表存储及输出
4星 · 用户满意度95%
以下是一个基于深度优先搜索的c语言算法,用于判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径:
```c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct ArcNode{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;
typedef struct VNode{
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和弧数
}ALGraph;
bool visited[MAX_VERTEX_NUM]; //用于记录顶点是否被访问过的数组
void CreateGraph(ALGraph *G){
int i, j, k;
ArcNode *p;
printf("请输入顶点数和弧数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入%d个顶点的值:\n", G->vexnum);
for(i = 0; i < G->vexnum; i++){
G->vertices[i].firstarc = NULL;
}
printf("请输入%d条弧的起点和终点:\n", G->arcnum);
for(k = 0; k < G->arcnum; k++){
scanf("%d%d", &i, &j);
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
void DFS(ALGraph G, int v, int k, int target, bool *flag){
ArcNode *p;
visited[v] = true;
if(k == 0 && v == target){ //找到一条长度为k的路径
*flag = true;
return;
}
for(p = G.vertices[v].firstarc; p && !(*flag); p = p->nextarc){
if(!visited[p->adjvex]){
DFS(G, p->adjvex, k-1, target, flag);
}
}
visited[v] = false;
}
bool FindPath(ALGraph G, int u, int v, int k){
bool flag = false;
DFS(G, u, k, v, &flag);
return flag;
}
int main(){
ALGraph G;
CreateGraph(&G);
int u, v, k;
printf("请输入需要判断的两个顶点u和v,以及路径长度k:\n");
scanf("%d%d%d", &u, &v, &k);
if(FindPath(G, u, v, k)){
printf("存在一条长度为%d的简单路径从顶点%d到顶点%d!\n", k, u, v);
}
else{
printf("不存在一条长度为%d的简单路径从顶点%d到顶点%d!\n", k, u, v);
}
return 0;
}
```
该算法先通过CreateGraph函数创建邻接表存储的无向图,然后通过DFS函数深度优先搜索图中从顶点u到顶点v的所有长度为k的简单路径。在搜索过程中,用visited数组记录每个顶点是否被访问过,用flag指针记录是否找到了一条符合要求的路径。如果找到了一条长度为k的路径,则将flag指针设为true。最后,通过FindPath函数判断是否存在一条长度为k的简单路径从顶点u到顶点v,如果存在,则返回true,否则返回false。
阅读全文