C++计算图任意两点间的所有路径

基于连通图,邻接矩阵实现的图,非递归实现。

算法思想:

设置两个标志位,①该顶点是否入栈,②与该顶点相邻的顶点是否已经访问。

A 将始点标志位①置1,将其入栈

B 查看栈顶节点V在图中,有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点

C 如果有,则将找到的这个节点入栈,这个顶点的标志位①置1,V的对应的此顶点的标志位②置1

D 如果没有,V出栈,并且将与v相邻的全部结点设为未访问,即全部的标志位②置0

E 当栈顶元素为终点时,设置终点没有被访问过,即①置0,打印栈中元素,弹出栈顶节点

F 重复执行B – E,直到栈中元素为空

先举一个例子吧

假设简单连通图如图1所示。假设我们要找出结点3到结点6的所有路径,那么,我们就设结点3为起点,结点6为终点。找到结点3到结点6的所有路径步骤如下:
1、 我们建立一个存储结点的栈结构,将起点3入栈,将结点3标记为入栈状态;
2、 从结点3出发,找到结点3的第一个非入栈没有访问过的邻结点1,将结点1标记为入栈状态,并且将3到1标记为已访问;
3、 从结点1出发,找到结点1的第一个非入栈没有访问过的邻结点0,将结点0标记为入栈状态,并且将1到0标记为已访问;
4、 从结点0出发,找到结点0的第一个非入栈没有访问过的邻结点2,将结点2标记为入栈状态,并且将0到2标记为已访问;
5、 从结点2出发,找到结点2的第一个非入栈没有访问过的邻结点5,将结点5标记为入栈状态,并且将2到5标记为已访问;
6、 从结点5出发,找到结点5的第一个非入栈没有访问过的邻结点6,将结点6标记为入栈状态,并且将5到6标记为已访问;
7、 栈顶结点6是终点,那么,我们就找到了一条起点到终点的路径,输出这条路径;
8、 从栈顶弹出结点6,将6标记为非入栈状态;
9、 现在栈顶结点为5,结点5没有非入栈并且非访问的结点,所以从栈顶将结点5弹出,并且将5到6标记为未访问;
10、        现在栈顶结点为2,结点2的相邻节点5已访问,6满足非入栈,非访问,那么我们将结点6入栈;
11、        现在栈顶为结点6,即找到了第二条路径,输出整个栈,即为第二条路径
12、        重复步骤8-11,就可以找到从起点3到终点6的所有路径;
13、        栈为空,算法结束。

下面讲一下C++代码实现

图类,基于邻接矩阵,不详细的写了 ==

class Graph
{
private:
 CArray<DataType,DataType> Vertices;
 int Edge[MaxVertices][MaxVertices];
 int numOfEdges;
public:
 Graph();
 ~Graph();
 void InsertVertex(DataType Vertex);
 void InsertEdge(int v1,int v2,int weight);
 int GetWeight(int i,int j);
 int GetVertices();
 DataType GetValue(int i);
};

首先自己写一个简单的“栈类”,由于新增了些方法所以不完全叫栈

template<class T>
class Stack
{
private:
 int m_size;
 int m_maxsize;
 T* data;
public:
 Stack();
 ~Stack();
 void push(T data); //压栈
 T pop(); //出栈,并返回弹出的元素
 T peek(); //查看栈顶元素
 bool isEmpty(); //判断是否空
 int getSize(); //得到栈的中元素个数
 T* getPath(); //返回栈中所有元素
};
template<class T>
Stack<T>::Stack()
{
 m_size=0;
 m_maxsize=100;
 data=new T[m_maxsize];
}
template<class T>
Stack<T>::~Stack()
{
 delete []data;
}
template<class T>
T Stack<T>::pop()
{
 m_size--;
 return data[m_size];
} 

template<class T>
void Stack<T>::push(T d)
{
 if (m_size==m_maxsize)
 {
  m_maxsize=2*m_maxsize;
  T* new_data=new T[m_maxsize];
  for (int i=0;i<m_size;i++)
  {
   new_data[i]=data[i];
  }
  delete []data;
  data=new_data;
 }
 data[m_size]=d;
 m_size++;
} 

template<class T>
T Stack<T>::peek()
{
 return data[m_size-1];
} 

template<class T>
bool Stack<T>::isEmpty()
{
 if (m_size==0)
 {
  return TRUE;
 }
 else
 {
  return FALSE;
 }
} 

template<class T>
T* Stack<T>::getPath()
{
 T* path=new T[m_size];
 for (int i=0;i<m_size;i++)
 {
  path[i]=data[i];
 }
 return path;
} 

