14.第14节课第7章图

罗泽兵 · 发表于 2024-4-15 09:18:35

图的遍地和树的遍地类似，图的遍地呢，也是图从图中某一顶点出发。按照某种方法，对图中的所有顶点访问，且仅访问一次图的便利算法呢，是求解图的连通性问题，拓扑排序和关键路径算法的基础。那么，我们图的便利呢？有深度优先搜索和广度优先搜索，那么我们来看一下。什么是图的深度优先搜索联通图的深度优先搜索便利呢？是从图的某个顶点出发。访问此顶点，

然后依次从v0的各个未被访问的零节点出发。深度优先搜索便利图，直到所有的和微有路径相同的顶点呢，都被访问到。那么比如说。w1，w2和w3均为v的临界点sg 1，sg 2和sg 3，分别为含顶点w1，w2和w3的子图。而我们进行深度优先遍历的时候呢，首先访问顶点v，然后呢，先访问w1，然后从该连接点呢。

若该连接点。w未被访问，则从它呢，触发深度优先，便利搜索便利，然后呢？访问。接下来呢，继续呢进行。这样的访问的这样一个方式，就是说先访问这样一个顶点，然后呢，深度优先进行便利，然后呢，访问完之后呢，

再回到顶点的这样一个部分呢？再进行这样一个访问遍历。再进行这样一个访问，也就是说它的过程是什么样子呢？比如说从图中某个顶点v出发，访问v找出刚访问过的顶点，第一个v访问的临界点访问该顶点。以该顶点为新顶点，重复此步骤，直到呢，刚访问过的顶点呢，没有被访问过的临界点访问，访问为止。返回前，一个访问过的仍有未被访问的临界点的顶点，

找出该顶点的下一个未被访问的临界点。那么，访问该顶点重复之前的步骤，直到所有的顶点呢，都被访问那么？访问级数那么如何知道？临界点是否被访问过了？从深度优先遍历搜索。连通图的过程呢？类似于树的先根便利，那么如何判断当前的零件w是否被访问呢？解决的办法呢？是为每一个顶点设立一个访问标志的w。接下来我们看一下这样一个dfs深度优先便利它的这样一个算法y的dfs graph f interview。visited v=true visited function。

v for w=first AD jx gw w=0 w呢等于next AD jx gv w。if感叹号。visit w那么这样一个判断呢？是反。dfs.gw对。未未被访问的临界点呢w调用dfs那么进行调用，那么就是说我们的。vex呢？vex v is的v。如果呢，它为零的话，那么这里取反了就为真，那么继续进行这样一个访问，这样一个深度优先访问，

那么这是我们的深度优先遍历它的这样一个算法。非联通途的深度优先便利呢？首先，将图中每个顶点的访问设置了设为boss，之后呢，搜索图中的每个顶点。如果未被访问，则以该景点呢为起始点进行深度优先搜索便利，否则呢，检查下一景点，那么我们来看一下这样一个深度优先便利。void for dfs traverse graph c graph g对图记录做深度优先，遍历for v=0 v小于g vexing。vx umber加加v。visit取的v=FALSE访问标志数组初始化。

for v=0 v小于g。vex number.加加v if v的v取反dfs gv，那么这里呢？就是图对图集呢？做深度优先便利。如果呢，我们的v的v=FALSE，那么取反了为真，那么进行这样一个dfs深度优先便利，那么对未访问的顶点呢，调用深度优先便利。那比如说。我们这个时候呢。访问标志啊，

那么都是f那么访问次数呢？首先是零那么设置为t那么a。然后呢，再访问c。那么第二个二呢？设置为t那么再访问。七那么访问h那么七呢？设置为t。那么，再访问d那么三呢？设置为t，那么接下来呢？再访问k。然后呢？八设置为t，

然后再访问f，那么五设置为t？那么这个时候呢，再访问e，那么就四设为t，接下来呢，再访问。b那么一设为t，那么最后呢？再访问g。六设为七，那么这是我们访问的这样一个次序，那么接下来我们再看一下广度优先搜索遍地图。那么，对于联通图来说，

从起点到v，起点v到起与各点呢，必定存在路径。其中呢，v1指向w1v指向w1v指向w2v指向w8的路径长度呢？为1v指向w7v指向w3v指向wv。它的路径长度呢？为二位置上w六位置上w4，它的路径长度呢？为三。从图中的某个顶点v出发并在访问此顶点后呢，依次访问v0的所有未被访问的临界点。之后按这些顶点，被访问的先后次序呢，依次访问它们的临界点，

