数据结构教程第6章图.ppt

第六章 图,本章的主要内容是:,图的基本概念图的存储结构图的遍历最小生成树最短路径AOV网与拓扑排序AOE网与关键路径,图论发展史,图论是组合数学的一个分支，也是近几十年来最活跃的数学分支之一.到目前为止，它已有二百六十多年的发展历史.图论的发展历史大体可以分为三个阶段：第一阶段是图论的萌芽阶段，它从十八世纪中叶到十九世纪中叶.这时，图论的多数问题是围绕游戏而产生的，其代表性的工作就是Knigsberg七桥问题.1736年L.Euler发表了他著名的Knigsberg七桥问题的论文，这是图论的第一篇文章.,第二阶段从十九世纪中叶到二十世纪中叶.在此阶段，图论问题大量出现.如著名的四色问题、Hamilton问题以及图的可平面问题等.在第二个阶段还应该特别提到Cayley把树应用于化学领域，Kirchhoff用树去研究电网络的分析问题.在漫长的300年中，图论几乎停留在数学游戏阶段.虽然这阶段里21岁的G.Kirchhoff在1847年从电网络问题，A.Cayley在1857年从计算有机化学的同分异构等不止一次地建立起图论的基本概念，但是直到1936年D.Knig发表的经典著作才有了图论的第一本专著.,二十世纪中叶以后是图论发展的第三阶段，即图论的应用阶段.由于生产管理、军事、交通运输、计算机网络、计算机科学、数字通讯、线性规划、运筹学等方面提出的实际问题的需要，特别是许多离散性问题的出现、刺激和推动，以及由于有了大型电子计算机，而使大规模问题的求解成为可能，图论及其应用的研究得到了飞速的发展.这个阶段的开创性工作是以Ford和Fulkerson建立的网络流理论为代表的.图论与其它学科的相互渗透，以及图论在生产实际中广泛地应用，都使图论的发展更加充满活力.,几个有趣的图论问题,Knigsberg七桥背后的故事 Knigsberg七桥位于前苏联的加里宁格勒，历史上曾是德国东普鲁士省的省会，霹雷格尔横穿城堡，河中有两个小岛B与C，并有七座桥连接岛与河岸及岛与岛（见图）。是否存在一种走发，从四块陆地中的任意一块开始，通过每一座桥恰好一次再回到起点。这就是著名的Knigsberg七桥问题，即一笔画问题；也是图论的起源。,欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。,图论欧拉,能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？,哥尼斯堡七桥问题,七桥问题的图模型,哥尼斯堡七桥问题,欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。,四色问题,为了能够迅速地区分一个平面地图或球面地图上的各个国家（假设这些国家在地图上都是连通的），需要用若干种颜色对这些国家着色，使得具有公共边界的两个国家涂染不同的颜色.那么，要保证每张地图都能如此着色，最少需要多少种颜色？这个问题是1850年被一名刚毕业的大学生Francis Guthrie首先提出的，直到1976年，四色问题被美国Illinois大学的K.Appel和W.Haken用计算机证明是正确的，这个证明令数学界震惊，它用了1200多小时，作出100亿个独立的逻辑判断.尽管有了这个机器证明，但它仍然是数学上未解决的问题之一.,Hamilton问题,Hamilton问题是图论中一直悬而未解的一大问题。它起源于1856年，当时英国数学家Hamilton设计了一种名为周游世界的游戏。他在一个实心的正十二面体的十二个顶点上标以世界上著名的二十座城市的名字，要求游戏者沿十二面体的棱从一个城市出发，经过每座城市恰好一次，然后返回到出发点，即“绕行世界”。正十二面体的顶点与棱的关系可以用平面上的图表示，把正十二面体的顶点与棱分别对应图的顶点与边，就得到正十二面体图。,正十二面体 Peterson图,旅行售货员问题,给出城市之间的距离，要求一位推销员从某一城市出发，周游每个城市一次，然后回到出发的城市，并且选的路径最短。这是一个图论优化问题，最早由美国数学家威特涅于1934年在普林斯顿一次讨论班上提出。1954年几位美国数学家写了第一篇论文，用线性方程的方法解决了49个城市的旅行售货员问题。后来也有不少论文讨论这个问题，在理论和应用上都很有价值。,生活中，人们常常需要考虑一些对象之间的某种特定的关系.如某区域内，两城市之间有无交通线；一群人中，两个人之间相识或不相识等等.这种关系是对称的，即如果甲对于乙有某种关系，则乙对于甲也有这种关系.可以用一个图形来描述给定对象之间的某个关系：我们用平面上的点分别表示这些对象，若对象甲和乙有关系，就用一条线连接表示甲和乙的两个点.这种由一些点与连接其中某些点对的线所构成的图形就是图论中所研究的图.图/Graph：可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。,6.1 图的基本概念,图的定义,图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。,在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。,如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。,若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。,若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。,如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。,6.1 图的基本概念,图的基本术语,简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。,数据结构中讨论的都是简单图。,6.1 图的基本概念,图的基本术语,邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。,V1的邻接点：V2、V4V2的邻接点：V1、V3、V5,6.1 图的基本概念,图的基本术语,邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。,V1的邻接点：V2、V3V3的邻接点：V4,6.1 图的基本概念,在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。,不同结构中逻辑关系的对比,在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。,不同结构中逻辑关系的对比,无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。,有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。,图的基本术语,6.1 图的基本概念,含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？,含有n个顶点的无向完全图有n(n-1)/2条边。含有n个顶点的有向完全图有n(n-1)条边。,6.1 图的基本概念,稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。,顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。,6.1 图的逻辑结构,图的基本术语,顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。,图的基本术语,在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？,6.1 图的基本概念,图的基本术语,在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？,6.1 图的基本概念,定理1.3.1(Handshaking)设无向图G=（V，E）有e条边，则G中所有顶点的度之和等于e的两倍。证明思路：考虑每条边在求和中的贡献。定理 无向图中度为奇数的顶点个数恰有偶数个。证明思路：将图中顶点的次分类，再利用定理1。定理 设有向图G=（V，A）有e条边，则G中所有顶点的入度之和等于所有顶点的出度之和，也等于e。证明思路：考虑每条边在求和中的情况。,即d(v)=2e,即d(v)=d+(v)=e,记住了吗？,几个重要定理,例 证明任何一群人中，有偶数个人认识其中奇数个人.(匈牙利数学竞赛试题)证 用n个顶点表示n个人.如果两个人相识，就用一条线把他们对应的一对顶点连起来，这样就得到了一个图G.每一个人所认识的人的数目就是他对应的顶点的次，于是问题就转化为证明图G中奇点的个数为偶数，而这正是定理的结论.,权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。,图的基本术语,6.1 图的基本概念,路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。,图的基本术语,一般情况下，图中的路径不惟一。,V1 到V4的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4,6.1 图的基本概念,路径长度：,6.1 图的逻辑结构,图的基本术语,非带权图路径上边的个数带权图路径上各边的权之和,V1 V4：长度为1V1 V2 V3 V4：长度为3V1 V2 V5V3 V4：长度为4,路径长度：,图的基本术语,非带权图路径上边的个数带权图路径上各边的权之和,V1 V4：长度为8V1 V2 V3 V4：长度为7V1 V2 V5V3 V4：长度为15,6.1 图的基本概念,回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。,图的基本术语,6.1 图的基本概念,子图：若图G=（V，E），G=（V，E），如果VV 且E E，则称图G是G的子图。,图的基本术语,6.1 图的基本概念,连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。,图的基本术语,如何求得一个非连通图的连通分量?,6.1 图的基本概念,V1,V2,V3,V4,V5,V6,V7,图的基本术语,连通分量是对无向图的一种划分。,6.1 图的基本概念,强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。,图的基本术语,如何求得一个非连通图的连通分量?,6.1 图的基本概念,图的基本术语,V1,V2,6.1 图的基本概念,生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。,生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。,如何理解极小连通子图?,图的基本术语,6.1 图的基本概念,6.1 图的基本概念,有向图中路的应用,例有A,B,C三个瓶，分别能装油8L,5L和3L.如果A装满油，B和C是空的，怎样以最快的速度平分A中的油？解法 我们用三位数码表示A,B,C三个瓶子装油的情况，又因为三位数码之和不变，所以可以用后两位数码表示三个瓶子装油的情况.例如：（0，0）表示初始状态.根据题意：共有十六种可能的状态，用这16个状态为顶点作图G，使得两个状态相邻当且仅当它们可以经过一次倒油相互转化.于是，问题就是要求从（0，0）到（4，0）的一条最短路.,容易作出图G（如下图）：,通过观察图得知共有两条从（0，0）到(4,0)的路：第一条:(0,0)(5,0)(2,3)(2,0)(0,2)(5,2)(4,3)(4,0);第二条:(0,0)(0,3)(3,0)(3,3)(5,1)(0,1)(1,0)(1,3)(4,0);从而，最快的速度平分即是最短的路所对应的过程，即第一条路的过程就是以最快的速度平分油的过程。,能说出具体操作吗？,图的抽象数据类型定义,class Graphpublic:Graph();void insertVertex(const T,6.1 图的基本概念,6.2 图的存储结构,是否可以采用顺序存储结构存储图?,图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。,如何存储图?,考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。,邻接矩阵（数组表示法）,基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。,假设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：,G.Edgeij,1 若(vi,vj)E（或E）0 其它,6.2 图的存储结构,无向图的邻接矩阵的特点？,无向图的邻接矩阵,主对角线为 0 且一定是对称矩阵。,6.2 图的存储结构,如何求顶点i的度？,无向图的邻接矩阵,V1,V3,V4,V2,邻接矩阵的第i行（或第i列）非零元素的个数。,6.2 图的存储结构,如何判断顶点 i 和 j 之间是否存在边？,无向图的邻接矩阵,V1,V3,V4,V2,测试邻接矩阵中相应位置的元素G.Edgeij是否为1。,6.2 图的存储结构,如何求顶点 i 的所有邻接点？,无向图的邻接矩阵,V1,V3,V4,V2,将数组中第 i 行元素扫描一遍，若G.Edgeij为1，则顶点 j 为顶点 i 的邻接点。,6.2 图的存储结构,有向图的邻接矩阵,有向图的邻接矩阵一定不对称吗？,不一定，例如有向完全图。,6.2 图的存储结构,有向图的邻接矩阵,如何求顶点 i 的出度？,邻接矩阵的第 i 行元素之和。,6.2 图的存储结构,有向图的邻接矩阵,如何求顶点 i 的入度？,邻接矩阵的第 i 列元素之和。,6.2 图的存储结构,有向图的邻接矩阵,如何判断从顶点 i 到顶点 j 是否存在边？,测试邻接矩阵中相应位置的元素G.Edgeij是否为1。,6.2 图的存储结构,网图的邻接矩阵,网图的邻接矩阵可定义为：,wij 若(vi,vj)E（或E）0 若i=j 其他,0 2 5 0 0 8 7 0,6.2 图的存储结构,邻接矩阵存储图的类,template class Graphmtx:public Graphfriend istream,6.2 图的存储结构,邻接表,邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。,图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？,假设图G有n个顶点e条边，则存储该图需要O(n2)。,6.2 图的存储结构,邻接表有两种结点结构：顶点表结点和边表结点。,顶点表 边 表,data：数据域，存放顶点信息。adj：指针域，指向边表中第一个结点。dest：邻接点域，边的终点在顶点表中的下标。link：指针域，指向边表中的下一个结点。,6.2 图的存储结构,template struct Edge int dest;E cost;Edge*link;template struct Vertex T data;Edge*adj;,定义邻接表的结点,6.2 图的存储结构,无向图的邻接表,边表中的结点表示什么？,每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。,6.2 图的存储结构,无向图的邻接表,如何求顶点 i 的度？,顶点i的边表中结点的个数。,6.2 图的存储结构,如何判断顶点 i 和顶点 j之间是否存在边?,测试顶点 i 的边表中是否存在终点为 j 的结点。,无向图的邻接表,6.2 图的存储结构,有向图的邻接表,如何求顶点 i 的出度？,顶点 i 的出边表中结点的个数。,6.2 图的存储结构,有向图的邻接表,如何求顶点 i 的入度？,各顶点的出边表中以顶点 i 为终点的结点个数。,6.2 图的存储结构,有向图的邻接表,如何求顶点 i 的所有邻接点？,遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。,6.2 图的存储结构,网图的邻接表,6.2 图的存储结构,邻接表表示的图的类定义,6.2 图的存储结构,template class Graphlnk:public Graphfriend istream,图的存储结构的比较邻接矩阵和邻接表,O（n2）,O（n+e）,6.2 图的存储结构,6.3 图的遍历,图的遍历操作,图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。,图的遍历操作要解决的关键问题,在图中，如何选取遍历的起始顶点？,在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。,解决方案：从编号小的顶点开始。,6.3 图的遍历,从某个起点始可能到达不了所有其它顶点，怎么办？,图的遍历操作要解决的关键问题,解决方案：多次调用从某顶点出发遍历图的算法。,下面仅讨论从某顶点出发遍历图的算法。,6.3 图的遍历,因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？,图的遍历操作要解决的关键问题,解决方案：附设访问标志数组visitedn。,解决方案：深度优先遍历和广度优先遍历。,6.3 图的遍历,约翰霍普克洛夫特1939年生于西雅图。1961年进入斯坦福大学研究生院深造，1962年获硕士学位，1964年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名学府工作，也曾任职于一些科学研究机构如 NSF（美国科学基金会）和 NRC（美国国家研究院）。,罗伯特陶尔扬1948年4月30日生于加利福尼亚州。1969年本科毕业，进入斯坦福大学研究生院，1972年获得博士学位。,1986年图灵奖获得者,6.3 图的遍历,1.深度优先遍历,基本思想：,访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。,6.3 图的遍历,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V5,6.3 图的遍历,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,V8,6.3 图的遍历,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,6.3 图的遍历,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V7,V2,V4,V5,V8,V3,V3,V6,V6,V7,6.3 图的遍历,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,遍历序列：,V1,V2,V4,V5,V8,V3,V6,V7,6.3 图的遍历,2.广度优先遍历,基本思想：,访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。,6.3 图的遍历,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V1,6.3 图的遍历,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V2,V3,V3,6.3 图的遍历,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V3,V3,V4,V4,V5,V5,6.3 图的遍历,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V3,V4,V4,V5,V5,V6,V6,V7,V7,6.3 图的遍历,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V3,V4,V5,V5,V6,V6,V7,V7,V8,V8,6.3 图的遍历,两种遍历算法时间性能的比较,O（n2）,O（n+e）,深度优先搜索,广度优先搜索,6.3 图的遍历,要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。,非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。,连通图：仅需从图中任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有顶点。,无向图的连通性,6.3 图的遍历,连通分量,count=0;2.for(图中每个顶点v)2.1 if(v尚未被访问过)2.1.1 count+;2.1.2 从v出发遍历该图；3.if(count=1)cout图是连通的;else cout图中有count个连通分量;,求无向图的连通分量,6.3 图的遍历,【例】以深度优先搜索方法从顶点 出发遍历图,建立深度优先生成森林。,A,B,C,D,E,F,G,A,A,B,D,E,C,F,G,有向图,深度优先生成森林,template void Graph:DFS_Forest(Tree/顶点 i 的值成为根 rt 的值 else,subT=T.InsertRightSibling(subT,GetValue(i);/顶点 i 的值成为 subT 右兄弟的值 DFS_Tree(T,subT,i,visited);/从顶点 i 出发深度优先遍历,建立以/subT为根的 T 的子树 template void Graph:DFS_Tree(Tree&T,TreeNode*RT,int v,int visited),TreeNode*p;visited v=1;/顶点 v 作访问过标志 int w=GetFirstNeighbor(v);/取顶点 v 的第一个邻接顶点 w int FirstChild=1;/第一个未访问子女应是 v 的左子女 while(w)/邻接顶点 w 存在 if(!visited w)/w未访问过,将成为 v 的子女 if(FirstChild)p=T.InsertLeftChild(RT,GetValue(w);/p 插入为 RT 的左子女,FirstChild=0;/建右兄弟 else p=T.InsertRightSibling(p,GetValue(w);/p 插入为 p 的左子女 DFS_Tree(T,p,w,visited);/递归建立 w 的以 p 为根的子树/邻接顶点 w 处理完 w=GetNextNeighbor(v,w);/取 v 的下一个邻接顶点 w/回到 while 判邻接顶点 w 存在,重连通分量(Biconnected Component),在无向连通图G中,当且仅当删去G中的顶点v及所有依附于v的所有边后,可将图分割成两个或两个以上的连通分量，则称顶点v为关节点。没有关节点的连通图叫做重连通图。在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。一个连通图G如果不是重连通图，那么它可以包括几个重连通分量。,在一个无向连通图G中,重连通分量可以利用深度优先生成树找到。在图中各顶点旁标明的深度优先数,给出进行深度优先搜索时各顶点访问的次序。深度优先生成树的根是关节点的充要条件是它至少有两个子女。其它顶点 u 是关节点的充要条件是它至少有一个子女 w,从 w 出发,不能通过 w、w 的子孙及一条回边所组成的路径到达 u 的祖先。,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,J,A,B,C,D,E,F,G,H,J,I,I,1,2,3,4,5,6,7,8,9,10,根有两 个子女,关节点,关节点,关节点,6.4 最小生成树,（a）深度优先生成树（b）广度优先生成树,生成树,由深度优先遍历得到的为深度优先生成树，由广度优先遍历得到的为广度优先生成树。,一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到不同的生成树。,对于非连通图，通过图的遍历，将得到的是生成森林。,结论：,生成树,6.4 最小生成树,生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。,最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。,最小生成树,最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？,6.4 最小生成树,最小生成树 在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边。,下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。,MST性质,假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。,6.4 最小生成树,基本思想：设G=(V,E)是具有n个顶点的连通网，T=(Vmst,Emst)是G的最小生成树，T的初始状态为Vmst=u0（u0V），Emst=，重复执行下述操作：在所有u Vmst，vV-Vmst的边中找一条代价最小的边(u,v)并入集合Emst，同时v并入Vmst，直至Vmst=V。,关键:是如何找到连接Vmst和V-Vmst的最短边。,普里姆（Prim）算法,利用MST性质，可以用下述方法构造候选最短边集：对应V-Vmst中的每个顶点，保留从该顶点到Vmst中的各顶点的最短边。,6.4 最小生成树,Vmst=A V-Vmst=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19,25,12,34,19,26,46,38,17,25,Prim算法,6.4 最小生成树,Prim算法,25,12,34,19,26,46,38,17,25,Vmst=A,F V-Vmst=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26,6.4 最小生成树,Prim算法,25,12,34,19,26,46,38,17,25,Vmst=A,F,C V-Vmst=B,D,Ecost=(A,B)34,(C,D)17,(F,E)26,6.4 最小生成树,Prim算法,25,12,34,19,26,46,38,17,25,Vmst=A,F,C,D V-Vmst=B,Ecost=(A,B)34,(F,E)26,6.4 最小生成树,Prim算法,25,12,34,19,26,46,38,17,25,Vmst=A,F,C,D,E V-Vmst=Bcost=(E,B)12,6.4 最小生成树,Prim算法,25,12,34,19,26,46,38,17,25,Vmst=A,F,C,D,E,B V-Vmst=,6.4 最小生成树,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,原图(a)(b),5,0,4,6,1,3,2,10,(c)(d)(e)(f),5,0,4,6,1,3,2,10,22,12,5,0,4,6,1,2,10,25,14,22,16,12,3,25,22,12,在构造过程中，还设置了两个辅助数组：lowcost 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；nearvex 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。例子,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,若选择从顶点0出发，即u0=0，则两个辅助数组的初始状态为：然后反复做以下工作：在 lowcost 中选择 nearvexi-1&lowcosti最小的边,用 v 标记它。则选中的权值最小的边为(nearvexv,v),相应的权值为 lowcostv。,0 28 10,-1 0 0 0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,将 nearvexv 改为-1,表示它已加入生成树顶点集合。将边(nearvexv,v,lowcostv)加入生成树的边集合。取 lowcosti=min lowcosti,Edgevi，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 v 的距离 Edgevi 与原来它们到生成树顶点集合中顶点的最短距离lowcosti 做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。,如果生成树顶点集合外顶点 i 到刚加入该集合的新顶点 v 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改nearvexi:nearvexi=v。表示生成树外顶点i到生成树内顶点v当前距离最近。,0 28 10,-1 0 0 0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,选 v=5,选边(0,5),顶点v=5加入生成树顶点集合：,0 28 25 10,-1 0 0 0 5-1 0,lowcost,nearvex,0 1 2 3 4 5 6,选 v=4,选边(5,4),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(0,5,10)加入生成树,12,0,4,6,1,3,2,10,25,5,0 1 2 3 4 5 6,顶点v=4加入生成树顶点集合：,0 28 22 25 10 24,-1 0 0 4-1-1 4,lowcost,nearvex,选 v=3,选边(4,3),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(5,4,25)加入生成树,12,5,0,4,6,1,3,2,10,25,22,顶点v=3加入生成树顶点集合：,0 28 12 22 25 10 18,-1 0 3-1-1-1 3,lowcost,nearvex,0 1 2 3 4 5 6,选 v=2,选边(3,2),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(4,3,22)加入生成树,12,5,0,4,6,1,3,2,10,25,22,12,lowcost,nearvex,0 1 2 3 4 5 6,顶点v=2加入生成树顶点集合：,0 16 12 22 25 10 18,-1 2-1-1-1-1 3,选 v=1,选边(2,1),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(3,2,12)加入生成树,12,5,0,4,1,3,2,10,25,22,16,12,顶点v=1加入生成树顶点集合：,0 16 12 22 25 10 14,-1-1-1-1-1-1 1,lowcost,nearvex,0 1 2 3 4 5 6,选 v=6,选边(1,6),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(2,1,16)加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,lowcost,nearvex,0 1 2 3 4 5 6,顶点v=6加入生成树顶点集合：,0 16 12 22 25 10 14,-1-1-1-1-1-1-1,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(1,6,14)加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,最后生成树中边集合里存入得各条边为：(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14),利用普里姆算法建立最小生成树void Graph:Prim(MinSpanTree/顶点0到各边代价,nearvexi=0;/及最短带权路径 nearvex0=-1;/加到生成树顶点集合 MSTEdgeNode e;/最小生成树结点单元 for(i=1;i NumVertices;i+)/循环n-1次,加入n-1条边 float min=MAXNUM;int v=0;for(int j=0;j NumVertices;j+)if(nearvexj!=-1/求生成树外顶点到生成树内顶点具有最/小权值的边,v是当前具最小权值的边,if(v)/v=0表示再也找不到要求顶点 e.tail=nearvexv;e.head=v;e.cost=lowcostv;T.Insert(e);/选出的边加入生成树 nearvexv=-1;/该边加入生成树标记 for(j=1;j NumVertices;j+)if(nearvexj!=-1,/循环n-1次,加入n-1条边分析以上算法,设连通网络有 n 个顶点,则该算法的时间复杂度为 O(n2),它适用于边稠密的网络。,1.初始化：Vmst=u0(V中任一顶点）；Emst=；2.循环直到Vmst=V为止 2.1 在所有uVmst,vV-Vmst的边中寻找代价最小 的边(u，v);2.2 Emst=Emst+(u,v)；2.3 Vmst=Vmst+u;,Prim算法伪代码,6.4 最小生成树,利用最小堆来存放E中的所有的边,堆中每个结点的格式为1、确定一个初始顶点u，加入Vmst,将所有依附于u和另一个在V-Vmst 中的顶点的边入堆；2、然后从堆顶取出权最小的边入Emst，同时修改u为新加入的顶点；3、重复步骤1、2直至V中所有顶点加入Vmst。,数据结构设计,6.4 最小生成树,tail head cost,边的两个顶点位置 边的权值,克鲁斯卡尔（Kruskal）算法,基本思想：设无向连通网为N(V,E)，令G的最小生成树为T=(Vmst,Emst)，其初态为Vmst V，Emst，然后，按照边的权值由小到大的顺序，考察N的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为N的