DFS和BFS用来干什么

DFS和BFS用来干什么？连通性拓扑排序关键路径连通分量(Connectedcomponent)当无向图为非连通图时,从图中某一顶点出发,利用DFS或BFS不可能遍历到图中的所有顶点,只能访问到该顶点所在的极大连通子图(连通分量)的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。图的连通性问题求连通分量的算法需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。ACDEIBFOGHJNMLK非连通无向图AHKCDEIBFOGJNML非连通图的连通分量最小生成树(MinimumCostSpanningTree)使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。构造最小生成树的准则必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。MST性质假设N=(V,{E}）是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中uU,vV-U,则必存在一棵包含边(u,v)的最小生成树。uvV-UUu’v’普里姆(Prim)算法普里姆算法的基本思想：从连通网络N=(V,{E})中的某一顶点u0出发,U={u0}。选择与u0关联的具有最小权值的边(u0,v0),将其顶点v0加入到生成树顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把顶点加入v到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。采用邻接矩阵作为图的存储表示。510046132原图(a)(b)(c)(d)(e)(f)22225046121025141612350461321025255046132102225504613210125046132281025142422161812克鲁斯卡尔(Kruskal)算法算法思想：从n个孤立顶点出发，顺次加入n-1条边。假设连通网N=(V,{E}),令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入，否则舍去该边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。算法时间复杂度O(eloge),适用于稀疏网。有向无环图(DAG)及其应用定义：一个无环的有向图称为有向无环图。有向无环图是描述含有公共子式的表达式以及一项工程或系统进行过程的有效工具。用顶点表示活动的网络(AOV网络)计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8课程代号课程名称先修课程学生课程学习工程图C8C3C5C4C9C6C7C1C2可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边Vi,Vj表示活动Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中不能出现有向回路,即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2拓扑排序的方法①输入AOV网络。令n为顶点个数。②在AOV网络中选一个没有直接前驱的顶点,并输出之;③从图中删去该顶点,同时删去所有它发出的有向边;④重复以上②、③步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。拓扑排序的过程C0C1C2C3C4C5(a)有向无环图C2C5C1C0C3(b)输出顶点C4C4C1C2C5C3(c)输出顶点C0C0C2C5C1C3(d)输出顶点C3C1C2C5(e)输出顶点C2C5C1(f)输出顶点C1C5(g)输出顶点C5最后得到的拓扑有序序列为C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。(即,得到了顶点集的一个全序关系）(h)拓扑排序完成AOV网络及其邻接表表示C0C1C2C3C4C5C0C1C2C3^C4C5^012345indegreedataadj1301031destlink3051500150在邻接表中增设一个数组indegree[]，记录各顶点入度。。入度为零的顶点即无前驱顶点。在输入数据前,顶点表VexList[]和入度数组indegree[]全部初始化。在输入数据时,每输入一条边j,k,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息：EdgeNode*p=newEdgeNode;p-dest=k;//建立边结点p-link=G.VexList[j].firstAdj;VexList[j].firstAdj=p;//链入顶点j的边链表的前端indegree[k]++;//顶点k入度加一在算法中,使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。拓扑排序算法可描述如下：建立入度为零的顶点栈;当入度为零的顶点栈不空时,重复执行从顶点栈中退出一个顶点,并输出之;从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。最短路径(ShortestPath)最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小？问题解法:边上权值非负情形的单源最短路径问题—Dijkstra算法边上权值为任意值的单源最短路径问题—Bellman和Ford算法所有顶点之间的最短路径—Floyd算法边上权值非负情形的单源最短路径问题问题的提法：给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明Dijkstra逐步求解的过程10432101003050206010源点终点最短路径路径长度v0v1(v0,v1)10v2(v0,v3,v2)50v3(v0,v3)30v4(v0,v3,v2,v4)60vV-SS:已求得的最短路径的终点集vjvk下一条最短路径（设其终点为vj),或者是弧(v,vj),或者是从v出发，中间只经过S中的顶点而最后到达vj的路径。…调整：每确定一个次短最短路径终点Vj，1.将其并入S集;2.调整V-S中其余顶点vk的“当前找到的从源点v到终点vk的最短路径的长度D[k]”:D[k]←Min{D[k],D[j]+arcs[j][k]}//开始主循环每次求得v0到某个v顶点的最短路径，并加v到S集。for(i=1;iG.vexnum;++i){//其余G.vexnum-1个顶点min=INFINITY;//当前所知离v0顶点最近距离for(w=0;wG.vexnum;++w)if(!final[w])//wV-Sif(D[w]min){v=w;min=D[w];}final[v]=TRUE;//v并入S集for(w=0;wG.vexnum;++w)//更新当前最短路径及距离if(!final[w]&&(min+G.arcs[v][w]D[w])){D[w]=min+G.arcs[v][w];P[w]=P[v];P[w][w]=TRUE;//P[w]=P[v]＋P[w]}//if}//for}算法7.15时间复杂度:O(n2)作业：习题集7.22(page49)课后阅读：Floyd算法（教材7.6.2)作业10