《数据结构》课件-第7章 图

数据构C语言描述结第7章

图第7章图知识目标理解图的概念和有关术语；掌握邻接矩阵表示法和邻接表表示法；理解连通图遍历的基本思想；掌握图的深度和广度优先搜索遍历算法；理解生成树和最小生成树的有关概念和算法；理解拓扑排序的概念、步骤和背景；理解关键路径和最短路径的概念和算法。技能目标：能应用图的理论设计算法，解决实际问题。7.4最小生成树7.1图的逻辑结构7.2图的存储结构7.3图的遍历7.5最短路径7.6案例实现——有向无环图及其应用欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他一生共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论——欧拉能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？ABCD哥尼斯堡七桥问题

CADB七桥问题的图模型哥尼斯堡七桥问题

欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。图的定义图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。7.1图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi

和vj

之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。

如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V0V1V2V3V4V0V1V2V37.1图的逻辑结构7.1图的逻辑结构图的基本术语简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。非简单图非简单图简单图数据结构中讨论的都是简单图V0V1V2V3V4V0V1V2V3V4V0V1V2V3V47.1图的逻辑结构邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi,vj)依附于顶点vi和顶点vj。V0的邻接点：V1、V3V1的邻接点：V0、V2、V4V0V1V2V3V4图的基本术语7.1图的逻辑结构图的基本术语邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj。其中vi为弧尾，vj为弧头。V0V1V2V3V0的邻接点：V1、V2V2的邻接点：V3<V0，V1>中，V0为弧尾，V1为弧头在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比V0V1V2V3V4图结构在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V0V1V2V3V4图结构不同结构中逻辑关系的对比7.1图的逻辑结构图的基本术语无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。V0V1V2V0V1V2V3含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？

