算法-计算无向图中两个节点之间所有的路径
1、深度优先遍历
1.1 深度优先遍历的定义
深度优先搜索（Depth_First Search）遍历类似于树的先根遍历，是树的先根遍历的推广。
假设给定图G，图中所有顶点未曾被访问过，则深度优先搜索可以从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。这是一个递归的过程。
1.2 图的深度优先遍历的过程
假设给定图G，设x 是当前被访问顶点， 在对x 做过访问标记后， 选择一条从x出发的未检测过的边(x，y)。若发现顶点y 已访问过，则重新选择另一条从x 出发的未检测过的边，否则若顶点y未被访问过，沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y 出发的所有路径，即访问完所有从y 出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x 出发的未检测过的边。上述过程直至从x 出发的所有边都已检测过为止。此时，若x 不是源点，则回溯到在x 之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G 是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
2、求两点间所有路径的算法
图1 连通图G
图2 G的邻接表存储结构
假设简单连通图如图1 所示，那么它的邻接表存储结构如图2 所示。假设我们要找出结点3到结点6的所有路径，那么，我们就设结点3为起点，结点6为终点。我们需要的存储结构有：一个保存路径的栈、一个保存已标记结点的数组，那么找到结点3到结点6的所有路径步骤如下：
（1）我们建立一个存储结点的栈结构，将起点3 入栈，将结点3 标记为入栈状态；
（2）从结点3 出发， 找到结点3 的第一个非入栈状态的邻结点1，将结点1 标记为入栈状态；
（3）从结点1 出发， 找到结点1 的第一个非入栈状态的邻结点0，将结点0 标记为入栈状态；
（4）从结点0 出发， 找到结点0 的第一个非入栈状态的邻结点2，将结点2 标记为入栈状态；
（5）从结点2 出发， 找到结点2 的第一个非入栈状态的邻结点5，将结点5 标记为入栈状态；
（6）从结点5 出发， 找到结点5 的第一个非入栈状态的邻结点6，将结点6 标记为入栈状态；
（7）栈顶结点6 是终点， 那么， 我们就找到了一条起点到终点的路径，输出这条路径；
（8）从栈顶弹出结点6，将6 标记为非入栈状态；
（9）现在栈顶结点为5， 结点5 没有除终点外的非入栈状态的结点，所以从栈顶将结点5 弹出；
（10）现在栈顶结点为2，结点2 除了刚出栈的结点5 之外，还有非入栈状态的结点6，那么我们将结点6 入栈；
（11）现在栈顶为结点6，即找到了第二条路径，输出整个栈，即为第二条路径；
（12）重复步骤2-11，就可以找到从起点3 到终点6 的所有路径；
（13）栈为空，算法结束。
#include <stack>
#include <iostream>using namespace std;
#define NUM 10
#define MAX_PATH 100
struct Node
{
int key;
int flag;
Node()
{
flag=0;
}
};
class Graph
{
public:
//stack<int> searchStack;
int resultPath[MAX_PATH][NUM];
int result[NUM+1];//将result设为NUM+1，主要是为了避免发生B->D->B的事情
Node headNode;//起始节点
Node endNode;//终止节点
stack<Node> tempStack;
int pathNum;
int nPos;
bool Mark[NUM];
public:
Graph()
{
//将矩阵中的元素置为空
for (int i=0;i<NUM;i++)
{
for (int j=0;j<MAX_PATH;j++)
{
resultPath[i][j]=0;
}
result[i]=0;
Mark[i]=false;
}
result[NUM]=0;
pathNum=0;
nPos=0;
}
void test()
{
//对应无向图的矩阵
int Matrix[NUM][NUM]={
{0,1,0,1,0}, //A
{1,0,1,0,1}, //B
{0,1,0,1,1}, //C
{1,0,1,0,0}, //D
{0,1,1,0,0} //E
};
//开始节点
headNode.key=1;
headNode.flag=1;
//结束节点
endNode.key=5;
FindAllPath(Matrix,headNode,endNode);
cout<<"顶点"<<headNode.key<<"到顶点"<<endNode.key<<"路径数目为："<<pathNum<<endl;
for (int i=0;i<pathNum;i++)
{
cout<<"第"<<i<<"条: ";
for(int j=0;j<NUM;j++)
{
if (resultPath[i][j]==0)
{
break;
}
cout<<resultPath[i][j]<<" ";
}
cout<<endl;
}
int i=0;
}
void FindAllPath(int Matrix[NUM][NUM],Node startNodeKey,Node endNodeKey)
{
result[nPos]=startNodeKey.key; //将当前元素放入结果集中
Mark[startNodeKey.key-1]=true; //将访问标记为已访问
nPos++; //结果集索引加1
while(nPos!=0)
{
int tempVal=result[nPos-1];//获取到最前面的元素
if (tempVal==endNodeKey.key) //若当前元素为目标节点
{
for (int j=0;j<nPos;j++)
{
resultPath[pathNum][j]=result[j]; //将结果集复制于最后的路径矩阵中
}
nPos--; //回溯至上一个节点
result[nPos]=0; //结果集对应索引置为空
pathNum++; //路径数目加1
Mark[endNodeKey.key-1]=false;
break;
}
while(startNodeKey.flag<NUM)//利用flag来指示每次的元素的索引
{
if (Matrix[tempVal-1][startNodeKey.flag]==1)
{
if (Mark[startNodeKey.flag]==false)//利用Mark来判断是否已经访问过该节点
{
Node tempNode;
tempNode.key=startNodeKey.flag+1;
FindAllPath(Matrix,tempNode,endNodeKey);//深度优先遍历算法，
}
}
startNodeKey.flag++;//索引值相应的加一
}
if (startNodeKey.flag==NUM)//如果已经是到最后的邻居，说明访问结束，
{ //将对应的值置为空
nPos--; //再次向上回溯
startNodeKey.flag=0; //将节点的索引置为空
result[nPos]=0; //将结果集中对应的索引置为空
Mark[startNodeKey.key-1]=false; //访问之后标记为未访问。因为下面的元素已经访问结束，便于下次的访问
break;
}
}
}
};
int main()
{
Graph G;
G.test();
return 0;
}