数据结构第九章图精品文稿.ppt

《数据结构第九章图精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构第九章图精品文稿.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第九章图第1页，本讲稿共43页图的基本概念图的基本概念n n图图(Graph)图是由顶点集合图是由顶点集合图是由顶点集合图是由顶点集合(vertex)及顶点间的关系集及顶点间的关系集及顶点间的关系集及顶点间的关系集合组成的一种数据结构合组成的一种数据结构合组成的一种数据结构合组成的一种数据结构：n GraphGraph(V V,E E)其中其中其中其中:V V=x x|x x 某个数据对象某个数据对象某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；E E=(=(x x,y y)|)|x x,y y V V 或或或或 E

2、E=y|x x,y y V V 是顶点之间关系的有穷集合。是顶点之间关系的有穷集合。是顶点之间关系的有穷集合。是顶点之间关系的有穷集合。125634abcd无向图无向图有向图有向图V=1,2,3,4E=(1,2),(1,5),(1,6),(2,3),(2,4),(3,4),(4,5),(4,6)（边）（边）V=a,b,c,dE=,（弧（弧）第2页，本讲稿共43页ADT Graph 数据对象:D=ai|1i n,n 0,ai属Elemtype类型 数据关系:R1=|ai,aj D,1i n,1j n,每个元素可以有多个直接前驱和可以有多个直接后继 基本运算:InitGraph(t);ClearG

3、raph(t);DSF(t);BSF(t);抽象数据类型数的定义第3页，本讲稿共43页n n完全图完全图 若有若有若有若有 n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n(n n-1)/2 1)/2 条边条边条边条边,则此图为完全无向图。有则此图为完全无向图。有则此图为完全无向图。有则此图为完全无向图。有 n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图有n n(n n-1)1)条条条条边边边边,则此图为完全有向图。则此图为完全有向图。则此图为完全有向图。则此图为完全有向图。abc1234邻接顶点邻接顶点邻接顶点邻接顶点 如果如果如果如果

