试基于图的深度优先搜索策略写一c语言算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点 vj的路径,(i≠j)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。
时间: 2024-02-25 15:59:01 浏览: 134
采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径.doc
以下是基于邻接表存储结构的C语言代码实现了判断有向图中是否存在由顶点vi到顶点vj的路径的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
int adjvex; // 邻接顶点的位置
struct ArcNode *nextarc; // 指向下一个邻接顶点的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接顶点的指针
} VNode;
typedef struct {
VNode adjlist[MAX_VERTEX_NUM]; // 邻接表
int vexnum, arcnum; // 顶点数目和弧的数目
} ALGraph;
// 定位一个顶点在顶点信息数组中的位置
int locateVex(ALGraph *G, char v) {
for (int i = 0; i < G->vexnum; i++) {
if (G->adjlist[i].data == v) {
return i;
}
}
return -1;
}
// 插入一个顶点
void insertVex(ALGraph *G, char v) {
if (G->vexnum == MAX_VERTEX_NUM) {
printf("插入失败,顶点数已达到上限!\n");
return;
}
G->adjlist[G->vexnum].data = v; // 将新顶点添加到顶点信息数组中
G->adjlist[G->vexnum].firstarc = NULL; // 初始化该顶点的邻接表
G->vexnum++;
}
// 插入一条弧
void insertArc(ALGraph *G, char v, char w) {
int i = locateVex(G, v);
int j = locateVex(G, w);
if (i == -1 || j == -1) {
printf("插入失败,顶点不存在!\n");
return;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p; // 将新弧添加到邻接表中
G->arcnum++;
}
// 深度优先搜索算法
void DFS(ALGraph *G, int i, bool visited[], int j, bool *flag) {
visited[i] = true; // 标记该顶点已经被访问过
if (i == j) {
*flag = true; // 找到了vi到vj的路径,将标志位置为true
return;
}
ArcNode *p = G->adjlist[i].firstarc;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited, j, flag); // 递归搜索邻接顶点
}
p = p->nextarc;
}
}
// 判断有向图中是否存在由顶点vi到顶点vj的路径
bool hasPath(ALGraph *G, char vi, char vj) {
int i = locateVex(G, vi);
int j = locateVex(G, vj);
if (i == -1 || j == -1) {
printf("判断失败,顶点不存在!\n");
return false;
}
bool visited[MAX_VERTEX_NUM] = {false}; // 初始化所有顶点为未访问
bool flag = false; // 判断标志
DFS(G, i, visited, j, &flag); // 从vi开始深度优先搜索
return flag;
}
// 测试函数
int main() {
ALGraph G;
G.vexnum = 0;
G.arcnum = 0;
insertVex(&G, 'A');
insertVex(&G, 'B');
insertVex(&G, 'C');
insertArc(&G, 'A', 'B');
insertArc(&G, 'B', 'C');
printf("%d\n", hasPath(&G, 'A', 'C')); // 输出1,表示存在从A到C的路径
printf("%d\n", hasPath(&G, 'C', 'A')); // 输出0,表示不存在从C到A的路径
return 0;
}
```
该代码实现了判断有向图中是否存在由顶点vi到顶点vj的路径的算法,该算法基于深度优先搜索策略实现。首先,通过locateVex函数定位顶点vi和vj在邻接表中的位置;然后,在DFS函数中,从顶点vi开始深度优先搜索,递归搜索邻接顶点,直到找到顶点vj或者搜索完所有与vi相邻的顶点;最后,在hasPath函数中判断是否找到了vi到vj的路径。
阅读全文