图的遍历拓扑排序最短路径算法

图的遍历、拓扑排序、最短路径算法图的遍历定义图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：①在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。②在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。③在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。④在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。分类图的遍历可分为四类：遍历完所有的边而不能有重复，即所谓“一笔画问题”或“欧拉路径”；遍历完所有的顶点而没有重复，即所谓“哈密尔顿问题”。遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密尔顿图的性质。图的遍历图的遍历有两种遍历方式：深度优先遍历(depth-firstsearch)和广度优先遍历(breadth-firstsearch)。1.深度优先遍历基本思想：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。如下图中的一个无向图其深度优先遍历得到的序列为：0-1-3-7-4-2-5-62.广度优先遍历基本思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。如上面图中其广度优先遍历得到的序列为：0-1-2-3-4-5-6-7算法图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。深度优先搜索法深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Booleanvisited[MAX_VERTEX_NUM];//访问标志数组Status(*VisitFunc)(intv);//VisitFunc是访问函数，对图的每个顶点调用该函数voidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}voidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE;VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。//若w是v的最后一个邻接点，则返回空（0）。if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w调用DFS}拓扑排序对一个有向无环图(DirectedAcyclicGraph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopologicalOrder)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。[1]执行步骤由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。(1)选择一个入度为0的顶点并输出之；(2)从网中删除此顶点及所有出边。循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。在计算机语言中的应用拓扑序列Pascal代码（无优化）?12345678910111213programTopSort;varmap,link:array[1..100,1..100]ofinteger;v,pnt:array[1..100]ofinteger;n,m,a,b,i,j,k:integer;beginfillchar(map,sizeof(map),0);fillchar(link,sizeof(link),0);fillchar(v,sizeof(v),0);readln(n,m);fori:=1tomdobeginreadln(a,b);map[a,b]:=1;141516171819202122232425262728293031v[b]:=v[b]+1;end;i:=0;link:=map;while(in)dobeginj:=1;while(v[j]0)doinc(j);v[j]:=-1;fork:=1tondoiflink[j,k]=1thenbegindec(v[k]);link[j,k]:=0;end;inc(i);pnt[i]:=j;end;fori:=1tondoln(pnt[i]);end.拓扑序列C++（STL）核心代码这里的代码可以参考这本书[3]，这里是我自己敲的代码，用了容器，感觉能看明白点。?123456789101112131415161718queueintq;//priority_queueint,vectorint,greaterintq;//优先队列的话，会按照数值大小有顺序的输出//此处为了理解，暂时就用简单队列inttopo(){for(inti=1;i=n;i++){if(indegree[i]==0){q.push(i);}}inttemp;while(!q.empty()){temp=q.front();//如果是优先队列，这里可以是top()192021222324252627282930printf(%d-,temp);q.pop();for(inti=1;i=n;i++)//遍历从temp出发的每一条边，入度--{if(map[temp][i]){indegree[i]--;if(indegree[i]==0)q.push(i);}}}}拓扑序列Pascal代码（邻接表+队列优化）?12345678910111213141516171819202122232425programtopsort;typenode=^link;link=recordprocedureaddd(x,y:longint);varp:node;beginnew(p);p^.g:=y;p^.next:=nd[x];nd[x]:=p;inc(ru[y]);end;beginreadln(n,m);fora:=1tomdobeginreadln(x,y);addd(x,y);end;fora:=1tondoifru[a]=0thenbegininc(stk);stack[stk]:=a;2627282930313233343536373839404142434445end;be:=0;repeatinc(be);x:=stack[be];p:=nd[x];write(x,'');whilepnildobegindec(ru[p^.g]);ifru[p^.g]=0thenbegininc(stk);stack[stk]:=p^.g;end;p:=p^.next;end;untilbe=stk;readln;end.这里主要是将入度为零的点加入队列stack，直接在队列内扩展即可，效率为O(n+m)典型实现算法：Kahn算法：摘一段维基百科上关于Kahn算法的伪码描述：L←EmptylistthatwillcontainthesortedelementsS←SetofallnodeswithnoincomingedgeswhileSisnon-emptydoremoveanodenfromSinsertnintoLforeachnodemwithanedgeefromntomdoremoveedgeefromthegraphifmhasnootherincomingedgestheninsertmintoSifgraphhasedgesthenreturnerror(graphhasatleastonecycle)elsereturnL(atopologicallysortedorder)不难看出该算法的实现十分直观，关键在于需要维护一个入度为0的顶点的集合：每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的List中。紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点…………当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List中的顺序就是对图进行拓扑排序的结果。基于DFS的拓扑排序：除了使用上面直观的Kahn算法之外，还能够借助深度优先遍历来实现拓扑排序。这个时候需要使用到栈结构来记录拓扑排序的结果。同样摘录一段维基百科上的伪码：L←EmptylistthatwillcontainthesortednodesS←SetofallnodeswithnooutgoingedgesforeachnodeninSdovisit(n)functionvisit(noden)ifnhasnotbeenvisitedyetthenmarknasvisitedforeachnodemwithanedgefrommtondovisit(m)addntoLDFS的实现更加简单直观，使用递归实现。利用DFS实现拓扑排序，实际上只需要添加一行代码，即上面伪码中的最后一行：addntoL。需要注意的是，将顶点添加到结果List中的时机是在visit方法即将退出之时。这个算法的实现非常简单，但是要理解的话就相对复杂一点。关键在于为什么在visit方法的最后将该顶点添加到一个集合中，就能保证这个集合就是拓扑排序的结果呢？因为添加顶点到集合中的时机是在dfs方法即将退出之时，而dfs方法本身是个递归方法，只要当前顶点还存在边指向其它任何顶点，它就会递归调用dfs方法，而不会退出。因此，退出dfs方法，意味着当前顶点没有指向其它顶点的边了，即当前顶点是一条路径上的最后一个顶点。彻底弄懂最短路径问题只想说：温故而知新，可以为师矣。我大二的《数据结构》是由申老师讲的，那时候不怎么明白，估计太理论化了(ps：或许是因为我睡觉了)；今天把老王的2011年课件又看了一遍，给大二的孩子们