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#include #include #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 &) 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 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 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语言中如何寻找无向图两点间的最短路径”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
本文标题：C语言中如何寻找无向图两点间的最短路径
文章链接：http://scyanting.com/article/jdiisg.html
