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>   #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语言怎么寻找无向图两点间的最短路径”的内容了，经过本文的学习后，相信大家对C语言怎么寻找无向图两点间的最短路径这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！