template<class T>
int Stack<T>::getSize()
{
 return m_size;
}

Vertex类,便于遍历全部的结点

class CVertex
{
private:
 int m_num;//保存与该顶点相邻的顶点个数
 int *m_nei; //与该顶点相邻的顶点序号
 int *m_flag; //与该顶点相邻的顶点是否访问过
 bool isin; //该顶点是否入栈
public:
 CVertex();
 void Initialize(int num,int a[]);
 int getOne(); //得到一个与该顶点相邻的顶点
 void resetFlag(); //与该顶点相邻的顶点全被标记为未访问
 void setIsin(bool);//标记该顶点是否入栈
 bool isIn(); //判断该顶点是否入栈
 void Reset();//将isin和所有flag置0
 ~CVertex(); 

};
CVertex::CVertex()
{
 m_num=SIZE;
 m_nei=new int[m_num];
 m_flag=new int[m_num];
 isin=false;
 for (int i=0;i<m_num;i++)
 {
  m_flag[i]=0;
 } 

}
void CVertex::Initialize(int num,int a[])
{
 m_num=num;
 for (int i=0;i<m_num;i++)
 {
  m_nei[i]=a[i];
 }
}
CVertex::~CVertex()
{
 delete []m_nei;
 delete []m_flag;
}
int CVertex::getOne()
{
 int i=0;
 for (i=0;i<m_num;i++)
 {
  if (m_flag[i]==0) //判断是否访问过
  {
   m_flag[i]=1; //表示这个顶点已经被访问,并将其返回
   return m_nei[i];
  }
 }
 return -1; //所有顶点都已访问过则返回-1
}
void CVertex::resetFlag()
{
 for (int i=0;i<m_num;i++)
 {
  m_flag[i]=0;
 }
}
void CVertex::setIsin(bool a)
{
 isin=a;
}
bool CVertex::isIn()
{
 return isin;
}
void CVertex::Reset()
{
 for (int i=0;i<m_num;i++)
 {
  m_flag[i]=0;
 }
 isin=false;
}

初始化顶点类