直至图中所有和v有路径相通的顶点呢，都被访问到。此时若此时，图中上游顶点的未被访问则另选图中一个未被访问的顶点做起始点。重复这样一个过程，直到图中所有顶点都被访问为止，那么它是怎么样一个访问的方式呢？比如说从图中的这样一个某个顶点v0出发。访问v。然后呢，依次访问v0的各个未被访问的临界点，接下来呢，分别从这些零零节点出发，依次访问它的临界点。并使先被访问的顶点的零基点先与后被访问的零零点的零基点呢被访问。

那么重复这样一个。方法呢，直到图中所有已被访问的顶点的临界点呢，都被访问到，那么这是我们网度。优先搜索编辑的这样一个方法好了，我们看一下它的这样一个算法void bfs traverse graph f graph g interview。interval for v=0 v小于gve x number加加vv is vist的v=FALSE。initial q=q for v=0 v小于g点vex number加加v。if v.日期的v取反那么进行了进行访问，那么这是我们的广度优先遍历搜索广度优先搜索遍历的方式。好吧，我们来看一下这个部分。这里呢？

那么，这样一个方式呢？首先呢？visit v呢？等于force初始化访问标志，然后呢？滞空辅助队列q。然后呢，当v等于初始条件v=0 v呢等于小于gv后加加v。if v的取得v，当它为零的时候呢？那么取反为真，这个时候呢？执行if后面的访问语句，那么进行访问。

那么之后呢，再回到循环那么进行一个运行，那么这是我们bfs广度优先搜索便利的这样一个方法。我们看一下队列操作的代码段，为了取得v=true。vex为in QQ。v yo qmtq除法DQ qu对头元素初对比数为UFO rw，等于first adj vex gww不等于零。w=next AD gv exguw，那么这是我们的，当我们的w呢？那么最先等于for的adggu的gu的一个。实现了这样一个部分呢，那么并且呢，它的并且呢w不等于0w呢等于next。

AD gv GG uw呢这样一个实验的这样一个方式，if vx t的w那么当达当vx t的w=0的时候呢？为零的时候呢？取返回值那么执行后面的部分。visit取了w=true，visit取了w那么进行访问。in qqq w访问的顶点呢w入队列，那么这是我们队列操作的代码的这样一个部分。我们来看一下。广度优先，遍地搜索，遍地的队列操作序列，那么首先是w。未入队，然后呢？

未出队？然后呢？w1入队w2入队。w8入队，那么接下来呢？w1出队，然后呢？w7入队，那么w？二出队那么w3入队，接下来呢？w8出队。w5入队，然后呢？w7出队，

w6入队，然后呢？w3出队。那么w4入队，那么最后呢？w6出队和w8那么删除这样一个运行，这样一个部分。那么，这是我们广度优先。广度优先，搜索便利的这样一个方式，那么接下来呢？我们再看一下。图的连通性。求无效图的生成树或者生成森林，

那么什么是生成树呢？生成树是一个。极小连通子图，它含有图中的全部顶点，但只有n- 1条边，它的生成森林是什么呢？生成森林是若由n棵生成树组成。含全部顶点，但构成这些数的边是最小的，对有相同和无相同的，那么均可以使用这样一个方式。那么就说，对于我们联通图的生成，对于我们联通图的生成树来说，它含有图中的全部顶点。

但只含有n- 1条边，那么这里大家要注意，比如说对于一个连对于一个图来说，如对于一个无相图来说，如果它是连通的。并且呢。不构成回路，那么它的边呢？就有n- 1条边，那么这里呢？大家注意，对于一个连通图来说，如果呢？它不构成。如果它是连通不构成，

并且不它是它要不构成回路，并且是连通的，那么这个时候呢，它就有n- 1条边。那么，如果对连通图进行便利，得到是什么呢？一个极小连通指图，那么就是生成树，由深度优先得到的这样一个生成树呢？是深度优先生成树。由广度优先得到所有的生成树呢？为广度优先生成树，若对非点土土进行便利呢？得到的呢就是深层森林。

那么，我们来看一下这样一个生成树v0v1v2v3v4，它的生成树呢？那么，进行深度优先便利，那么就是。零三四二一这样一个生成树。那么，我们来看一下。广度优先，搜索便利了，那么就是零一三二四那么这样一个生成树。呃，我们再看一下这样一个图的深层森林。那么就是这样一个。

它有它的子图子图一子图二和子图三，那么它的生成森林呢？那么就是a。fcb.mjlde和gi HK，这是它的生存森林。那么图的生成树呢？和生成森林呢？那么是不唯一的，那么这里大家要注意图的生成树和生成森林呢？是不唯一的，那么就说图的生成树和生成森林呢？那么是不唯一的。好吧，我们看看一下求无线网的最小生成数。

