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#include #include #defineERROR-1 #defineV_E_INFO1 #defineFIND1 #definePATH2 #defineMAX100 usingnamespacestd; 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&)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
{
queuemyQ;
intvalue[vertices_num];/用于存放各点到src的距离
inthead=0;
intoutput[10];
for(inti=0;imyS;
myS.push(dst);
while(find!=src)
{
for(intj=0;jget_value()]==-1)
{
value[a->get_value()]=value[head]+1;
myQ.push(a->get_value());
}
a=a->get_next();
}
}
cout<<"Error:nopathbetween"<
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。