4、 (u u,v v)是是是是 E E(G)(G)中的一条边，则中的一条边，则中的一条边，则中的一条边，则称称称称 u u 与与与与 v v 互为邻接顶点互为邻接顶点互为邻接顶点互为邻接顶点。例：存在例：存在(1,2)，则顶点，则顶点1与与2互为邻接点。互为邻接点。存在存在,则顶点则顶点a与与b互为邻接点。互为邻接点。第4页，本讲稿共43页125634abcd 顶点的度顶点的度 一个顶点一个顶点一个顶点一个顶点v v的度是与它相关联的边的条数。的度是与它相关联的边的条数。的度是与它相关联的边的条数。的度是与它相关联的边的条数。记作记作记作记作TD(TD(v v)。在有向图中在有向图中在有向图中在

5、有向图中,顶点的度顶点的度顶点的度顶点的度=入度入度入度入度+出度。出度。出度。出度。顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(ID(v v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度 是以是以是以是以 v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记作记作 OD(OD(v v)。TD(TD(v v)=ID()=ID(v v)+OD()+OD(v v)例：例：TD(1)=3 TD(4)=4 T

6、D(5)=2例：例：TD(b)=ID(b)+OD(b)TD(d)=ID(d)+OD(d)=2+1=3=2+3=5第5页，本讲稿共43页n n子图子图 设有两个图设有两个图设有两个图设有两个图 G G(V V,E E)和和和和 G G(V V,E E)。若若若若 V V V V 且且且且 E E E E,则称则称则称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。0123子图子图0130123023 权权 某些图的边具有与它相某些图的边具有与它相某些图的边具有与它相某些图的边具有与它相关的数关的数关的数关的数,称为权。这种带权称为权。这种带权称为权。这种带权称为权

7、。这种带权图叫做网络。图叫做网络。图叫做网络。图叫做网络。任意图都是其自身子图任意图都是其自身子图abcd 8 1 93 4 11 23第6页，本讲稿共43页n n路径路径 在图在图在图在图 G G(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发,沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点到达顶点到达顶点到达顶点v vj j。则称顶点序列则称顶点序列则称顶点序列则称顶点序列 (v vi i v vp p1 1 v vp p2 2.v vpm pm

8、v vj j)为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的路的路的路的路径径径径。125634例：例：V1到到V3的路径：的路径：123 、123423、16423、1544.路径长度路径长度 非带权图的路径长度是指此路径上边的条数。带权图非带权图的路径长度是指此路径上边的条数。带权图非带权图的路径长度是指此路径上边的条数。带权图非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。的路径长度是指路径上各边的权之和。的路径长度是指路径上各边的权之和。的路径长度是指路径上各边的权之和。简单路径简单路径 若路径上各顶点若路径上各

9、顶点若路径上各顶点若路径上各顶点 v v1 1,v v2 2,.,.,v vm m 均不均不均不均不 互相重复互相重复互相重复互相重复,则则则则称这样的路径为简单路径。称这样的路径为简单路径。称这样的路径为简单路径。称这样的路径为简单路径。回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v vm m 重合重合重合重合,则称则称则称则称这样的路径为回路或环。这样的路径为回路或环。这样的路径为回路或环。这样的路径为回路或环。路径长度：路径长度：2 、5 、4 、3 .第7页，本讲稿共43页n

10、n连通图与连通分量连通图与连通分量 在无向图中在无向图中在无向图中在无向图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径,则称则称则称则称顶点顶点顶点顶点v v1 1与与与与v v2 2是连通的是连通的是连通的是连通的。如果图中任意一对顶点都如果图中任意一对顶点都如果图中任意一对顶点都如果图中任意一对顶点都是连通的是连通的是连通的是连通的,则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连通子图叫做非连通图的极大连通子图叫做非连通图的极大连通子图叫做非连通图的极大连通子图叫做连连连连通分量通分量通分量

11、通分量。生成树生成树 一个连通图的生成树是其一个连通图的生成树是其一个连通图的生成树是其一个连通图的生成树是其极小连通子图极小连通子图极小连通子图极小连通子图。n n个顶点个顶点个顶点个顶点、n n-1 1条边条边条边条边、连通子图连通子图连通子图连通子图。12563441532连通图连通图非连通图非连通图两个连通分量两个连通分量125634125634第8页，本讲稿共43页 强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中在有向图中在有向图中,若对于每一对若对于每一对若对于每一对若对于每一对顶点顶点顶点顶点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都

12、存在一条从v vi i到到到到v vj j和从和从和从和从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此图是强强强强连通图连通图连通图连通图。非强连通图的极大强连通子图叫做。非强连通图的极大强连通子图叫做。非强连通图的极大强连通子图叫做。非强连通图的极大强连通子图叫做强连通分量强连通分量强连通分量强连通分量。abcd abcd 强连通图强连通图非强连通图非强连通图cabd 两个强连通分量两个强连通分量第9页，本讲稿共43页图的存储表示图的存储表示邻接矩阵邻接矩阵(Adjacency Matrix)aij=abef cd vexs1 2 3 4 5

13、 6 a b c d e f A=0 1 0 0 1 11 0 1 1 0 00 1 0 1 0 00 1 1 0 1 11 0 0 1 0 01 0 0 1 0 0利用数组利用数组vertex 存储顶点存储顶点基本思想：基本思想：利用矩阵利用矩阵A表示顶点之间的关系表示顶点之间的关系无向图的邻接矩阵是对称矩阵第10页，本讲稿共43页aij=A=abcd 8 1 93 4 11 23 vexs1 2 3 4A=a b c d 1111111000000000A=abef cd vexs1 2 3 4 5 6 a b c d e f 4 8 2 19 6 7 3 1084931 11 23419

14、84198262633107107A=0 1 0 0 1 11 0 1 1 0 00 1 0 1 0 00 1 1 0 1 11 0 0 1 0 01 0 0 1 0 0邻接矩阵所占存邻接矩阵所占存储空间与顶点数储空间与顶点数成正比成正比但图中有无但图中有无关系都分配关系都分配存储空间存储空间边的插入和删除边的插入和删除不影响存储空间不影响存储空间大小大小0100？求顶点的度？求顶点的度第11页，本讲稿共43页邻接矩阵的数据类型邻接矩阵的数据类型A=vexs1 2 3 4Typedef enumDG,DN,UDG,UDN Graphkind;typedef struct ArcCell VRT

15、ype adj;/*各顶点之间的关系或权值各顶点之间的关系或权值*/InfoType *info;ArcCell,AdjMatrixMAXVMAXV;typedef struct VertexType vexsMAXV;/*存储顶点元素存储顶点元素*/AdjMatrix arcs;int vexnum,arcnum;/*顶点数，弧数顶点数，弧数*/Graphkind kind;Mgraph;第12页，本讲稿共43页建立邻接矩阵建立邻接矩阵*邻接矩阵初始化（置邻接矩阵初始化（置0或或 ）*输入顶点数，弧数输入顶点数，弧数 ga-vexnum ga-arcnum*输入各顶点信息存入输入各顶点信息存

16、入ga-vexs*输入各边信息（或权值）存入输入各边信息（或权值）存入ga-arcsarcsvexs1 2 3 4第13页，本讲稿共43页邻接表邻接表(Adjacency List)n n基本思想：基本思想：在无向图中，将依附于某个顶点的在无向图中，将依附于某个顶点的在无向图中，将依附于某个顶点的在无向图中，将依附于某个顶点的所有边所有边所有边所有边（边结点）（边结点）（边结点）（边结点）以单链表形式链接，每个链表设以单链表形式链接，每个链表设以单链表形式链接，每个链表设以单链表形式链接，每个链表设立一个立一个立一个立一个表头结点表头结点表头结点表头结点。abef cd123456 abcde

17、f(a,b)(a,e)(a,f)256(b,a)(b,c)(b,d)1 3 4(c,b)(c,d)2 4(d,b)(d,c)(d,e)(d,f)2 3 5 6 (e,a)(e,d)(f,a)(f,d)1 41 4 data firstarc 4 8 2 19 6 7 3 104 8 198 7 4 2 6adjvex info nextarc3 6 10 7 2 319 10adjvex nextarc注：在注：在无向图无向图中每中每个边生成两个结点个边生成两个结点？插入和删除？插入和删除(d,f)=(f,d)?求顶点的度求顶点的度第14页，本讲稿共43页 data firstarc1234a

18、bcd 8 5 93 7 11 13邻接表：邻接表：在有向图中，将以该顶点作为在有向图中，将以该顶点作为弧尾弧尾顶点顶点的所有弧链接成单链表。的所有弧链接成单链表。abcd 2 8 4 74 91 3 1 5 2 11 3 13 data firstarc1234 abcd 3 3 4 5 4 13 1 8 4 111 7 4 9逆逆邻邻接接表表逆邻接表：逆邻接表：在有向图中，将以在有向图中，将以该顶点作为该顶点作为弧头顶弧头顶点点的所有弧链接成的所有弧链接成单链表。单链表。？求顶点的度？求顶点的度第15页，本讲稿共43页邻接表的结点结构和数据类型邻接表的结点结构和数据类型 data firs

19、tarc表头结点表头结点typedef struct ArcNode int adjvex;/*邻接点存储序号邻接点存储序号*/infoType info;/*若是网络存储权值若是网络存储权值*/struct ArcNode *nextarc;/*指向下一个边结点指向下一个边结点*/ArcNode;typedef struct Vertex data;/*存储顶点元素存储顶点元素*/Arcnode *firstarc;/*指向依附于该顶点的第一边指向依附于该顶点的第一边*/VNode,AdjListMAXV;typedef struct AdjList vertices;int vexnum,

20、arcnum;int kind;ALGraph;adjvex nextarc边结点边结点adjvex info nextarc第16页，本讲稿共43页 data firstarcadjvex info nextarc123456 abcdef256 1 3 4 2 4 2 3 5 6 1 41 44 8 198 7 4 2 63 6 10 7 2 319 10abef cd 4 8 2 19 6 7 3 10建立邻接表建立邻接表*邻接表初始化邻接表初始化（置各单链表为空表（置各单链表为空表 ga.firstarc=NULL）*输入各顶点信息存入输入各顶点信息存入 ga.data*输入各边信息，

21、生成新结点，插入相应的单链中。输入各边信息，生成新结点，插入相应的单链中。第17页，本讲稿共43页abcd 8 5 93 7 11 13 data firstarc1234abcd 2 8 4 74 91 3 1 5 2 11 3 13邻接表的基本操作邻接表的基本操作插入：插入：*确定单链表确定单链表*生成新结点生成新结点63 6*头插链表头插链表注：注：有向图只插入有向图只插入(或删除）一个结点，或删除）一个结点，而无向图需插入（或删除）两个结点。而无向图需插入（或删除）两个结点。删除：删除：*确定结点确定结点*删除结点删除结点*释放结点释放结点 第18页，本讲稿共43页十字链表十字链表(有

22、向图有向图)abcd 8 5 93 7 11 13a a a b a c a d a 1 2 a 1 4a 2 4 a 3 1 a 4 1 a 4 2 a 4 3 tailvex headvex hlink tlink info弧结点弧结点data firstin firstout顶点结点顶点结点第19页，本讲稿共43页a 4 6(d,f)abef cd 4 8 2 19 6 7 3 10A BCDEFa 1 2(a,b)a 1 5(a,e)a 1 6(a,f)a 2 3(b,c)a 2 4(b,d)a 3 4(c,d)a 4 5(d,e)邻接多重表邻接多重表（无向图）（无向图）mark iv

23、ex ilink jvex jlink边结点边结点 data firstedge顶点结点顶点结点第20页，本讲稿共43页图的遍历图的遍历 (Graph Traversal)n n图的遍历图的遍历从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一 些边访遍图中些边访遍图中些边访遍图中些边访遍图中所有的顶点，且使每个顶点仅被访问一次。所有的顶点，且使每个顶点仅被访问一次。所有的顶点，且使每个顶点仅被访问一次。所有的顶点，且使每个顶点仅被访问一次。为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的

24、辅助数组为了避免重复访问，设置一个的辅助数组 visited visited 标志标志标志标志各各各各顶点是否被访问过顶点是否被访问过顶点是否被访问过顶点是否被访问过。图的遍历的分类：图的遍历的分类：深深深深度优先搜索度优先搜索度优先搜索度优先搜索 DFS(Depth First Search)DFS(Depth First Search)广度优先搜索广度优先搜索广度优先搜索广度优先搜索 BFS(Breadth First Search)BFS(Breadth First Search)第21页，本讲稿共43页12563478深度优先搜索深度优先搜索DFS(Depth First Search

25、)visited1 2 3 4 5 6 7 8DFS基本思想：基本思想：*访问顶点访问顶点v0。*依次从依次从v0未被访问的邻接点出发未被访问的邻接点出发进行深度优先搜索遍历。进行深度优先搜索遍历。遍历序列：遍历序列：1231 256414521426264545262653178177383883733780 0 0 0 0 0 0 01111111 1注：注：访问访问v0的邻接点与访问的邻接点与访问v0方法一样，用递归方式实现。方法一样，用递归方式实现。12563478DFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未

26、访问，则从则从w出发进行遍历出发进行遍历DFS(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 第22页，本讲稿共43页DFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问，则从则从w出发进行遍历出发进行遍历DFS(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 深度优先搜索深度优先搜索深度优先搜索深度优先搜索DFS(Depth First Search)DFS(v0)visit

27、e(v0);visitedv0=1;w=FIRST(v0);while(存在存在w)if (visitedv0=0)DFS(w);w=NEXT(v0,w);第23页，本讲稿共43页125634 data firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4DFS(v0)visite(v0);visitedv0=1;w=FIRST(v0);while(存在存在w)if (visitedv0=0)DFS(w);w=NEXT(v0,w);第一邻接点:p=gav0.firstarc下一个邻接点：p=p-nextarc第24页，本讲稿共43页广度优先搜索广

28、度优先搜索广度优先搜索广度优先搜索 BFS(Breadth First Search)12563478BFS基本思想：基本思想：*访问顶点访问顶点v0。*依次访问依次访问v0未被访问的邻接点未被访问的邻接点*依次从这些邻接点出发进行广度依次从这些邻接点出发进行广度优先搜索遍历。优先搜索遍历。注：为了从已访问的邻接点出发，设置队列保存结点注：为了从已访问的邻接点出发，设置队列保存结点visited1 2 3 4 5 6 7 8遍历序列：遍历序列：1 2 3 4 5 7 8 612 223 334445557 7 7 888队列队列0 0 0 0 0 0 0 06661111 1111111256

29、3478第25页，本讲稿共43页BFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)顶点顶点v0入队列入队列(3)取出队头取出队头v 确定第一邻接点确定第一邻接点w 若若w未访问，未访问，则访问则访问w，w入队列。入队列。确定下一个邻接点确定下一个邻接点w 重复重复 直到所有邻接点都处理直到所有邻接点都处理(4)重复重复(3)直到队列空。直到队列空。广度优先广度优先广度优先广度优先搜索搜索BFS(Breadth First Search)BFS(Breadth First Search)BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue

30、(Q,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);while(存在存在w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NEXT(v,w);第26页，本讲稿共43页BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue(Q,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);while(存在存在w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NEXT(v,w);12563

31、4 data firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4第一邻接点:p=gav0.firstarc下一个邻接点：p=p-nextarc第27页，本讲稿共43页深度优先搜索深度优先搜索DFS(Depth First Search)深度优先搜索过程的示例深度优先搜索过程的示例ACDEGBFIHACDEGBFIH123456791234567889深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树前进回退第28页，本讲稿共43页广度优先搜索广度优先搜索BFS(Breadth First Search)n n广度优先搜索的示例广度优

32、先搜索的示例ACDEGBFIH123456789123456789广度优先搜索过程广度优先搜索过程 ACDEGBFHI广度优先生成树广度优先生成树第29页，本讲稿共43页 问题：问题：当对非连通图遍历时当对非连通图遍历时当对非连通图遍历时当对非连通图遍历时,从图中某一顶点出发从图中某一顶点出发从图中某一顶点出发从图中某一顶点出发,利用深度优先搜索算法或广度优先搜索算法不可能遍利用深度优先搜索算法或广度优先搜索算法不可能遍利用深度优先搜索算法或广度优先搜索算法不可能遍利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点历到图中的所有顶点历到图中的所有顶点历到图中的所有顶点,只能访问到

33、该顶点所在的最大只能访问到该顶点所在的最大只能访问到该顶点所在的最大只能访问到该顶点所在的最大连通子图连通子图连通子图连通子图(连通分量连通分量连通分量连通分量)的所有顶点。的所有顶点。的所有顶点。的所有顶点。ACDEBFGIHJONMLK非连通无向图要实现任意图的遍历，则要扫描图中的所有顶点。TRQVER()for(i=1;i=n;i+)visitedi=0;for(i=1;i=n;i+)if(visitedi=0)DFS(vi);TRQVER()for(i=1;i=n;i+)visitedi=0;for(i=1;i=n;i+)if(visitedi=0)BFS(vi);第30页，本讲稿共4

34、3页ACDEBFGIHJONMLK非连通无向图ACDEBFGHIJKONML非连通图的连通分量n n对于非连通的无向图，所有连通分量的生成树组成了对于非连通的无向图，所有连通分量的生成树组成了对于非连通的无向图，所有连通分量的生成树组成了对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。非连通图的生成森林。非连通图的生成森林。非连通图的生成森林。第31页，本讲稿共43页ACDEBFGIHJONMLK非连通无向图ACDEBFGIHJONMLK非连通图的连通分量第32页，本讲稿共43页1624351624351624351251042312104312542深度优先搜索遍历广度优先

35、搜索遍历遍历序列遍历序列:123456遍历序列遍历序列:125634连连通通图图生生成成树树不同的遍历得到不同的生成树不同的遍历得到不同的生成树权值之和权值之和:20权值之和权值之和:14第33页，本讲稿共43页最小生成树最小生成树(minimum cost spanning tree)最小生成树最小生成树最小生成树最小生成树-在一个连通网得到的所有生成树中在一个连通网得到的所有生成树中在一个连通网得到的所有生成树中在一个连通网得到的所有生成树中,权权权权值之和最小的生成树称为最小生成树值之和最小的生成树称为最小生成树值之和最小的生成树称为最小生成树值之和最小的生成树称为最小生成树.35642

36、57156146352n n使用且仅使用该网络中的使用且仅使用该网络中的使用且仅使用该网络中的使用且仅使用该网络中的n n-1 1 条条条条边来联结网络中的边来联结网络中的边来联结网络中的边来联结网络中的 n n 个必须顶点；个必须顶点；个必须顶点；个必须顶点；n n不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；n n各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。应用应用:在若干个城市中建立通讯网。在若干个城市中建立通讯网。第34页，本讲稿共43页MST性质：性质：设设G=G=（V,EV

37、,E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的一个子集。若（的一个子集。若（u,vu,v）是）是G G中所有的一个端点在中所有的一个端点在U U（即（即u u U U）里，另一个端点不在）里，另一个端点不在U U（即（即v v V-U V-U）里的边中，）里的边中，具有最小权值的一条边，则一定存在具有最小权值的一条边，则一定存在G G的一棵最小生成树的一棵最小生成树包含此边包含此边（u,vu,v）。）。UV-U反正法证明：反正法证明：假设假设G中任何一棵最中任何一棵最小生成树中都不包含边小生成树中都不包含边（u,vu,v）。）。vuvu设设T T是一棵最小生成树，不包是

38、一棵最小生成树，不包（u,vu,v）,一定要包含一条边一定要包含一条边（u u,v,v）。）。若用（若用（u,vu,v）取代（）取代（u u,v,v）得到一棵）得到一棵新的生成树新的生成树T T,由于由于W W（u,vu,v）W W（u,vu,v），则），则T T的权的权TT的权，与假设矛的权，与假设矛盾。盾。第35页，本讲稿共43页535642571561463525461356242361657 756643255普里姆普里姆(Prim)算法算法 基本思想：基本思想：基本思想：基本思想：设连通网络设连通网络设连通网络设连通网络 N N=(=(V V,E E)，最小生成树最小生成树最小生成树

39、最小生成树T=(U,TE)T=(U,TE)（1 1）初始状态：）初始状态：）初始状态：）初始状态：U=vU=v0 0,TE=,TE=。（2 2）选择满足）选择满足）选择满足）选择满足MSTMST性质的一条边（性质的一条边（性质的一条边（性质的一条边（u,u,v v）,其中其中其中其中u u U U，v v V-UV-U，且边，且边（u,vu,v）的权值最小。的权值最小。的权值最小。的权值最小。（3 3）吸收）吸收）吸收）吸收v vU U,吸收吸收吸收吸收（u,vu,v）TETE。（4 4）重复（）重复（）重复（）重复（2 2）（）（）（）（3 3），直到），直到），直到），直到U=VU=V。第

40、36页，本讲稿共43页55351246142360657 755632143564257156035241 0 6 1 5 6 0 5 3 1 5 0 7 5 4 5 7 0 2 3 5 0 6 4 2 6 0cost lowcost closest 0 6 1 5 0 0 0 0 0 0最小5540最小222最小最小2050034 0 1 2 3 4 5cost :利用邻接矩阵法存储图利用邻接矩阵法存储图 i=j:costij=0 closest 和和lowcost 分别存储顶点序号和权值，分别存储顶点序号和权值，当当lowcosti=0:顶点顶点i已经吸收到已经吸收到U。当当lowcost

41、i 0:顶点顶点i未被吸收未被吸收V-U。当当0lowcosti：存储存储顶点顶点i与顶点与顶点closesti之间的权值。之间的权值。当当lowcosti=：顶点顶点i未与已吸收的顶点之间没有关系（边）。未与已吸收的顶点之间没有关系（边）。第37页，本讲稿共43页prim(cost,n,v)for(i=0;in;i+)lowcosti=costvi;closesti=v;for(i=1;in;i+)min=;for(j=0;jn;j+)if(lowcostj!=0&lowcostjmin)min=lowcostj;k=j;输出输出(closestk,k,min);lowcostk=0;for

42、(j=0;jn;j+)if(lowcostj!=0&costkjvi可达的距离0 10 2 记录到达vi的路径1 1 1 1 1 1 1最小最小(Si=0)121修正修正:distmin+costminidisti?013 3043最小最小(Si=0)143084 010 4最小最小(Si=0)184095 015 5最小最小(Si=0)195最小最小(Si=0)110 4 013 6 113 6path=13467第42页，本讲稿共43页小小 结结一、图的定义：一、图的定义：G=(V,E)G=(V,E)二、图的逻辑结构：非线性结构二、图的逻辑结构：非线性结构 多多-多多三、图的概念及术语：有向图与无向图三、图的概念及术语：有向图与无向图 邻接点，顶点的度，子图，网络，路径及路径长度邻接点，顶点的度，子图，网络，路径及路径长度 连通图与连通分量（无），强连通图与强连通分量连通图与连通分量（无），强连通图与强连通分量四、图的存储结构：邻接矩阵法、邻接表法、四、图的存储结构：邻接矩阵法、邻接表法、十字链表和多重邻接表十字链表和多重邻接表五、图的遍历：深度优先搜索遍历和广度优先搜索遍历五、图的遍历：深度优先搜索遍历和广度优先搜索遍历六、图的应用：最小生成树、最短路径六、图的应用：最小生成树、最短路径第43页，本讲稿共43页