那么，现实生活中的许多问题呢？都可以转化为图来解决，比如说如何以最小成本构造一个通讯网络，如何计算两地中最短路径。如何为复杂活动的各自任务呢？完成一个较优的顺序，那么这些呢都可以。转化为图来解决。包括我们的最小生成数，最短路径，拓扑排序和关键路径，这些算法那么求无线网的最小生成数呢？它的目标呢？是在网络的多个生成树中寻找一个各边全值之和最小的生成树。

如果说在一条带全的边中选取n- 1条边不构成回路，使全值之和最小。那么，典型用途呢？是在n个城市之间建立通讯网，则n个城市呢？input n减一条线路，但因为每条线路呢，都会有对应的经济成本，而n个城市呢，可能有二分之n减一条线n。安全n- 1条线路，那么如何选择n- 1条线路呢？是总费用最少，那么最小，

甚至说mst的，它的性质是这样一个部分。v是顶点级u是v的一个非空子集，若u0v0是一条最小生成，最小全值的边，其中的u0属于uvv 0属于。v-u那么则v0u0。b在最小生成树上，那么求最小生成树呢？有多种算法，那么最常用的是两种blue prim算法和克鲁斯凯尔算法。克鲁斯prime算法呢，是对顶点进行操作，而克鲁斯凯凯尔算法呢，对边进行操作。

prime算法呢？是顶点归，并与边数无关，适用于稠密网，克鲁斯卡尔算法的特点呢？是边归并，适用于求悉数网。p算法的基本思想呢，是在生成树的构造过程中，图中n个顶点呢，分出两个集合，以落在生成树上的顶点集u和未落在生成树上的顶点集。v-u则应在所有连通u中顶点和v-u中顶点的边中选择全值最小的边，那么我们来看一下它的这样一个过程。我们它的过程呢，

是比如说假设我们嗯v1呢是联通网。p1呢，是生成树上编的最小，生成树编的集合，那么最开始呢？u呢等于u0那么最下一个顶点顶点的这样一个部分，那么t呢是一个空一等于空集在所有的u属于u。v属于v-u的这样一个边uv中属于一中找到一条全值最小的边u0v0并入集合t1，同时v0呢并入u那么重复，这样一个操作呢？知道了u=v，那么这是这样一个操作的部分，那么我们来看一下。首先，我们是一个顶点a，

这个顶点a呢？我们找了这样一个顶点的，这样一个。实现了这样一个运用的，执行的使用，使用部分，那么这个时候呢，就是在与顶点。与顶点的与这个顶点a相连的，这其他顶点当中找到一条与这条与这个顶点。相连的。顶点这样一，这顶点它构它构成的边呢？它全值最小的边，那么我们找到14这条边就是与它顶相连的顶点是八。

那么这个时候呢，我们再在与顶点a和顶点e相连的这些顶点呢，所构成的边当中找一条全值最小的边。那么这个时候呢，我们找到的是八那么这个顶点呢是d。这个时候呢，我们再在这样一个与它顶点相连的边构相连的点构成的边当中呢，找一条全值最小的边。b这个这个时候呢，我们找到的是三那么找到的顶点呢，是c那么接下来按这个方法继续寻找，我们找到了是五那么找到的顶点呢，是b那么按这个方式继续寻找呢，我们找到是16找到这个顶点是g。那么最后找的这个顶点呢？

是f找的这个边呢？是21那么所得数？所得生成数全值之和了，那么是这样一个部分。那么，这是我们的。frame算法。prime算prime算法的这样一个方式。然后我们来看一下它的这样一个。方法它的方法呢，是设置一个辅助数组，对当前微减易集中的每个顶点记录和顶点及u中顶点相连接的代价最小的边。对于每个属于v-u的顶点VI，在辅助输入中呢，存在一个相应的分量close age i- 1，

它代号两个域，其中lowcost I low cost储存储该片的全。呃，并且呢？close age i-en oc cast=min cost uiuviu属于u，那么是最？这样一个权值最它是这样一个这样一个边当中最小权值最小的这样一个边就这样一个边。那么，它的存储方式呢？是draft vertex type a dg vax？where we are type no cost closed age max v TeX number，那么它是这样一个。结构体的这样一个部分。比如说我们有abcdefg，那么这样一个方式啊，

