C语言怎么寻找无向图两点间的最短路径
C语言怎么寻找无向图两点间的最短路径
这篇文章主要讲解了“C语言怎么寻找无向图两点间的最短路径”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“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>#defineERROR-1#defineV_E_INFO1#defineFIND1#definePATH2#defineMAX100usingnamespacestd;classArcNode{private:intvalue;ArcNode*next;public:ArcNode(int,ArcNode*=nullptr);voidset_next(ArcNode*);ArcNode*get_next()const;intget_value()const;voidset_value(int);};classList{private:intvalue;ArcNode*firstnode;public:List(int=0,ArcNode*=nullptr);~List();ArcNode*Pop();voidPush(int);intget_value()const;intis_exist(int)const;ArcNode*get_firstnode()const;voidset_value(int);voiddfs_find_path()const;voidset_firstnode(ArcNode*);voidprint()const;};classGraph{private:Listlist[MAX];intvertices_num;intedge_num;public:Graph(int,int,int[]);~Graph();intget_vertices_num()const;intget_edge_num()const;List*get_list(int);voidprint()const;voiddfs_print_path(int,int)const;voiddfs_find_path(int,int,int[],stack<int>&,int&)const;voiddfs(intsrc,intvisited[],int&count)const;voiddfs_print(int)const;voiddfs_non_recursive()const;intfind_shortest_path(int,int)const;voiddfs(int,int[])const;};#endif
BFS找寻最短路径代码：
intGraph::find_shortest_path(intsrc,intdst)const{queue<int>myQ;intvalue[vertices_num];/用于存放各点到src的距离inthead=0;intoutput[10];for(inti=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){intfind=dst;stack<int>myS;myS.push(dst);while(find!=src){for(intj=0;j<vertices_num;j++){if((list[j].is_exist(find)==1)&&(value[find]==value[j]+1)){myS.push(j);find=j;break;}}}intcount=myS.size();for(intj=0;j<count;j++){if(j==count-1)cout<<myS.top()<<endl;else{cout<<myS.top()<<"-";myS.pop();}}returnFIND;}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:nopathbetween"<<src<<"and"<<dst<<endl;returnERROR;}
感谢各位的阅读，以上就是“C语言怎么寻找无向图两点间的最短路径”的内容了，经过本文的学习后，相信大家对C语言怎么寻找无向图两点间的最短路径这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是恰卡编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！
