C语言寻找无向图两点间的最短路径
1.简介
无向图是图结构的一种。本次程序利用邻接表实现无向图,并且通过广度优先遍历找到两点之间的最短路径。
2.广度优先遍历
广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式。其中广度优先遍历配合上队列能够找到两点之间的最短路径,同时也能解决一些其他的问题(比如寻找迷宫的最短逃离路线)。广度优先遍历寻找两点之间最短路径的操作分为以下几步:
1).首先定义起始点和终点src和dst。接着定义一个数组distance[ ],用于存放各点到src的距离。初始化时各点到src的距离是INF(表示正无穷。这里可自行定义,作用是表示还未得到该结点到src的距离),而distance[src] = 0。然后将src放入队列。
2).取出队列的第一个结点(一开始队列只有src,这里就是取出src)放在变量top中;
3).获得该结点的所有邻接结点,并且判断distance[ ]数组中各个邻接结点是否为INF。如果是说明还没有访问过该结点则将distance[ ]相应的位置设定为distance[top] + 1。如果不为INF,则表示之前已经访问过了,因此跳过。
4).重复2-3步直到top变量等于dst为止。或者一直到队列为空,这种情况下说明两点间不存在路径。
总结起来就是将结点从src开始按顺序放进队列中,而已经放进过队列的结点会被标识,因此不会重复放进队列,直到找到dst为止。这种方法得到的路径一定时最短路劲。
3.输出最短路径
上面使用广度优先遍历找到的是两点之间最短路径的长度,并且存储在了distance[dst]中,而如果要输出这条最短路径有不同的方法。本人这里使用的方法是先将dst压入栈中,然后通过遍历dst的邻接结点中有哪一个结点在distance数组中的值是distance[dst] - 1,找到后压入栈中。接着继续寻找再前一个结点,同样压入栈中。循环该操作最后找到src,然后将栈中的元素依次pop出来。因为栈先进后出的性质,便能够得到该条路径。
4.代码实现
具体的代码如下
#ifndef _GRAPH_H #define _GRAPH_H #include <stack> #include <iostream> #include <queue> #define ERROR -1 #define V_E_INFO 1 #define FIND 1 #define PATH 2 #define MAX 100 using namespace std; class ArcNode { private: int value; ArcNode *next; public: ArcNode(int , ArcNode * = nullptr); void set_next(ArcNode *); ArcNode *get_next() const; int get_value() const; void set_value(int); }; class List { private: int value; ArcNode *firstnode; public: List(int = 0,ArcNode * = nullptr); ~List(); ArcNode *Pop(); void Push(int); int get_value() const; int is_exist(int) const; ArcNode *get_firstnode() const; void set_value(int); void dfs_find_path() const; void set_firstnode(ArcNode *); void print() const; }; class Graph { private: List list[MAX]; int vertices_num; int edge_num; public: Graph(int,int,int []); ~Graph(); int get_vertices_num() const; int get_edge_num() const; List *get_list(int); void print() const; void dfs_print_path(int,int) const; void dfs_find_path(int,int,int [],stack<int> & ,int &) const; void dfs(int src,int visited[],int &count) const; void dfs_print(int) const; void dfs_non_recursive() const; int find_shortest_path(int,int) const; void dfs(int,int []) const; }; #endif
BFS找寻最短路径代码:
int Graph::find_shortest_path(int src,int dst) const { queue<int> myQ; int value[vertices_num];/用于存放各点到src的距离 int head = 0; int output[10]; for(int i = 0;i < vertices_num;i++) { value[i] = -1;//-1表示还没有访问过该结点 } value[src] = 0; myQ.push(src); while(myQ.size()) { head = myQ.front(); myQ.pop(); if(head == dst) { int find = dst; stack<int> myS; myS.push(dst); while(find != src) { for(int j = 0; j < vertices_num; j++) { if((list[j].is_exist(find) == 1) && (value[find] == value[j] + 1)) { myS.push(j); find = j; break; } } } int count = myS.size(); for(int j = 0;j < count;j++) { if(j == count - 1) cout << myS.top() << endl; else { cout << myS.top() << "-"; myS.pop(); } } return FIND; } ArcNode *a = list[head].get_firstnode(); while( a != nullptr) { if(value[a -> get_value()] == -1) { value[a -> get_value()] = value[head] + 1; myQ.push(a -> get_value()); } a = a -> get_next(); } } cout << "Error: no path between " << src << " and " << dst << endl; return ERROR; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04