【数据结构 | C语言】求图(邻接表)两个顶点之间的简单路径算法 C语言实现
2022/2/6 20:12:36
本文主要是介绍【数据结构 | C语言】求图(邻接表)两个顶点之间的简单路径算法 C语言实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 算法
- 文字说明
- 完整代码
算法
void SamplePath(pGraph graph, ElemType vexa, ElemType vexb) { // path是结构体类型,存放图的顶点,和存储数量。就是个栈 Path *path = (Path *) malloc(sizeof(Path)); memset(path, 0, sizeof(Path)); // 标志数组 bool searched[MAX_SIZE]; bool found=false; int i; for (i=0; i<MAX_SIZE; i++) searched[i] = false; // 先找到 a for (i=0; i<graph->vexnum; i++) if (graph->vertices[i].data==vexa) break; // 调用 SampleP 生成路径 SampleP(graph, i, vexb, path, searched, 0, &found); // 如果遍历完图,没有找到路径,说明两顶点不连通 if (path->path[path->final-1].data!=vexb) { printf("%c与%c不连通\n", vexa, vexb); return ; } for (int i=0; i<path->final; i++) printf("%c\t", path->path[i].data); printf("\n"); } // 参数: v,搜索的结点索引, vexb 是目标结点, path 存放路径, found 如果找到了就为 true,否则一直为 false void SampleP(pGraph graph, int v, ElemType vexb, Path *path, bool *searched, bool *found) { searched[v] = true; // 把当前结点添加进 路径 中 Add(path, graph->vertices[v]); // 循环遍历结点的邻接点 for (ArcNode *arc=graph->vertices[v].firstArc; arc!=NULL && *found==false; arc=arc->nextArc) { // 如果找到了,把 目标顶点添加进 路径中 if (graph->vertices[arc->adj].data==vexb) { *found = true; Add(path, graph->vertices[arc->adj]); } // 如果没遍历过该结点,递归遍历 else if (searched[arc->adj]==false) SampleP(graph, arc->adj, vexb, path, searched, found); } // 没找到,把当前结点退出栈 if (*found==false) Delete(path); }
文字说明
搜索路径,利用栈
- 把遍历的结点入栈,并遍历该结点的邻接点。
- 若邻接点未被访问过,递归搜索邻接点
- 如果所有的邻接点遍历完,都没有目标结点,那么当前结点出栈。退回上一个顶点
- 重复 步骤 1-3 。
- 当找到结点时, found 相当于全局变量,告诉递归函数,已经找到
完整代码
# include <stdio.h> # include <stdlib.h> # include <string.h> # define MAX_SIZE 20 # define true 1 # define false 0 typedef char ElemType; typedef int bool; typedef enum { DG, DN, UDG, UDN } GraphKind; typedef struct ArcNode { int adj; // 指向弧头 struct ArcNode *nextArc; // 指向的下一个弧头 ElemType *info; // 弧尾信息 } ArcNode; typedef struct { ElemType data; // 数据域 ArcNode *firstArc; // 第一个弧头 } VNode, AdjList[MAX_SIZE]; typedef struct { VNode path[MAX_SIZE]; int final; } Path; typedef struct { AdjList vertices; // 数据域 int vexnum, arcnum; // 顶点数,弧数 GraphKind kind; // 图类型 } Graph, *pGraph; // 路径 void Add(Path *path, VNode c); void Delete(Path *path); // 图 pGraph CreateGraph(GraphKind kind); void AddVex(pGraph graph, ElemType vex); void AddArc(pGraph graph, ElemType vexa, ElemType vexb); // 求两个顶点之间的简单路径 void SamplePath(pGraph graph, ElemType vexa, ElemType vexb); void SampleP(pGraph graph, int v, ElemType vexb, Path *path, bool *searched, bool *found); int main() { pGraph graph = CreateGraph(DG); // 添加结点 AddVex(graph, 'a'); AddVex(graph, 'b'); AddVex(graph, 'c'); AddVex(graph, 'd'); AddVex(graph, 'e'); AddVex(graph, 'f'); AddVex(graph, 'g'); AddVex(graph, 'h'); AddVex(graph, 'k'); // 添加弧 AddArc(graph, 'a', 'b'); AddArc(graph, 'c', 'a'); AddArc(graph, 'b', 'd'); AddArc(graph, 'b', 'e'); AddArc(graph, 'd', 'h'); AddArc(graph, 'e', 'h'); AddArc(graph, 'c', 'f'); AddArc(graph, 'c', 'g'); AddArc(graph, 'f', 'g'); /* // 广度优先遍历 WidFirstSearch(graph, 'a'); // 深度优先遍历 DeepFirstSearch(graph, 'a'); */ /* // 创建图 pGraph graph = CreateGraph(UDN); // 添加顶点 AddVex(graph, 'a'); AddVex(graph, 'b'); AddVex(graph, 'c'); AddVex(graph, 'd'); AddVex(graph, 'e'); AddVex(graph, 'f'); AddVex(graph, 'g'); // 添加边 AddArc(graph, 'a', 'b'); AddArc(graph, 'a', 'c'); AddArc(graph, 'a', 'd'); AddArc(graph, 'a', 'e'); AddArc(graph, 'a', 'f'); AddArc(graph, 'a', 'g'); AddArc(graph, 'b', 'c'); AddArc(graph, 'd', 'e'); AddArc(graph, 'f', 'g'); */ // 找路径 SamplePath(graph, 'a', 'k'); SamplePath(graph, 'a', 'e'); return 0; } pGraph CreateGraph(GraphKind kind) { pGraph new = (pGraph) malloc(sizeof(Graph)); memset(new, 0, sizeof(Graph)); new->kind = kind; return new; } void AddVex(pGraph graph, ElemType vex) { graph->vertices[graph->vexnum++].data = vex; } void AddArc(pGraph graph, ElemType vexa, ElemType vexb) { // 找到元素索引 int index_a, index_b; for (int i=0; i<graph->vexnum; i++) { if (graph->vertices[i].data==vexa) index_a = i; if (graph->vertices[i].data==vexb) index_b = i; } // 创建弧结点 ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode)); memset(node, 0, sizeof(ArcNode)); node->adj = index_b; // 添加弧结点 if (graph->vertices[index_a].firstArc==NULL) graph->vertices[index_a].firstArc = node; else { ArcNode *final = graph->vertices[index_a].firstArc; while (final->nextArc!=NULL) final = final->nextArc; final->nextArc = node; } // 弧的另一个结点 node = (ArcNode *) malloc(sizeof(ArcNode)); memset(node, 0, sizeof(ArcNode)); node->adj = index_a; // 添加弧结点 if (graph->vertices[index_b].firstArc==NULL) graph->vertices[index_b].firstArc = node; else { ArcNode *final = graph->vertices[index_b].firstArc; while (final->nextArc!=NULL) final = final->nextArc; final->nextArc = node; } graph->arcnum++; } void SamplePath(pGraph graph, ElemType vexa, ElemType vexb) { Path *path = (Path *) malloc(sizeof(Path)); memset(path, 0, sizeof(Path)); // 标志数组 bool searched[MAX_SIZE]; bool found=false; int i; for (i=0; i<MAX_SIZE; i++) searched[i] = false; // 先找到 a for (i=0; i<graph->vexnum; i++) if (graph->vertices[i].data==vexa) break; SampleP(graph, i, vexb, path, searched, &found); if (path->path[path->final-1].data!=vexb) { printf("%c与%c不连通\n", vexa, vexb); return ; } for (int i=0; i<path->final; i++) printf("%c\t", path->path[i].data); printf("\n"); } void SampleP(pGraph graph, int v, ElemType vexb, Path *path, bool *searched, bool *found) { searched[v] = true; Add(path, graph->vertices[v]); for (ArcNode *arc=graph->vertices[v].firstArc; arc!=NULL && *found==false; arc=arc->nextArc) { if (graph->vertices[arc->adj].data==vexb) { *found = true; Add(path, graph->vertices[arc->adj]); } else if (searched[arc->adj]==false) SampleP(graph, arc->adj, vexb, path, searched, found); } if (*found==false) Delete(path); } void Add(Path *path, VNode c) { path->path[path->final++] = c; } void Delete(Path *path) { path->final--; }
这篇关于【数据结构 | C语言】求图(邻接表)两个顶点之间的简单路径算法 C语言实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置