int a[SIZE],num;
for ( i=0;i<SIZE;i++)
{
 num=0;
 for (int j=0;j<SIZE;j++)
 { 

  if (m_graph.Edge[i][j]!=MaxWeight&&i!=j)
  {
   a[num]=j;
   num++;
  } 

 }
 vertex[i].Initialize(num,a);

算法实现(由于是基于MFC实现,所有下边的代码不可以直接使用)

stack.push(selection1); //将起点压栈
vertex[selection1].setIsin(true); //标记为已入栈
int path_num=0;
while (!stack.isEmpty()) //判断栈是否空
{ 

 int flag=vertex[stack.peek()].getOne(); //得到相邻的顶点
 if (flag==-1) //如果相邻顶点全部访问过
 {
  int pop=stack.pop(); //栈弹出一个元素
  vertex[pop].resetFlag(); //该顶点相邻的顶点标记为未访问
  vertex[pop].setIsin(false); //该顶点标记为未入栈
  continue; //取栈顶的相邻节点
 }
 if (vertex[flag].isIn()) //若已经在栈中,取下一个顶点
 {
  continue;
 }
 if (stack.getSize()>maxver-1) //判断栈中个数是否超过了用户要求的 ,这里是限制了一条路径节点的最大个数
 {
  int pop=stack.pop();
  vertex[pop].resetFlag();
  vertex[pop].setIsin(false);
  continue;
 }
 stack.push(flag); //将该顶点入栈 

 vertex[flag].setIsin(true); //记为已入栈 

 if (stack.peek()==selection2) //如果栈顶已经为所求,将此路径记录
 {
  int *path=stack.getPath();
   //保存路径的代码省略
  int pop=stack.pop(); //将其弹出,继续探索
   vertex[pop].setIsin(false); //清空入栈的标志位
 } 

}

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

(0)

相关推荐

  • C++ 中boost::share_ptr智能指针的使用方法

    C++ 中boost::share_ptr智能指针的使用方法 最近项目中使用boost库的智能指针,感觉智能指针还是蛮强大的,在此贴出自己学习过程中编写的测试代码,以供其他想了解boost智能指针的朋友参考,有讲得不正确之处欢迎指出讨论.当然,使用boost智能指针首先要编译boost库,具体方法可以网上查询,在此不再赘述. 智能指针能够使C++的开发简单化,主要是它能够自动管理内存的释放,而且能够做更多的事情,即使用智能指针,则可以再代码中new了之后不用delete,智能指针自己会帮助你管理

  • C++中构造函数的参数缺省的详解

    C++中构造函数的参数缺省的详解 前言: 构造函数中参数的值既可以通过实参传递,也可以指定为某些默认值,即如果用户不指定实参值,编译系统就使形参取默认值.在构造函数中也可以采用这样的方法来实现初始化. #include <iostream> using namespace std; class A { public : A(int aa=0,int bb=00); //在声明构造函数时指定默认参数 int volume( ); int a; int b; }; int main( ) { A

  • C++ 中Vector常用基本操作

    标准库vector类型是C++中使用较多的一种类模板,vector类型相当于一种动态的容器,在vector中主要有一些基本的操作,下面通过本文给大家介绍,具体内容如下所示: (1)头文件#include<vector>. (2)创建vector对象,vector<int> vec; (3)尾部插入数字:vec.push_back(a); (4)使用下标访问元素,cout<<vec[0]<<endl;记住下标是从0开始的. (5)使用迭代器访问元素. vect

  • C++ 中构造函数的实例详解

    C++ 中构造函数的实例详解 c++构造函数的知识在各种c++教材上已有介绍,不过初学者往往不太注意观察和总结其中各种构造函数的特点和用法,故在此我根据自己的c++编程经验总结了一下c++中各种构造函数的特点,并附上例子,希望对初学者有所帮助. 1. 构造函数是干什么的 class Counter { public: // 类Counter的构造函数 // 特点:以类名作为函数名,无返回类型 Counter() { m_value = 0; } private: // 数据成员 int m_va

  • C++中函数指针详解及代码分享

    函数指针 函数存放在内存的代码区域内,它们同样有地址.如果我们有一个int test(int a)的函数,那么,它的地址就是函数的名字,如同数组的名字就是数组的起始地址. 1.函数指针的定义方式:data_types (*func_pointer)( data_types arg1, data_types arg2, ...,data_types argn); c语言函数指针的定义形式:返回类型 (*函数指针名称)(参数类型,参数类型,参数类型,-); c++函数指针的定义形式:返回类型 (类名

  • C++中strstr函数的实现方法总结

    C++中strstr函数的实现方法总结 函数说明: 包含文件:string.h 函数名: strstr 函数原型:extern char *strstr(char *str1, char *str2); 功能:从字符串str1中查找是否有字符串str2, 如果有,从str1中的str2位置起,返回str1的指针,如果没有,返回null. 返回值:返回该位置的指针,如找不到,返回空指针. 方法一: #include <iostream> #include <assert.h> usi

  • C++计算图任意两点间的所有路径

    基于连通图,邻接矩阵实现的图,非递归实现. 算法思想: 设置两个标志位,①该顶点是否入栈,②与该顶点相邻的顶点是否已经访问. A 将始点标志位①置1,将其入栈 B 查看栈顶节点V在图中,有没有可以到达.且没有入栈.且没有从这个节点V出发访问过的节点 C 如果有,则将找到的这个节点入栈,这个顶点的标志位①置1,V的对应的此顶点的标志位②置1 D 如果没有,V出栈,并且将与v相邻的全部结点设为未访问,即全部的标志位②置0 E 当栈顶元素为终点时,设置终点没有被访问过,即①置0,打印栈中元素,弹出栈顶

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

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

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

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

  • java计算图两点之间的所有路径

    本文实例为大家分享了java计算图两点之间的所有路径的具体代码,供大家参考,具体内容如下 1.给定图如下: 2.求0到3之间可达的所有路径 这里问题就是关于搜索遍历的问题,但其中需要注意到不能产生回路或环. 算法描述如下: top_node:当前栈顶元素 adjvex_node;当前top_node已经访问的邻接点 next_node:即将访问的元素(top_node的第adjvex_node个邻接点所对应的元素) 找出所有路径采用的是遍历的方法,以"深度优先"算法为基础.从源点出发,

  • 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

  • Python计算任意多边形间的重叠面积的示例代码

    目录 简介 1. shapely工具箱 2. 程序 简介 跟某人讨论一个排样问题. 他说,算法搜索速度很慢,每两个物体间的重叠面积计算时间若按1s来算,300个物体需要计算将近9万次. 我说,这用计算机视觉难道不是几句话解决的嘛! (小小的嘚瑟一把,虽然做了这么久的CV,一直觉得自己一无所成,但是没想到默默的就能解决别人的问题了哈哈哈~~) 本文档目的为: 给定的数据为多边形的各个顶点,为N*2的矩阵,N 为多边形的顶点个数,计算任意两个多边形重叠面积计算的工具介绍及程序. 注意,并不涉及IOU

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

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

随机推荐