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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C语言求解无向图顶点之间的所有最短路径

    本文实例为大家分享了C语言求解无向图顶点之间的所有最短路径的具体代码,供大家参考,具体内容如下 思路一: DFS,遇到终点之后进行记录 辅助存储: std::vector<int> tempPath; std::vector<std::vector<int>> totalPath; 实现: //查找无向图的所有最短路径,直接dfs就可以解决了 //记录保存这里用 vector<vector<int>> 插入失败,重新搞一下 OK // 时间复杂度

  • C语言实现图的最短路径Floyd算法

    Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径. D代表顶点到顶点的最短路径权值和的矩阵. P代表对应顶点的最小路径的前驱矩阵. 以下程序在DEV C++中调试运行通过. #include <stdio.h> #define INFINITY 65535 typedef int VertexType; //顶点是字符型 typedef int EdgeType; //边是整型 typedef struct //图的邻接矩阵存储结构 { VertexType vexs[9]; /

  • C语言寻找无向图两点间的最短路径

    1.简介 无向图是图结构的一种.本次程序利用邻接表实现无向图,并且通过广度优先遍历找到两点之间的最短路径. 2.广度优先遍历 广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式.其中广度优先遍历配合上队列能够找到两点之间的最短路径,同时也能解决一些其他的问题(比如寻找迷宫的最短逃离路线).广度优先遍历寻找两点之间最短路径的操作分为以下几步: 1).首先定义起始点和终点src和dst.接着定义一个数组distance[ ],用于存放各点到src的距离.初始化时各点到src的距

  • JS实现深度优先搜索求解两点间最短路径

    本文实例为大家分享了JS实现深度优先搜索求解两点间最短路径的具体代码,供大家参考,具体内容如下 效果: 找出图里点到点最短路径,并打印轨迹 图片如下所示: 代码: const map = [ [0, 1, 1, 0, 1], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 0, 0], [1, 0, 1, 0, 0] ] function dfsManager(map, start, end){ var min = 9999, path = [], unv

  • 使用PostGIS完成两点间的河流轨迹及流经长度的计算(推荐)

    目录 基础准备工作 1.PostGIS 的安装 2.加载Post GIS扩展 3.河流矢量图层转成单线格式 4.河流矢量数据导入PostgreSQL数据库 5.河流数据拓扑处理 PG分析处理函数 1.函数编写 2.参数说明 3.内部调用函数说明 4.输出结果验证 基础准备工作 1.PostGIS 的安装 在安装PostGIS前首先必须安装PostgreSQL,然后再安装好的Stack Builder中选择安装PostGIS组件.具体安装步骤可参照PostGIS的安装与初步使用 2.加载Post

  • PHP根据两点间的经纬度计算距离

    这是一个不错的示例,直接贴代码,首先要知道纬度值.经度值 /** * @desc 根据两点间的经纬度计算距离 * @param float $lat 纬度值 * @param float $lng 经度值 */ function getDistance($lat1, $lng1, $lat2, $lng2) { $earthRadius = 6367000; //approximate radius of earth in meters /* Convert these degrees to r

  • java计算两点间的距离方法总结

    使用java自带的Point类 import java.awt.Point;//引用awt包下的Point类,此类的功能是表示 (x,y) 坐标空间中的位置的点 public class Distance { public static void main(String[] args) { Point p1 = new Point(5, 6);// 定义第一个点的坐标(5,6) Point p2 = new Point(7,8);// 定义第二个点的坐标(7,8) //定位坐标 System.o

  • opengl实现任意两点间画圆柱体

    本文实例为大家分享了opengl实现任意两点间画圆柱体的具体代码,供大家参考,具体内容如下 1.问题提出 两点间画线简单: glBegin(GL_LINES);  //注意是LINES不是LINE,这个错误一定要注意. glVertexf(x1, y1, z1); glVertexf(x2, y2, z2); glEnd(); 画线函数不会影响opengl的矩阵堆栈. 但是很多时候线条效果会比较差,比如我要做一个骨骼动画,关节点间的骨头用线条太难看,即使使用glLineWidth设置线宽,视觉效

  • matplotlib绘制两点间连线的几种方法实现

    目录 绘制方法<1> 绘制方法<2>使用pyplot绘制图像 绘制方法<3>使用axes类绘制图像 绘制方法<4>使用figure类绘制图像 为了找到matplotlib在两个点之间连线的方法真是费了好大功夫,本文主要介绍了 matplotlib绘制两点间连线的几种方法,具体如下 绘制方法 <1> 本文将通过最简单的模式拆解Matplotlib绘图的几个组成部分,将cover以下内容1. Create a dataset2. Create a c

  • python广度优先搜索得到两点间最短路径

    前言 之前一直写不出来,这周周日花了一下午终于弄懂了, 顺便放博客里,方便以后忘记了再看看. 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径. 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索: 比如下图: 从0结点开始搜索的话,一开始是0.将0加入队列中: 然后

  • java查找无向连通图中两点间所有路径的算法

    之前就这个问题发帖求教过,过了几天没看到回复就没再关心.后来自己设计了一个算法,在公司的项目中实践了一下,效果还可以,贴出来供大家参考. 算法要求: 1. 在一个无向连通图中求出两个给定点之间的所有路径: 2. 在所得路径上不能含有环路或重复的点: 算法思想描述: 1. 整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身): 2. 定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一个与起始节点直接

随机推荐