含有n个顶点的无向完全图有n×(n-1)/2条边含有n个顶点的有向完全图有n×(n-1)条弧7.1图的逻辑结构V0V1V2V0V1V2V37.1图的逻辑结构图的基本术语稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。7.1图的逻辑结构图的基本术语在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？å==nievTD12)(iV0V1V2V3V47.1图的逻辑结构图的基本术语V0V1V2V3在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii====11)()(nnåå7.1图的逻辑结构图的基本术语权（Weight）：指对边赋予的有意义的数值量。网（Network）：边上带权的图，也称网图。V0V1V2V32785哈夫曼树中的权与网图的权有何区别？74237.1图的逻辑结构图的基本术语路径（Path）：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<vij-1,vij>∈E。一般情况下，图中的路径不唯一V0到V3的路径：

V0V3

V0V1V2V3V0V1V4V2V3V0V1V2V3V47.1图的逻辑结构图的基本术语路径长度：非带权图——路径上边的个数带权图——路径上各边的权之和V0V3：长度为1V0V1V2V3：长度为3V0V1V4V2V3：长度为4V0V1V2V3V47.1图的逻辑结构图的基本术语路径长度：非带权图——路径上边的个数带权图——路径上各边的权之和V0V3：长度为8V0V1V2V3：长度为7V0V1V4V2V3：长度为15256328V0V1V2V3V47.1图的逻辑结构图的基本术语回路或环（Cycle）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。V0V1V2V3V4V0V1V2V37.1图的逻辑结构图的基本术语子图：若图G=（V，E），G'=（V'，E'），如果V'

V

且E'

E，则称图G’是G的子图。V0V1V2V3V4V0V1V2V3V4V0V2V37.1图的逻辑结构图的基本术语连通图：在无向图中，如果从一个顶点vi到另一个顶点vj（i≠j）有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。如何求得一个非连通图的连通分量?1.含有极大顶点数2.依附于这些顶点的所有边7.1图的逻辑结构图的基本术语连通分量1V0V1V3V4V2V6V5V0V1V4V2V3V6V5连通分量2连通分量是对无向图的一种划分7.1图的逻辑结构图的基本术语强连通图：在有向图中，对图中任意一对顶点vi和vj（i≠j），若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。如何求得一个非强连通图的强连通分量?7.1图的逻辑结构图的基本术语V0V1V2V3强连通分量1

强连通分量2V0V2V3V17.1图的逻辑结构图的基本术语生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个

极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如何理解极小连通子图?多——构成回路少——不连通含有n-1条边7.1图的逻辑结构V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成树生成森林你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。7.1图的逻辑结构案例：六度空间理论7.1图的逻辑结构图的抽象数据类型定义图是一种与具体应用密切相关的数据结构，它的基本操作往往随应用不同而有很大差别。下面给出一个图的抽象数据类型定义的例子，简单起见，基本操作仅包含图的遍历，针对具体应用，需要重新定义其基本操作。7.1图的逻辑结构图的抽象数据类型定义ADTGraphData

顶点的有穷非空集合和边的集合OperationCreateGraph(G)：输入图G的顶点和边，建立图G的存储DestroyGraph(G)：释放图所占用的存储空间LocateVertex(G,v)：在图G中找到顶点v，返回该顶点在图中的位置GetVertex(G,i)：在图G中找到顶点v，返回该顶点的相关信息FirstAdjVertex(G,v)：在图G中返回v的第一个邻接点7.1图的逻辑结构NextAdjVertex(G,v,w)：在图G中返回v的下一个邻接点，若w为v的最后一个邻接点，则返回空InsertVertex(G,v)：在图G中增添一个新顶点vDeleteVertex(G,v)：在图G中删除顶点v以及所有和顶点v相关联的弧或边InsertArc(G,v,w)：在图G中增添一条从顶点v到顶点w的边或弧DeleteArc(G,v,w)：在图G中删除一条从顶点v到顶点w的边或弧DFSTraverse(G,v)：从顶点v出发深度优先遍历图GBFSTraverse(G,v)从顶点v出发广度优先遍历图GendADT7.2图的存储结构图的特点?顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系。如何存储图?链式存储结构：顺序存储结构：邻接矩阵邻接表十字链表邻接多重表01顶点信息边或弧的信息，即顶点之间的关系027.2图的存储结构基本思想：建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：arc[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它邻接矩阵（数组表示法）7.2图的存储结构无向图的邻接矩阵无向图的邻接矩阵的特点？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主对角线为0且一定是对称矩阵。01

2

3顶点表邻接矩阵7.2图的存储结构无向图的邻接矩阵如何求顶点Vi的度？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3邻接矩阵的Vi行（或Vi列）非零元素的个数。01

2

37.2图的存储结构无向图的邻接矩阵如何判断顶点Vi

和Vj

之间是否存在边？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3测试邻接矩阵中相应位置的元素arc[i][j]是否为1。01

2

37.2图的存储结构无向图的邻接矩阵如何求顶点Vi

的所有邻接点？(第一个邻接点和下一个邻接点)？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3将二维数组中对应的Vi行元素扫描一遍，若arc[i][j]为1，则顶点Vj

为顶点Vi的邻接点。01

2

37.2图的存储结构无向图的邻接矩阵完全图的邻接矩阵的特点？V0V2V3V1V0V1V2V3vertex=0101101101001100arc=V0V1V2V3V0V1V2V3主对角线为0，其余都为1。01

2

37.2图的存储结构有向图的邻接矩阵有向图的邻接矩阵一定不对称吗？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3不一定，例如有向完全图。01

2

37.2图的存储结构有向图的邻接矩阵如何求顶点Vi

的出度？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3邻接矩阵中顶点Vi

所在的行元素之和。01

2

37.2图的存储结构有向图的邻接矩阵如何求顶点Vi

的入度？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3邻接矩阵中顶点Vi

所在的列元素之和。01

2

37.2图的存储结构有向图的邻接矩阵如何判断从顶点Vi到顶点Vj是否存在边？V0V3V1V2V0V1V2V3vertex=011

0

000

0

0001

1000arc=V0V1V2V3V0V1V2V3测试邻接矩阵中相应位置的元素arc[i][j]是否为1。01

2

37.2图的存储结构网图的邻接矩阵025∞∞0∞∞∞∞087∞∞0arc=V0V3V1V22785网图的邻接矩阵可定义为：arc[i][j]＝wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他缺点：存储空间浪费大对于无向图而言，可采用压缩存储法（下三角），其存储空间只需n(n+1)/2。但对于有向图而言，需要n2个存储空间。优点：便于运算，采用邻接矩阵表示法，便于求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。邻接矩阵所占的空间与边数无关，适合于存储稠密图7.2图的存储结构邻接矩阵的特点

#defineMAX_VEX_NUM20/*定义图中最大顶点个数*/typedefcharVertexType;/*定义顶点类型*/typedefstructGraph{VertexTypevexs[MAX_VEX_NUM];/*顶点集合*/int

AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];

/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧(边)数*/}MGraph;

MGraphG；G->vexnum=i;G->arcnum=j;G.vexs[i]==u；G->AdjMatrix[i][j]=17.2图的存储结构邻接矩阵表示法的C语言类型描述7.2图的存储结构邻接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。7.2图的存储结构邻接表邻接表有两种结点结构：顶点表结点和边表结点。vertexfirstedgeadjvexnext

顶点表边表vertex：数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。7.2图的存储结构邻接表103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2图的存储结构定义邻接表的结点#defineMaxVertexNum100typedefstructnode{/*边表结点*/

intadjvex;/*邻接点域*/structnode*next;/*指向下一个邻接点的指针域*/}EdgeNode;typedefstructvnode{/*顶点表结点*/VertexTypevertex;/*顶点域*/EdgeNode*firstedge;/*指向边表中第一个结点*/}VertexNode;