按照这样一个存储的形式呢来。查看我们的这样一个。要使用的边的。连接的运用情况，那么得到的呢？是我们。找到这样一个。编的这样一个运用的这样一个使用的这样一个情况部分，那么最后呢？得到了我们这样一个实现的寻找的运用方式，运用的运用的这样一个部分，那么prime算法的时间效率呢？是oon的平方。那么，接下来我们再看一下克鲁斯卡尔的基本思想考虑的问题的出发点呢？

是为使生成树上边的全值呢？的和达到最小，则以使生成树中每一条边的全值呢？尽可能的小。它的具体做法呢是？先构造一个只含n个顶点的子图。sg，然后从全值最小的边开始，若它的添加了，不使sg中产生回路，则在sg上呢，加上这条边那么这样进行重复操作，那么直到了加上n- 1条边为止。那么，它的过程是什么样的呢？

就是我们的这样一个算法呢？就是将我们的这样一个。每条每个首先呢，写出每个顶点，每个顶点呢。那么，找到我们这构造，就找到我们的这样一些顶点的，这找到我们这些顶点，然后呢，初始状态呢，就只有n个顶点而无边的非连通图t。图中每个顶点呢，自成一个连通分量在一，在这样一个边的集合中呢，

选择权值最小的。若该边依附的顶点落在其中，不同的连通分量上，也就说既就不构成我们不构成回路，则将此边呢加入到我们的。要找的边的集合当中，否则舍去此边寻找下一条全值最小的边那么重复，这样一个方法呢？那么直到其中的顶点呢？都在同一个连通分量上为止。那么，我们来看一下。我们首先呢，找到这些顶点一二三四五六，然后呢，

在这些边当中呢，找一条全值最小的边，并且呢，这条边呢，不使我们这些。使用运用的这样一个图当中呢，采用的构造的这样一个顶点的这样一个图当中呢，采用的这样一个图的这样一个运用运用当中呢，那么不不不，产生回路。那么，现在这个图呢？不产生回路，那么使得这个图呢？不产生回路，

那么说我们找到一条全图最小的边呢？使得这样一个选择图呢？不构成回路，我们可以呢？在原来在这个图当中呢？选择一条从。转这条权值最小的边是我们。采取了这样一个图当中呢，不构成回路，那么我们可以呢，选择这样一条一一呢，不使。可以那么七条全都最小的边，那么我们选择这条一这条边，那么接下来是有全值为二的这条边，

我们可以呢，选择全值为二的这条边。那么接下来呢，我们还有全职为三的这条边，我们选择了全职为三的这条边，那么接下来呢，我们还有全职为四的这条边，那么我们就选取全职为四的这条边。接下来，我们还有全值为五的这些边，那么这些边呢？有些边呢？会使我们的图呢？构成回路，那么我们选择一条呢？

不构成回路的这样一个边，那么就是这个为五的边。那么最后呢，我们就得到了。这样一个。联通这样一个联通的这样一个联通的这样一个联通的这样一个图，那么比如说全职。全职了，边上的全职了，最小的这样一个联通的这样一个图。那么，这样一个生成树的，这样一个情况。克鲁斯卡尔算法的实践效率呢，是o1 log二一，

那么我们来比较一下克鲁斯卡尔算法和prom算法。prime算法的时间复杂度呢，是on的平方，这里大家记住可可prime算法的时间复杂度呢，是on的平方。克鲁斯凯尔算法的时间复杂度呢，是o1 log 1，那么这里大家记住克鲁斯凯尔算法的时间复杂度，是o1 log 1。proe算法呢，适用于稠密图，那么就是说适用于边比较多的图。那么。克鲁斯凯尔算法呢，适用于稀疏图，

那么就是边比较少的图，那么大家记住prime算法呢，适用于稠密图，克鲁斯凯尔算法呢，适用于稀疏图。那么，接下来我们再看一下有效模块图的这样应用，部分假设以有效图呢？表示一个工程的施工图或者程序的数据流图。那么，这图中呢？不允许出现回路，那么检查图中是否存在回路的方法之一呢？是对有效图进行拓扑排序，那么什么是拓扑排序呢？

就是对有效图进行操作，按照有效图给出的次序关系呢？将图中顶点排成一个线性序列，对于有效图中没有限定次序关系的顶点，那么可以人为加上任意的次序关系。那么，由此所得顶点的线性序列呢？称为top有序序列啊，比如说对于有下列，有向图，那么可以得到top序列了。abcd或者a cbd，那么对于这样一个有向图呢？那么就不能得到它的有序。序列因为图中呢，

出现出现一个回路。

		自动登录	找回密码
密码			立即注册