数据结构(CC++语言版)第六章new课件.ppt

1.图的基本概念图的基本概念2.2.图的存储结构图的存储结构3.3.图的遍历图的遍历4.4.最小生成树最小生成树5.5.最短路径最短路径6.6.拓扑排序拓扑排序7.7.关键路径关键路径1问题问题n假设要在假设要在n个城市之间建立通信网。令图个城市之间建立通信网。令图G的的顶点表示城市，边表示连接两个城市的通信顶点表示城市，边表示连接两个城市的通信线路，边的权值表示通信线路的长度或代价。线路，边的权值表示通信线路的长度或代价。在在n个城市间构造通信网最少需要个城市间构造通信网最少需要n-1条线路，条线路，问：如何选择这问：如何选择这n-1条边，使得构造这个通信条边，使得构造这个通信网总的代价最小？网总的代价最小？21 1、熟悉图的各种存储结构、熟悉图的各种存储结构2 2、熟练掌握遍历图的算法、熟练掌握遍历图的算法3 3、应用图的遍历算法求解各、应用图的遍历算法求解各 种简单路径问题种简单路径问题学习要点：学习要点：36.1 图的基本概念图的基本概念定义定义:图是由图是由顶点顶点集合集合(vertex)及及边边的集合组的集合组成的一种数据结构成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点的有穷是顶点的有穷非空集合；非空集合；E=(x,y)|x,y V 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集集合。例如合。例如:E=,4n n顶点的度顶点的度 一个顶点一个顶点v 的度是与它相关联的的度是与它相关联的边的条数。边的条数。记作记作TD(v)。顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(ID(v v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以是以是以 v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记作记作 OD(OD(v v)。邻接点：邻接点：若（若（vi,vjvi,vj）是一条无向边，则称）是一条无向边，则称顶点顶点vivi和和vjvj互为邻接点互为邻接点。1235687410796671231516ABDCE603045358040756 子图子图子图子图 设有两个图设有两个图设有两个图设有两个图 GG(V V,E E)和和和和 GG(V V,E E)。若。若。若。若 V V V V 且且且且 E E E E,则称则称则称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。7 路径路径路径路径 在图在图在图在图 G G(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 vi vi 出发出发出发出发,沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点 vpvp1 1,vpvp2 2,vpmvpm，到达顶点，到达顶点，到达顶点，到达顶点vj vj。则称顶点序列。则称顶点序列。则称顶点序列。则称顶点序列 (vi vi vpvp1 1 vpvp2.2.vpm vpm vj vj)为从顶点为从顶点为从顶点为从顶点vi vi 到顶点到顶点到顶点到顶点 vj vj 的路径的路径的路径的路径。它经过的边。它经过的边。它经过的边。它经过的边(vi vi,vpvp1)1)、(vpvp1,1,vpvp2)2)、.、(vpmvpm,vj vj)应是属于应是属于应是属于应是属于E E的边。的边。的边。的边。简单路径简单路径简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上各顶点 v v1,1,v v2,.,2,.,vm vm 均不互相重复均不互相重复均不互相重复均不互相重复,则称这样的路径则称这样的路径则称这样的路径则称这样的路径为简单路径。为简单路径。为简单路径。为简单路径。回路回路回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点vm vm 重合重合重合重合,则称这样的路径则称这样的路径则称这样的路径则称这样的路径为回路或环。为回路或环。为回路或环。为回路或环。路径长度路径长度路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。81235687410796671231516ABDCE60304535804075权：权：权：权：某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。这称之为权。这种带权图叫做网种带权图叫做网。10 生成树生成树 一个连通图的生成树是它的极小一个连通图的生成树是它的极小 连通子图，在连通子图，在n个顶点的情形下，有个顶点的情形下，有n-1条条 边。边。生成森林生成森林n n不予讨论的图不予讨论的图 包含顶点到其自身的边；包含顶点到其自身的边；一条边在图中重复出现一条边在图中重复出现1121435n n邻接矩阵邻接矩阵邻接矩阵邻接矩阵n n顶点矩阵顶点矩阵顶点矩阵顶点矩阵13若若G G是带权的图是带权的图,则邻接矩阵定义为则邻接矩阵定义为:Wi,j若若 或或(vi,vj)E0 0或或 反之反之 Aij=5 9 7 4 G1.arcs=V1V2V3V4有向图有向图G15497有向网有向网G1的邻接矩阵为：的邻接矩阵为：15215346203050407080带权图的邻接矩阵带权图的邻接矩阵16邻接矩阵的实现邻接矩阵的实现(class(class定义定义)C+)C+：template class MGraph public:MGraph(T a,int n,int e);MGraph();MGraph();void dfs(int v);void bfs(int v);private:T vertexMaxsize;int arcMaxsizeMaxsize;int vertexnum,arcnum;18邻接矩阵的构造函数方法一邻接矩阵的构造函数方法一:(无向图无向图)template MGraph:MGraph(T a,int n,int e)vertexnum=n,arcnum=e;for(i=0;ivertexnum;i+)vertexi=ai;for(i=0;ivertexnum;i+)for(j=0;jvertexnum;j+)arcij=0;for(k=0;kij;arcij=1;arcji=1;19邻接矩阵的构造函数方法二邻接矩阵的构造函数方法二:(无向图无向图)template MGraph:MGraph()cinvexnumarcnum;for(i=0;i vertexi;for(i=0;ivexnum;i+)for(j=0;j vexnum;j+)arcij0;for(k=0;kvivj;i=search(vertex,vi);j=search(vertex,vj);arcij=1;arcji=1;20Status CreateGraph(Mgraph&G)int i，j;AdjType w;VexType v1,v2;/输入顶点数、边数和是否输入边的相关信息的标志 scanf(“%d%d”,&G.vexnum,&G.arcnum);for(i=0;i G.vexnum;i+)/读入所有的顶点 scanf(“%c”,&G.vexsi);for(i=0;i G.vexnum;i+)/初始化邻接矩阵 for(j=0;jarcsij =INFINITY;for(i=0;iarcsij.adj=w;pG-arcsji=pG.arcsij;return OK;/查找某个顶点在图中的存储位置（下标），找不到返回-1int LocateVex(Mgraph&G,VexType vert)int i;for(i=0;ivexsi=vert)return i;return-1;22n基本思想：基本思想：v 如果对图中的所有顶点都建立一个单链表（如果对图中的所有顶点都建立一个单链表（边表边表边表边表）来存储所有依附于该顶点的弧或边，就可以把图中来存储所有依附于该顶点的弧或边，就可以把图中所有已有的弧或边的信息保存下来。所有已有的弧或边的信息保存下来。v对于图中所有顶点还是使用一个一维数组来存放。对于图中所有顶点还是使用一个一维数组来存放。在邻接表表示法中，对于顶点单元在邻接表表示法中，对于顶点单元i，需要存放的内容，需要存放的内容有顶点信息以及指向依附于该顶点的所有的弧或边组有顶点信息以及指向依附于该顶点的所有的弧或边组成的单链表（边表）。成的单链表（边表）。对于边表中弧单元，需要存放该弧指向的顶点的位置对于边表中弧单元，需要存放该弧指向的顶点的位置（也就是该弧依附的另一个顶点的位置）和指向下一（也就是该弧依附的另一个顶点的位置）和指向下一条弧的指针。条弧的指针。二二.邻接表邻接表(Adjacency List)24无向图的邻接表无向图的邻接表 把同一个顶点发出的边链接在同一个边链表中，把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点结点中保存有与该边相关联的另一顶点的顶点下标下标 dest 和指向同一链表中下一个边结点的指和指向同一链表中下一个边结点的指针针 link。25有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表 在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第 i i 个边链表链接的边都是个边链表链接的边都是个边链表链接的边都是个边链表链接的边都是顶点顶点顶点顶点 i i 发出发出发出发出的边的边的边的边。也叫做。也叫做。也叫做。也叫做出边表出边表出边表出边表。在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接表中，第 i i 个边链表链接的边都是个边链表链接的边都是个边链表链接的边都是个边链表链接的边都是进入顶点进入顶点进入顶点进入顶点 i i 的边的边的边的边。也叫做。也叫做。也叫做。也叫做入边表入边表入边表入边表。26网网(带权图带权图)的邻接表的邻接表28邻接表中的结点类型定义：邻接表中的结点类型定义：struct ArcNode int adjvex;ArcNode*next;template struct VertexNode T vertex;ArcNode*firstedge;29 邻接表的构造函数邻接表的构造函数(方法一方法一)：ALGraph:ALGgraph(T a,int n,int e);vexnum=n;arcnum=e;for(i=0;i vexnum;i+)adjlisti.vertex=ai;adjlisti.firstedge NULL;for(k=0;kij;snew ArcNode;s-adjvexj;s-next adjlisti.firstedge;adjlisti.firstedge s;31 邻接表的构造函数邻接表的构造函数(方法二方法二)：ALGraph:ALGraph()cinvexnumarcnum;for(i=0;i adjlisti.vertex;adjlisti.firstedge NULL;for(k=0;kvivj;i=search(adjlist,vi);j=search(adjlist,vj);snew ArcNode;s-adjvexj;s-next adjlisti.firstedge;adjlisti.firstedge s;32 优点：优点：在边稀疏的情况下，节省存储空间在边稀疏的情况下，节省存储空间 易于确定图中任一顶点的度数和它的所易于确定图中任一顶点的度数和它的所有邻接点。有邻接点。缺点：缺点：判定任意两个顶点之间是否有边或弧不判定任意两个顶点之间是否有边或弧不方便。方便。邻接表的优缺点邻接表的优缺点：33n给出其邻接矩阵和邻接表表示。n请画出：（1）以a为起点的一棵深度优先生成树和广度优先生成树。（2）以d为起点的一棵深度优先生成树和广度优先生成树。346.3 图的遍历图的遍历n n概念概念概念概念 从图中某一顶点出发，沿着某条搜索路径访问从图中某一顶点出发，沿着某条搜索路径访问从图中某一顶点出发，沿着某条搜索路径访问从图中某一顶点出发，沿着某条搜索路径访问图中所有的顶点，且使每个顶点仅被访问一次，图中所有的顶点，且使每个顶点仅被访问一次，图中所有的顶点，且使每个顶点仅被访问一次，图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历。就叫做图的遍历。就叫做图的遍历。就叫做图的遍历。n n复杂性复杂性复杂性复杂性图的任一顶点都可能与其它顶点相通，即图中可图的任一顶点都可能与其它顶点相通，即图中可图的任一顶点都可能与其它顶点相通，即图中可图的任一顶点都可能与其它顶点相通，即图中可能存在回路，在访问完某个顶点之后可能会沿着能存在回路，在访问完某个顶点之后可能会沿着能存在回路，在访问完某个顶点之后可能会沿着能存在回路，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。某些边又回到了曾经访问过的顶点。某些边又回到了曾经访问过的顶点。某些边又回到了曾经访问过的顶点。为了避免重复访问，需设置一个标志顶点是否被为了避免重复访问，需设置一个标志顶点是否被为了避免重复访问，需设置一个标志顶点是否被为了避免重复访问，需设置一个标志顶点是否被访问过的辅助数组访问过的辅助数组访问过的辅助数组访问过的辅助数组 visitedvisited ，它的初始状态为它的初始状态为它的初始状态为它的初始状态为 0 0，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点 i i 被访问，被访问，被访问，被访问，就立即让就立即让就立即让就立即让 visitedvisited i i 为为为为 1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。35 类似于树的先根遍历，是树的先根遍历的推广。类似于树的先根遍历，是树的先根遍历的推广。图的深度优先遍历规则：图的深度优先遍历规则：假设初始状态是图中所有顶点都未被访问，则可从图假设初始状态是图中所有顶点都未被访问，则可从图中某个顶点中某个顶点v出发，访问此顶点，然后依次从出发，访问此顶点，然后依次从v的未被访的未被访问的邻接点出发深度优先遍历图，直至所有与问的邻接点出发深度优先遍历图，直至所有与v有通路有通路的顶点都被访问到；的顶点都被访问到；若此时图中还有顶点未被访问到，则另选图中未被访若此时图中还有顶点未被访问到，则另选图中未被访问的顶点作起点，重复上述过程，直到图中所有顶点都问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到为止。被访问到为止。V1V2V3V4V5V8V6V7深度优先搜索深度优先搜索(DFS:Depth First Search)36深度优先搜索的示例深度优先搜索的示例37void DFS(MGraph G,int i)int j;VisitFunc(G.vexsv);/访问第访问第v个顶点个顶点 visitedi=TRUE;/设置访问标志为设置访问标志为TRUE(已访问已访问)for(j=0;jG.vexnum;j+)if(G.arcsij=1&!visitedj)DFS(G,j);图的深度优先搜索算法：图的深度优先搜索算法：图的深度优先搜索算法：图的深度优先搜索算法：Boolean visited MAX;Status (*VisitFunc)(int v);以邻接矩阵表示法作为图的存储结构以邻接矩阵表示法作为图的存储结构连通图：连通图：连通图：连通图：38非连通图：非连通图：void DFSTraverse(MGraph G,Status(*Visit)(VertexType)int v;VisitFunc=Visit;for(v=0;vG.vexnum;v+)visitedv=FALSE;/访问标志数组初始化访问标志数组初始化(未被访问未被访问)for(v=0;vG.vexnum;v+)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用对尚未访问的顶点调用DFS问题：问题：1.如何判断一个图是否是连通的？如何判断一个图是否是连通的？2.如何求出一个非连通图中的连通分量个数？如何求出一个非连通图中的连通分量个数？39例子例子遍历结果：遍历结果：A A、C C、B B、D D40算法分析：算法分析：设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边。条边。条边。条边。如果用邻接矩阵表示图，查找每一个顶点的所有如果用邻接矩阵表示图，查找每一个顶点的所有如果用邻接矩阵表示图，查找每一个顶点的所有如果用邻接矩阵表示图，查找每一个顶点的所有的边，所需时间为的边，所需时间为的边，所需时间为的边，所需时间为O(O(n n)，则遍历图中所有的顶点则遍历图中所有的顶点则遍历图中所有的顶点则遍历图中所有的顶点所需的时间为所需的时间为所需的时间为所需的时间为O(O(n n2 2)。如果用邻接表表示图，沿如果用邻接表表示图，沿如果用邻接表表示图，沿如果用邻接表表示图，沿 firstarcfirstarc nextarcnextarc 链可链可链可链可以找到某个顶点以找到某个顶点以找到某个顶点以找到某个顶点 v v 的所有邻接顶点的所有邻接顶点的所有邻接顶点的所有邻接顶点 w w。由于总共由于总共由于总共由于总共有有有有 2 2e e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(O(e e)。而且而且而且而且对所有顶点递归访问对所有顶点递归访问对所有顶点递归访问对所有顶点递归访问1 1次，所以遍历图的时间复杂次，所以遍历图的时间复杂次，所以遍历图的时间复杂次，所以遍历图的时间复杂性为性为性为性为O(O(n n+e e)。41 类似于树的层次遍历。类似于树的层次遍历。假设从图中某个顶点假设从图中某个顶点v出发，在访问了出发，在访问了v之后，依次访问之后，依次访问v的各个未曾访问过的邻接点，并保证的各个未曾访问过的邻接点，并保证“先被访问的顶点的先被访问的顶点的邻接点邻接点”要先于要先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问。直被访问。直至图中所有已被访问的顶点的邻接点都被访问到。若此时至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的顶点，则任选其中之一作为起点，重图中还有未被访问的顶点，则任选其中之一作为起点，重新开始上述过程，直至图中所有顶点都被访问到。新开始上述过程，直至图中所有顶点都被访问到。对于广度优先遍历：对于广度优先遍历：其关键之处在于怎么保证其关键之处在于怎么保证“先被访问的顶点的邻接点先被访问的顶点的邻接点”要先于要先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问被访问，也就是，也就是先到先被访问。先到先被访问。广度优先搜索广度优先搜索(BFS:Breadth First Search)42广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树43 使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v v 之后，由之后，由之后，由之后，由 v v 出发，依次出发，依次出发，依次出发，依次访问访问访问访问 v v 的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点 w w1 1,w w2 2,w wt t，然后然后然后然后再顺序访问再顺序访问再顺序访问再顺序访问 w w1 1,w w2 2,w wt t 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问再从这些访问过的顶点出发，再访问它们的所有还未被访问再从这些访问过的顶点出发，再访问它们的所有还未被访问再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，过的邻接顶点，过的邻接顶点，过的邻接顶点，如此做下去，直到图中所有顶点都被访问如此做下去，直到图中所有顶点都被访问如此做下去，直到图中所有顶点都被访问如此做下去，直到图中所有顶点都被访问到为止。到为止。到为止。到为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访广度优先搜索是一种分层的搜索过程，每向前走一步可能访广度优先搜索是一种分层的搜索过程，每向前走一步可能访广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，问一批顶点，不像深度优先搜索那样有往回退的情况。因此，问一批顶点，不像深度优先搜索那样有往回退的情况。因此，问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。广度优先搜索不是一个递归的过程，其算法也不是递归的。广度优先搜索不是一个递归的过程，其算法也不是递归的。广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访为了实现逐层访问，算法中使用了一个队列，以记忆正在访为了实现逐层访问，算法中使用了一个队列，以记忆正在访为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。问的这一层和上一层的顶点，以便于向下一层访问。问的这一层和上一层的顶点，以便于向下一层访问。问的这一层和上一层的顶点，以便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，需要一个辅助与深度优先搜索过程一样，为避免重复访问，需要一个辅助与深度优先搜索过程一样，为避免重复访问，需要一个辅助与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组数组数组数组 visitedvisited ，给被访问过的顶点加标记。，给被访问过的顶点加标记。，给被访问过的顶点加标记。，给被访问过的顶点加标记。44void BFSTraverse(MGraph G,Status(*Visit)(VertexType)int v,j;LinkQueue Q;InitQueue(Q);/置空的辅助队列置空的辅助队列Q for(v=0;vG.vexnum;v+)visitedv=FALSE;/置初值置初值 for(v=0;vG.vexnum;v+)if(!visitedv)visitedv=TRUE;/设置访问标志为设置访问标志为TRUE(已访问已访问)Visit(G.vexsv);EnQueue(Q,v);/v入队列入队列 while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为队头元素出队并置为u 广度优先遍历算法（邻接矩阵表示法）：广度优先遍历算法（邻接矩阵表示法）：45 for(j=0;jG.vexnum;j+)if(G.arcsij=1&!visitedj)visitedj=TRUE;Visit(G.vexsj);EnQueue(Q,j);46例子例子遍历结果：遍历结果：A A、B B、C C、D D476.4 图的连通性图的连通性利用遍历判断一个图是否是连通图利用遍历判断一个图是否是连通图?1.1.无向图的连通性无向图的连通性 count=0;count=0;for(for(图中每个顶点图中每个顶点v)v)if(v if(v未被访问过未被访问过)count+;count+;从从v v出发遍历该图出发遍历该图;if(count=1)cout“if(count=1)cout“连通的连通的”else cout“else cout1)cout1)cout“不连通不连通”;”;else else 从最后被访问的顶点出发逆向从最后被访问的顶点出发逆向dfs;dfs;if(if(全被访问到全被访问到)则是连通的则是连通的;else else 该图不连通该图不连通.49 生成树的定义生成树的定义生成树的定义生成树的定义:n n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n n 个顶点、个顶点、个顶点、个顶点、n-n-1 1 条边。条边。条边。条边。生成树是连通图的极小连通子生成树是连通图的极小连通子图。图。问题：对于给定的连通网络，如何求得其问题：对于给定的连通网络，如何求得其问题：对于给定的连通网络，如何求得其问题：对于给定的连通网络，如何求得其生成树生成树生成树生成树？对含有对含有对含有对含有n n个顶点的连通图个顶点的连通图个顶点的连通图个顶点的连通图GG，从任一顶点出发，从任一顶点出发，从任一顶点出发，从任一顶点出发，作一次深度优先或广度优先遍历，将遍历过程中作一次深度优先或广度优先遍历，将遍历过程中作一次深度优先或广度优先遍历，将遍历过程中作一次深度优先或广度优先遍历，将遍历过程中经过的经过的经过的经过的n-1n-1条边和图中的条边和图中的条边和图中的条边和图中的n n个顶点连接起来构成一个顶点连接起来构成一个顶点连接起来构成一个顶点连接起来构成一个极小连通子图，就是图个极小连通子图，就是图个极小连通子图，就是图个极小连通子图，就是图GG的一棵生成树。的一棵生成树。的一棵生成树。的一棵生成树。用不同的遍历图的方法，可以得到不同的生成用不同的遍历图的方法，可以得到不同的生成用不同的遍历图的方法，可以得到不同的生成用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。树。树。树。6.5 最小生成树最小生成树(minimum cost spanning tree)50最小生成树最小生成树 生成树各边的权值总和称为生成树各边的权值总和称为生成树的权生成树的权。权最小的生成树称为权最小的生成树称为最小生成树最小生成树。最小生成树的应用实例：最小生成树的应用实例：假设要在假设要在n n个城市之间建立通信网。令图个城市之间建立通信网。令图G G的顶点表示的顶点表示城市，边表示连接两个城市的通信线路，边的权值表示城市，边表示连接两个城市的通信线路，边的权值表示通信线路的长度或代价。在通信线路的长度或代价。在n n个城市间构造通信网最少个城市间构造通信网最少需要需要n-1n-1条线路，问：如何选择这条线路，问：如何选择这n-1n-1条边，使得构造这条边，使得构造这个通信网总的代价最小？个通信网总的代价最小？构造最小生成树的准则：构造最小生成树的准则：构造最小生成树的准则：构造最小生成树的准则：必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须使用且仅使用必须使用且仅使用必须使用且仅使用必须使用且仅使用 n n-1 1 条边来联结网络中的条边来联结网络中的条边来联结网络中的条边来联结网络中的 n n 个顶点；个顶点；个顶点；个顶点；不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。51MST MST 性质性质：设设 G=G=（V V，E E）是一个连通网络，）是一个连通网络，U U 是顶点集是顶点集 V V 的一个真子集。若（的一个真子集。若（u u，v v）是）是 G G 中所有的一个中所有的一个顶点在顶点在 U U，另一个顶点不在，另一个顶点不在 U U 的边中，具有最小的边中，具有最小权值的一条边，则一定存在权值的一条边，则一定存在 G G 的一棵最小生成树的一棵最小生成树包括此边。包括此边。uvUVU最小生成树的构造算法：最小生成树的构造算法：52证明证明（反证法）：（反证法）：假设假设 G G 中任何一棵最小生成树都不包含中任何一棵最小生成树都不包含(u(u，v)v)。设设T T是一棵最小生成树但不包含是一棵最小生成树但不包含(u(u，v)v)。由于由于T T是最是最小生成树，所以小生成树，所以 T T 是连通的，因此有一条从是连通的，因此有一条从u u到到v v的的路径，且该路径上必有一条连接两个顶点集路径，且该路径上必有一条连接两个顶点集 U U、V-U V-U 的边的边(u,v)(u,v)，其中其中uUuU，vV-UvV-U。当把边当把边(u(u，v)v)加入到加入到T T中后，得到一个含有边中后，得到一个含有边(u(u，v)v)的回路。的回路。删除边删除边(u,v)(u,v)，上述回路即被消除。由此得到另一上述回路即被消除。由此得到另一棵生成树棵生成树 TT，T T和和TT的区别仅在于用边的区别仅在于用边(u(u，v)v)代替代替了了(u,v)(u,v)。由于由于(u(u，v)v)的权的权=(u,v)=(u,v)的权，所以，的权，所以，TT的权的权=T=T的权，与假设矛盾。的权，与假设矛盾。53普里姆普里姆(Prim)算法算法:基本思想：基本思想：基本思想：基本思想：从连通网络从连通网络从连通网络从连通网络 N N=V V,E E 中的某一顶点中的某一顶点中的某一顶点中的某一顶点 u u0 0 出发，出发，出发，出发，选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边(u u0 0,v v)，将将将将其顶点加入到其顶点加入到其顶点加入到其顶点加入到生成树的顶点集合生成树的顶点集合生成树的顶点集合生成树的顶点集合U U中。中。中。中。以后每一步从以后每一步从以后每一步从以后每一步从一个顶点在一个顶点在一个顶点在一个顶点在U U中中中中，而，而，而，而另一个顶点另一个顶点另一个顶点另一个顶点不在不在不在不在U U中中中中的各条边中选择的各条边中选择的各条边中选择的各条边中选择权值最小的边权值最小的边权值最小的边权值最小的边(u u,v v),把把把把它的顶点加入到它的顶点加入到它的顶点加入到它的顶点加入到集合集合集合集合U U中。如此继续下去，直到中。如此继续下去，直到中。如此继续下去，直到中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合网络中的所有顶点都加入到生成树顶点集合网络中的所有顶点都加入到生成树顶点集合网络中的所有顶点都加入到生成树顶点集合U U中中中中为止。为止。为止。为止。54n n在构造过程中，需引入一个辅助数组：在构造过程中，需引入一个辅助数组：uu closedgeclosedge 用用用用于于于于存存存存放放放放生生生生成成成成树树树树外外外外各各各各顶顶顶顶点点点点(V V中中中中各各各各顶顶顶顶点点点点)到到到到生生生生成成成成树树树树顶顶顶顶点点点点集集集集合合合合内内内内顶顶顶顶点点点点(中中中中各各各各顶顶顶顶点点点点)的各边的当前最小权值；的各边的当前最小权值；的各边的当前最小权值；的各边的当前最小权值；struct VertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;uu 对对于于每每个个顶顶点点v vi iV-U,V-U,在在数数组组closedgeclosedge对对应应一一个相应分量个相应分量closedgeclosedge i-1 i-1。其中：其中：其中：其中：closedgeclosedge i-1 i-1.lowcostlowcost =Min Min cost(cost(v vi i,u)u)|u uU U 55用普里姆算法构造最小生成树的过程用普里姆算法构造最小生成树的过程123465565173254612346551324561.1.从连通网络从连通网络 N N=V V,E E 中的选择任一顶点中的选择任一顶点 u u0 0 加入到生成树的顶点集合加入到生成树的顶点集合中，并为集合中，并为集合V V中的各顶点置最小权值边中的各顶点置最小权值边2.while(生成树生成树T中顶点数目中顶点数目 n)从从集合集合V V中各顶点对应的最小权值边中选取最短中各顶点对应的最小权值边中选取最短边边(u,v);将边将边(u,v)及其在及其在集合集合V V中的顶点中的顶点 v，加到生成加到生成树树 T 中；中；调整调整集合集合V V中各顶点对应的最小权值边；中各顶点对应的最小权值边；Prim Prim 算法框架描述如下：算法框架描述如下：57 void MiniSpanTree_PRIM(MGraph G,VertexType u)int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;/U=u 普里姆算法普里姆算法（邻接矩阵表示法）：（邻接矩阵表示法）：58for(i=1;iG.vexnum;+i)k=minimum(closedge);/求出T的下一个结点 printf(closedgek.adjvex,G.vexsk);/输出生成树的边 closedgek.lowcost=0;/第K顶点并入U集 for(j=0;jG.vexnum;+j)if(G.arcskj.adj closedgej.lowcost)closedgej.lowcost=G.arcskj.adj;59克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法基本思想：基本思想：基本思想：基本思想：设有一个有设有一个有设有一个有设有一个有 n n 个顶点的连通网络个顶点的连通网络个顶点的连通网络个顶点的连通网络 N N=V V,E E ,最初先构造一个只有最初先构造一个只有最初先构造一个只有最初先构造一个只有 n n 个顶点，没有边的非连通个顶点，没有边的非连通个顶点，没有边的非连通个顶点，没有边的非连通图图图图 T T=V V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。当在当在当在当在 E E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的若该边的若该边的若该边的两个顶点落在不同的连通分量上，则将此边加入两个顶点落在不同的连通分量上，则将此边加入两个顶点落在不同的连通分量上，则将此边加入两个顶点落在不同的连通分量上，则将此边加入到到到到 T T 中；否则将此边舍去，重新选择一条权值最中；否则将此边舍去，重新选择一条权值最中；否则将此边舍去，重新选择一条权值最中；否则将此边舍去，重新选择一条权值最小的边。小的边。小的边。小的边。如此重复下去，直到所有顶点在同一个连通如此重复下去，直到所有顶点在同一个连通如此重复下去，直到所有顶点在同一个连通如此重复下去，直到所有顶点在同一个连通分量上为止。分量上为止。分量上为止。分量上为止。60用克鲁斯卡尔算法构造最小生成树的过程用克鲁斯卡尔算法构造最小生成树的过程12346556517325461234655132461克鲁斯卡尔算法的基本思想克鲁斯卡尔算法的基本思想T=(V,)；While (T中所含边数中所含边数 n-1)从从E中选取当前最短边中选取当前最短边(u,v);从从E中删除边中删除边(u,v);i