adjvex

next

边表vertexfirstedge顶点表7.2图的存储结构定义邻接表typedefVertexNodeAdjList[MaxVertexNum];typedefstruct{AdjListadjlist;/*邻接表*/intn,e;/*顶点数和边数*/}ALGraph;/*基于邻接表的图7.2图的存储结构无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2图的存储结构无向图的邻接表如何求顶点Vi的度？顶点Vi的边表中结点的个数。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2图的存储结构无向图的邻接表如何判断顶点Vi和顶点Vj之间是否存在边?测试顶点Vi的边表中是否存在终点为Vj的结点。103∧23∧1∧01∧V0V1

V2V30123vertexfirstedgeV0V2V3V17.2图的存储结构有向图的邻接表如何求顶点Vi的出度？顶点Vi

的出边表中结点的个数。12∧3∧0∧V0V1

∧V2V30123vertexfirstedgeV0V3V1V27.2图的存储结构有向图的邻接表如何求顶点Vi的入度？各顶点的出边表中以顶点Vi

为终点的结点个数。12∧3∧0∧V0V1

∧V2V30123vertexfirstedgeV0V3V1V27.2图的存储结构有向图的邻接表如何求顶点Vi的所有邻接点？遍历顶点Vi

的边表，该边表中的所有终点都是顶点Vi的邻接点。12∧3∧0∧V0V1

∧V2V30123vertexfirstedgeV0V3V1V27.2图的存储结构网图的邻接表V0V1V2V3278521V0V1

V2V30123vertexfirstedge∧52∧83∧70∧7.2图的存储结构图的存储结构的比较——邻接矩阵和邻接表O(n2)O(n+e)O(n2)O(n+e)空间性能时间性能适用范围唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。7.3图的遍历图的遍历算法是求解图的连通性问题、拓扑排序和关键路径等算法的基础。图的遍历操作图的遍历操作要解决的关键问题①在图中，如何选取遍历的起始顶点？在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。

为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始。7.3图的遍历②从某个起点始可能到达不了所有其它顶点，怎么办？解决方案：多次调用从某顶点出发遍历图的算法。下面仅讨论从某顶点出发遍历图的算法。7.3图的遍历图的遍历操作要解决的关键问题③因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。④在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？解决方案：附设访问标志数组visited[n]。解决方案：深度优先遍历和广度优先遍历。7.3图的遍历图的遍历操作要解决的关键问题1.深度优先遍历基本思想：访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。7.3图的遍历深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V57.3图的遍历深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V8V87.3图的遍历深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8V1遍历序列：V1V2V2V4V4V5V87.3图的遍历深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8V1遍历序列：V1V7V2V4V5V8V3V3V6V6V77.3图的遍历1.深度优先遍历从顶点v出发图的深度优先遍历算法的伪代码：

1.访问顶点v;visited[v]=1;2.w=顶点v的第一个邻接点；3.while(w存在)3.1if(w未被访问)从顶点w出发递归执行该算法;3.2w=顶点v的下一个邻接点;7.3图的遍历voidDFS(GraphG,intv)/*从第v个顶点出发深度优先遍历图G*/{visited[v]=1；/*访问顶点v，并置访问标志数组相应分量值*/

VisitFunc(v);/*访问第v个顶点*/w=FirstAdjVex(G,v);while(w!=-1)/*邻接点存在*/{if(!visited[w])DFS(G,w);/*对v的尚未访问的邻接顶点w递归调用DFS*/w=NextAdjVex(G,v,w);/*找下一个邻接点*/}}对于FirstAdjVertex(G,v)以及NextAdjVertex(G,v,w)并没有具体展开，若图的存储结构不同，对应操作的实现方法不同，时间耗费也不同。教材P195【算法7-3】以邻接表为存储结构深度优先遍历图G2.广度优先遍历基本思想：访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,…,vk；分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。7.3图的遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V17.3图的遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V37.3图的遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V57.3图的遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V77.3图的遍历广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V87.3图的遍历2.广度优先遍历从顶点v出发图的广度优先遍历算法的伪代码：

1.初始化队列Q;2.访问顶点v;visited[v]=1;顶点v入队列Q;3.while(队列Q非空)3.1v=队列Q的队头元素出队;3.2w=顶点v的第一个邻接点;3.3while(w存在)3.3.1如果w未被访问，则访问顶点w;visited[w]=1;顶点w入队列Q；

3.3.2w=顶点v的下一个邻接点；7.3图的遍历具体代码

