本文共 6014 字,大约阅读时间需要 20 分钟。
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; } private Set<Integer> nodes; private Map<Integer, LinkedList<Integer>> links; private Map<Link, Weight> weights; nodes用于存储所有节点,不重复;links为邻接表;weights为边上的权值。1、两点间最短路径(dijkstra算法)
实现代码为:
public Path shortestPath(int a_node, int b_node)
{ //从a_node到其他节点的代价,有序排列 Map<Integer, Path> cost = new HashMap<Integer, Path>(); //sNodes初始为空 LinkedList<Integer> sNodes = new LinkedList<Integer>(); //qNodes初始为整个节点集 LinkedList<Integer> qNodes = new LinkedList<Integer>(); for (int node : nodes) { qNodes.add(node); cost.put(node, new Path(new Weight(Float.MAX_VALUE))); } cost.put(a_node, new Path(new Link(a_node, a_node), new Weight(0.0f))); //每次迭代qNodes集中被选中的节点 int uNode; while (!qNodes.isEmpty()) { uNode = extractMin(qNodes, cost); sNodes.add(uNode); if (uNode == b_node)//已经找到到b_node的最短路径 break; for (int vNode : adjNodes(uNode))//代表qNodes集合中的某一节点 { relax(cost, uNode, vNode); } } return cost.get(b_node); } 其中extractMin函数从qNodes集合中选取从源点出发代价最小的点。relax函数使用到了松弛(relaxation)技术。对于每个顶点v ∈ V,都设置一个属性d[v],用来描述从源点s到v的最短路径上权值的上界,称为最短路径估计(shortest-path estimate)。在松弛一条边(u,v)的过程中,要测试是否可以通过u,对迄今找到的到v的最短路径进行改进;如果可以,就更新。一次松弛操作可以减小最短路径估计的值。(摘自《算法导论》) 如果只要找出源点到特定点的最短路径,可以提前跳出循环,如代码中所示。2、两点间所有路径
实现代码如下:
public LinkedList<Path> allPath(int a_node, int b_node, Weight max)
{ LinkedList<Path> apath = new LinkedList<Path>(); int top_node; //即栈顶节点 int cur_node;//当前的临接节点 int next_node;//下一个入栈节点 //遍历过程中使用的栈 LinkedList<Integer> stack = new LinkedList<Integer>(); //标记节点是否在栈内,避免回路 Map<Integer, Integer> states = new HashMap<Integer, Integer>(); //记录栈中路径长度 Weight weight; for (int node : nodes) { states.put(node, 0);//0表示不在栈内 } //初始化变量 stack.add(a_node); weight = new Weight();//初始化为0 states.put(a_node, 1); cur_node = -1; //定义为第一个临接节点的前一个 while (!stack.isEmpty()) { top_node = stack.getLast(); weight = calWeight(stack); //路径是否超出最大权值 if (weight.compareTo(max) > 0) { cur_node = stack.removeLast(); states.put(cur_node, 0); continue; } //找到一条路径 if (top_node == b_node) { apath.add(genPath(stack, weight)); cur_node = stack.removeLast(); states.put(cur_node, 0); } else { next_node = nextNode(top_node, cur_node, states); if (next_node < Integer.MAX_VALUE) { stack.add(next_node); states.put(next_node, 1); cur_node = -1; //新节点入栈,要从头遍历它的所有临接节点 } else { cur_node = stack.removeLast(); states.put(cur_node, 0); } } } return apath; }找出所有路径采用的是遍历的方法,以“深度优先”算法为基础。从源点出发,先到源点的第一个邻接点N00,再到N00的第一个邻接点N10,再到N10的第一个邻接点N20...当遍历到目标点时表明找到一条路径。上述代码以核心数据结构为一个栈,主要步骤:
①源点先入栈,当栈顶为终点时,即找到一条路径;②栈顶元素N1出栈,新的栈顶元素为N2,从N2的所有邻接点中,以N1为起点,选取下一个N3入栈;
③为避免回路,已入栈元素要记录,选取新入栈顶点时应跳过已入栈的顶点
④当栈为空时,遍历完成。
这里我用了两个特殊的标记:一个值为-1,另一个值为Integer.MAX_VALUE。前者代表遍历某个顶点所有邻接点的开始位置,后者为结束位置。
详细的算法描述可以参考中国海洋大学熊建设、梁磊的论文《两点间所有路径的遍历算法》。
转载地址:http://zdlai.baihongyu.com/