详见教材P197生成树的代价：设G=(V,E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树（MST）：在图G所有生成树中，代价最小的生成树称为最小生成树。7.4最小生成树（MST）最小生成树的定义生成树的代价：设G=(V,E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树（MinimumCostSpanningTree，MST）：在图G所有生成树中，代价最小的生成树。最小生成树的经典应用：在n个城市之间建造通信网络，至少要架设n-1条通信线路，每两个城市之间架设通信线路的造价是不一样的，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路，使总费用最少？7.4最小生成树（MST）最小生成树的定义数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间通信网。显然此连通网是一个生成树假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集，用于存放G的最小生成树中的顶点。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。顶点集UV－Uu'vv'u顶点集T1T27.4最小生成树（MST）最小生成树MST性质Prim（普里姆）算法：归并顶点，与边数无关，适于稠密网Kruskal（克鲁斯卡尔）算法：归并边，适于稀疏网7.4最小生成树（MST）如何求最小生成树基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U={u0}（u0∈V），TE={}，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。7.4最小生成树Prim算法的基本思想用伪代码描述如下：1.初始化：U={u0}；TE={}；2.重复下述操作直到U=V：2.1在E中寻找最短边(u，v)，且满足u∈U，v∈V-U；

2.2U=U+{v}；2.3TE=TE+{(u，v)}；关键：是如何找到连接U和V-U的最短边。普里姆（Prim）算法U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,

(A,E)∞,(A,F)19}251234192646381725ABEDCF7.4最小生成树普里姆（Prim）算法U={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,

(F,D)25,(F,E)26}251234192646381725ABEDCF7.4最小生成树普里姆（Prim）算法U={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}251234192646381725ABEDCF7.4最小生成树普里姆（Prim）算法U={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}2512341926381725ABEDCF7.4最小生成树普里姆（Prim）算法U={A,F,C,D,E}V-U={B}cost={(E,B)12}123419261725ABEDCF7.4最小生成树普里姆（Prim）算法U={A,F,C,D,E,B}V-U={}1219261725ABEDCF7.4最小生成树普里姆（Prim）算法7.4最小生成树基本思想：从加权图中选取权值最小的边，与该边相关联的顶点被选择；再从图中选取权值最小的边，若该边使已经选择的顶点和边构成圈，则去掉该边；重复步骤②，直到没有未被选择也未被去掉的边，剩下的边和图的全部顶点构成最小生成树。克鲁斯卡尔（Kruskal）算法251234192646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}7.4最小生成树克鲁斯卡尔（Kruskal）算法251234192646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}7.4最小生成树克鲁斯卡尔（Kruskal）算法12连通分量＝{A},{B,E},{C},{D},{F}251234192646381725ABEDCFABEDCF连通分量＝{A},{B,E},{C},{D},{F}7.4最小生成树克鲁斯卡尔（Kruskal）算法12连通分量＝{A},{B,E},{C,D},{F}17251234192646381725ABEDCFABEDCF连通分量＝{A},{B,E},{C,D},{F}7.4最小生成树克鲁斯卡尔（Kruskal）算法12连通分量＝{A,F},{B,E},{C,D}1917251234192646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C,D}7.4最小生成树克鲁斯卡尔（Kruskal）算法12连通分量＝{A,F,C,D},{B,E}191725251234192646381725ABEDCFABEDCF连通分量＝{A,F,C,D},{B,E}7.4最小生成树克鲁斯卡尔（Kruskal）算法12连通分量＝{A,F,C,D,B,E}19172526在非网图中，最短路径是指两顶点之间经历的边数最少的路径。7.5最短路径BAEDCAE：1ADE：2ADCE：3ABCE：3最短路径在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。7.5最短路径BAEDC最短路径105030101002060AE：100ADE：90ADCE：60ABCE：70问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径。应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。7.5最短路径单源点最短路径问题基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,…,vk，就将vk加入集合S中，并将路径v,…,vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。7.5最短路径集合

V-S集合

Svkvvi迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)1007.5最短路径迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)1007.5最短路径迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)907.5最短路径迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)607.5最短路径迪杰斯特拉（Dijkstra）算法ABAEDC105030101002060S={A,B,D,C,

E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)607.5最短路径迪杰斯特拉（Dijkstra）算法问题描述：给定带权有向图G＝(V,E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。解决办法1：每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为O(n3)。解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。7.5最短路径每一对顶点之间的最短路径基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。7.5最短路径弗洛伊德（Floyd）算法04116023∞0有向网图邻接矩阵7.5最短路径弗洛伊德（Floyd）算法acb346112acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化7.5最短路径弗洛伊德（Floyd）算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代

加入顶点adist0

=0411602370path0

=

abacbabccacab

7.5最短路径弗洛伊德（Floyd）算法acb346112dist0

=0411602370path0

=

abacbabccacab第2次迭代

加入顶点bdist1

=046602370path1

=ababc

babccacab7.5最短路径弗洛伊德（Floyd）算法acb346112dist1

=046602370path1

=ababcbabccacab第3次迭代

加入顶点cdist2

=0465