《数据结构第九章图幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第九章图幻灯片.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第九章图第1页，共43页，编辑于2022年，星期六图的基本概念图的基本概念n n图图(Graph)图是由顶点集合图是由顶点集合图是由顶点集合图是由顶点集合(vertex)及顶点间的关系集及顶点间的关系集合组成的一种数据结构合组成的一种数据结构：n Graph(V,E E)其中其中其中其中:V V=x|x x 某个数据对象某个数据对象某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；是顶点的有穷非空集合；E E=(x,y)|)|x x,y y V 或或 E E=y|x x,y y V V 是顶点之间关系的有穷集合。是顶点之间关系的有穷集合。125
2、634abcd无向图无向图有向图有向图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页，编辑于2022年，星期六ADT Graph 数据对象:D=ai|1i n,n 0,ai属Elemtype类型 数据关系:R1=|ai,aj D,1i n,1j n,每个元素可以有多个直接前驱和可以有多个直接后继 基本运算:InitGraph(t);ClearGraph(t);DSF(t);BSF(t);抽象数据类型数的定义第3页，共43页，编辑于2022年，星期六n n完全图完全
3、图 若有若有 n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n(n n-1)/2 1)/2 条边条边条边条边,则此图为完全无向图。有则此图为完全无向图。有则此图为完全无向图。有则此图为完全无向图。有 n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图有n n(n-1)条边条边,则此图为完全有向图。则此图为完全有向图。则此图为完全有向图。则此图为完全有向图。abc1234邻接顶点邻接顶点 如果如果(u u,v v)是是 E E(G)(G)中的一条边，则中的一条边，则中的一条边，则中的一条边，则称称称称 u 与与与与 v v 互为邻接顶点互为邻接
4、顶点互为邻接顶点互为邻接顶点。例：存在例：存在(1,2)，则顶点，则顶点1与与2互为邻接点。互为邻接点。存在存在,则顶点则顶点a与与b互为邻接点。互为邻接点。第4页，共43页，编辑于2022年，星期六125634abcd 顶点的度顶点的度 一个顶点一个顶点v v的度是与它相关联的边的条的度是与它相关联的边的条数。记作数。记作TD(TD(v v)。在有向图中在有向图中在有向图中在有向图中,顶点的度顶点的度顶点的度顶点的度=入度入度入度入度+出度。出度。出度。出度。顶点顶点 v v 的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v v);顶点顶点
5、顶点顶点 v v 的出度的出度 是以是以是以是以 v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记记记记作作作作 OD(OD(v v)。TD(TD(v v)=ID(v)+OD()+OD(v v)例：例：TD(1)=3 TD(4)=4 TD(5)=2例：例：TD(b)=ID(b)+OD(b)TD(d)=ID(d)+OD(d)=2+1=3=2+3=5第5页，共43页，编辑于2022年，星期六n n子图子图 设有两个图设有两个图设有两个图设有两个图 G G(V V,E E)和和和和 G G(V V,E)。若。若。若。若 V V 且且且且 E E E,则称则称则
6、称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。0123子图子图0130123023 权权 某些图的边具有与它相某些图的边具有与它相某些图的边具有与它相某些图的边具有与它相关的数关的数关的数关的数,称为权。这种带权称为权。这种带权称为权。这种带权称为权。这种带权图叫做网络。图叫做网络。图叫做网络。图叫做网络。任意图都是其自身子图任意图都是其自身子图abcd 8 1 93 4 11 23第6页，共43页，编辑于2022年，星期六n n路径路径 在图在图在图在图 G G(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出出出出发发发发,沿
7、一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点 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 v vj j)为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的路径的路径的路径的路径。125634例：例：V1到到V3的路径：的路径：123 、123423、16423、1544.路径长度路径长度 非带权图的路径长度是指此路径上边的条数。带权非带权图的路
8、径长度是指此路径上边的条数。带权非带权图的路径长度是指此路径上边的条数。带权非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。图的路径长度是指路径上各边的权之和。图的路径长度是指路径上各边的权之和。图的路径长度是指路径上各边的权之和。简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上各顶点 v v1 1,v v2 2,.,.,v vm m 均不均不均不均不 互相重复互相重复互相重复互相重复,则则则则称这样的路径为简单路径。称这样的路径为简单路径。称这样的路径为简单路径。称这样的路径为简单路径。回路回路 若路径上第一个顶点若路径上第一个顶点若路径上
9、第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v vm m 重合重合重合重合,则称则称则称则称这样的路径为回路或环。这样的路径为回路或环。这样的路径为回路或环。这样的路径为回路或环。路径长度：路径长度：2 、5 、4 、3 .第7页，共43页，编辑于2022年，星期六n n连通图与连通分量连通图与连通分量 在无向图中在无向图中在无向图中在无向图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径,则称则称则称则称顶点顶点顶点顶点v v1 1与与与与v v2 2是连通的是连通的是连通的是
10、连通的。如果图中任意一对顶点都是连如果图中任意一对顶点都是连如果图中任意一对顶点都是连如果图中任意一对顶点都是连通的通的通的通的,则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连通子图叫做非连通图的极大连通子图叫做非连通图的极大连通子图叫做非连通图的极大连通子图叫做连通分连通分连通分连通分量量量量。生成树生成树 一个连通图的生成树是其一个连通图的生成树是其一个连通图的生成树是其一个连通图的生成树是其极小连通子图极小连通子图极小连通子图极小连通子图。n n个顶点个顶点个顶点个顶点、n n-1 1条边条边条边条边、连通子图连通子图连通子图连通子图。12563441
11、532连通图连通图非连通图非连通图两个连通分量两个连通分量125634125634第8页，共43页，编辑于2022年，星期六 强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中在有向图中在有向图中,若对于每一对顶若对于每一对顶若对于每一对顶若对于每一对顶点点点点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都存在一条从v vi i到到到到v vj j和从和从和从和从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此图是强强强强连通图连通图连通图连通图。非强连通图的极大强连通子图叫做。非强连通图的极大强连通子图叫做。
12、非强连通图的极大强连通子图叫做。非强连通图的极大强连通子图叫做强连通分量强连通分量强连通分量强连通分量。abcd abcd 强连通图强连通图非强连通图非强连通图cabd 两个强连通分量两个强连通分量第9页，共43页，编辑于2022年，星期六图的存储表示图的存储表示邻接矩阵邻接矩阵(Adjacency Matrix)aij=abef cd vexs1 2 3 4 5 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 存储顶点存储顶点基本思想：基本思想：利
13、用矩阵利用矩阵A表示顶点之间的关系表示顶点之间的关系无向图的邻接矩阵是对称矩阵第10页，共43页，编辑于2022年，星期六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 8419826263310 7107A=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邻接矩阵所占存邻接矩阵所占存储空间与顶点
14、数储空间与顶点数成正比成正比但图中有无关但图中有无关系都分配存储系都分配存储空间空间边的插入和删除不边的插入和删除不影响存储空间大小影响存储空间大小0100？求顶点的度？求顶点的度第11页，共43页，编辑于2022年，星期六邻接矩阵的数据类型邻接矩阵的数据类型A=vexs1 2 3 4Typedef enumDG,DN,UDG,UDN Graphkind;typedef struct ArcCell VRType adj;/*各顶点之间的关系或权值各顶点之间的关系或权值*/InfoType *info;ArcCell,AdjMatrixMAXVMAXV;typedef struct Verte
15、xType vexsMAXV;/*存储顶点元素存储顶点元素*/AdjMatrix arcs;int vexnum,arcnum;/*顶点数，弧数顶点数，弧数*/Graphkind kind;Mgraph;第12页，共43页，编辑于2022年，星期六建立邻接矩阵建立邻接矩阵*邻接矩阵初始化（置邻接矩阵初始化（置0或或 ）*输入顶点数，弧数输入顶点数，弧数 ga-vexnum ga-arcnum*输入各顶点信息存入输入各顶点信息存入ga-vexs*输入各边信息（或权值）存入输入各边信息（或权值）存入ga-arcsarcsvexs1 2 3 4第13页，共43页，编辑于2022年，星期六邻接表邻接表
16、(Adjacency List)n n基本思想：基本思想：在无向图中，将依附于某个顶点的所在无向图中，将依附于某个顶点的所在无向图中，将依附于某个顶点的所在无向图中，将依附于某个顶点的所有边有边有边有边（边结点）（边结点）（边结点）（边结点）以单链表形式链接，每个链表设立以单链表形式链接，每个链表设立一个一个表头结点表头结点表头结点表头结点。abef cd123456 abcdef(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 da
17、ta 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页，编辑于2022年，星期六 data firstarc1234abcd 8 5 93 7 11 13邻接表：邻接表：在有向图中，将以该顶点作为在有向图中，将以该顶点作为弧弧尾顶点尾顶点的所有弧链接成单链表。的所有弧链接成单链表。abcd 2 8 4 74 91
18、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页，编辑于2022年，星期六邻接表的结点结构和数据类型邻接表的结点结构和数据类型 data firstarc表头结点表头结点typedef struct ArcNode int adjvex;/*邻接点存储序号邻接点存储序号*/infoType info;/*若是网络存储权值若
19、是网络存储权值*/struct ArcNode *nextarc;/*指向下一个边结点指向下一个边结点*/ArcNode;typedef struct Vertex data;/*存储顶点元素存储顶点元素*/Arcnode *firstarc;/*指向依附于该顶点的第一边指向依附于该顶点的第一边*/VNode,AdjListMAXV;typedef struct AdjList vertices;int vexnum,arcnum;int kind;ALGraph;adjvex nextarc边结点边结点adjvex info nextarc第16页，共43页，编辑于2022年，星期六 dat
20、a 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*输入各边信息，生成新结点，插入相应的单链中。输入各边信息，生成新结点，插入相应的单链中。第17页，共43页，编辑于2022年，星期六abcd 8 5 93 7 11 13
21、data firstarc1234abcd 2 8 4 74 91 3 1 5 2 11 3 13邻接表的基本操作邻接表的基本操作插入：插入：*确定单链表确定单链表*生成新结点生成新结点63 6*头插链表头插链表注：注：有向图只插入有向图只插入(或删除）一个结点，而或删除）一个结点，而无向图需插入（或删除）两个结点。无向图需插入（或删除）两个结点。删除：删除：*确定结点确定结点*删除结点删除结点*释放结点释放结点 第18页，共43页，编辑于2022年，星期六十字链表十字链表(有向图有向图)abcd 8 5 93 7 11 13a a a b a c a d a 1 2 a 1 4a 2 4 a
22、 3 1 a 4 1 a 4 2 a 4 3 tailvex headvex hlink tlink info弧结点弧结点data firstin firstout顶点结点顶点结点第19页，共43页，编辑于2022年，星期六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 ivex ilink jvex jlink边结点边结点 data firstedge顶点结点顶点结点第
23、20页，共43页，编辑于2022年，星期六图的遍历图的遍历 (Graph Traversal)n n图的遍历图的遍历从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一 些边访遍图些边访遍图些边访遍图些边访遍图中所有的顶点，且使每个顶点仅被访问一次。中所有的顶点，且使每个顶点仅被访问一次。中所有的顶点，且使每个顶点仅被访问一次。中所有的顶点，且使每个顶点仅被访问一次。为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组 visited visited
24、标志标志标志标志各顶点是否被访问过各顶点是否被访问过各顶点是否被访问过各顶点是否被访问过。图的遍历的分类：图的遍历的分类：深度优先深度优先深度优先深度优先搜索搜索搜索搜索 DFS(Depth First Search)DFS(Depth First Search)广度优先搜索广度优先搜索广度优先搜索广度优先搜索 BFS(Breadth First Search)BFS(Breadth First Search)第21页，共43页，编辑于2022年，星期六12563478深度优先搜索深度优先搜索DFS(Depth First Search)visited1 2 3 4 5 6 7 8DFS基本思
25、想：基本思想：*访问顶点访问顶点v0。*依次从依次从v0未被访问的邻接点出发未被访问的邻接点出发进行深度优先搜索遍历。进行深度优先搜索遍历。遍历序列：遍历序列：1231256414521426264545262653178177383883733780 0 0 0 0 0 0 011111111注：注：访问访问v0的邻接点与访问的邻接点与访问v0方方法一样，用递归方式实现。法一样，用递归方式实现。12563478DFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问，则从则从w出发进行遍历出发进行遍历DFS(w)(4)确定
26、下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 第22页，共43页，编辑于2022年，星期六DFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问，则从则从w出发进行遍历出发进行遍历DFS(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 深度优先搜索深度优先搜索DFS(Depth First Search)DFS(v0)visite(v0);visitedv0=1;w=FIRST(v0);whi
27、le(存在存在w)if (visitedv0=0)DFS(w);w=NEXT(v0,w);第23页，共43页，编辑于2022年，星期六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页，编辑于2022年，星期六广度优先搜索广度优先搜索 BFS(Bre
28、adth First Search)12563478BFS基本思想：基本思想：*访问顶点访问顶点v0。*依次访问依次访问v0未被访问的邻接点未被访问的邻接点*依次从这些邻接点出发进行广度依次从这些邻接点出发进行广度优先搜索遍历。优先搜索遍历。注：为了从已访问的邻接点出发，设置队列保存结点注：为了从已访问的邻接点出发，设置队列保存结点visited1 2 3 4 5 6 7 8遍历序列：遍历序列：1 2 3 4 5 7 8 612223334445 557 7 7 888队列队列0 0 0 0 0 0 0 0666111111111112563478第25页，共43页，编辑于2022年，星期六B
29、FS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)顶点顶点v0入队列入队列(3)取出队头取出队头v 确定第一邻接点确定第一邻接点w 若若w未访问，未访问，则访问则访问w，w入队列。入队列。确定下一个邻接点确定下一个邻接点w 重复重复 直到所有邻接点都处理直到所有邻接点都处理(4)重复重复(3)直到队列空。直到队列空。广度优先广度优先搜索搜索BFS(Breadth First Search)BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue(Q,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);whil
30、e(存在存在w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NEXT(v,w);第26页，共43页，编辑于2022年，星期六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);125634 data firstarc123456abcdef 562 3 1 4 2
31、4 3 5 6 2 4 1 1 4第一邻接点:p=gav0.firstarc下一个邻接点：p=p-nextarc第27页，共43页，编辑于2022年，星期六深度优先搜索深度优先搜索DFS(Depth First Search)深度优先搜索过程的示例深度优先搜索过程的示例ACDEGBFIHACDEGBFIH123456791234567889深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树前进回退第28页，共43页，编辑于2022年，星期六广度优先搜索广度优先搜索BFS(Breadth First Search)n n广度优先搜索的示例广度优先搜索的示例ACDEGBFIH12345
32、6789123456789广度优先搜索过程广度优先搜索过程 ACDEGBFHI广度优先生成树广度优先生成树第29页，共43页，编辑于2022年，星期六 问题：问题：当对非连通图遍历时当对非连通图遍历时当对非连通图遍历时当对非连通图遍历时,从图中某一顶点出发从图中某一顶点出发从图中某一顶点出发从图中某一顶点出发,利用利用利用利用深度优先搜索算法或广度优先搜索算法不可能遍历到图深度优先搜索算法或广度优先搜索算法不可能遍历到图深度优先搜索算法或广度优先搜索算法不可能遍历到图深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点中的所有顶点中的所有顶点中的所有顶点,只能访问到该顶点所在的最大连通
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页，共43页，编辑于2022年，星
34、期六ACDEBFGIHJONMLK非连通无向图ACDEBFGHIJKONML非连通图的连通分量n n对于非连通的无向图，所有连通分量的生成树组成对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。了非连通图的生成森林。第31页，共43页，编辑于2022年，星期六ACDEBFGIHJONMLK非连通无向图ACDEBFGIHJONMLK非连通图的连通分量第32页，共43页，编辑于2022年，星期六1624351624351624351251042312104312542深度优先搜索遍历广度优先搜索遍历遍历序列遍历序列:123456遍历序列遍历序列:125634连连通通图图生生成成树树
35、不同的遍历得到不同的生成树不同的遍历得到不同的生成树权值之和权值之和:20权值之和权值之和:14第33页，共43页，编辑于2022年，星期六最小生成树最小生成树(minimum cost spanning tree)最小生成树最小生成树-在一个连通网得到的所有生成树中在一个连通网得到的所有生成树中,权值之和最小的生成树称为最小生成树权值之和最小的生成树称为最小生成树.3564257156146352n n使用且仅使用该网络中的使用且仅使用该网络中的使用且仅使用该网络中的使用且仅使用该网络中的n n-1 1 条边条边条边条边来联结网络中的来联结网络中的来联结网络中的来联结网络中的 n n 个必须
36、顶点；个必须顶点；个必须顶点；个必须顶点；n n不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；n n各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。应用应用:在若干个城市中建立通讯网。在若干个城市中建立通讯网。第34页，共43页，编辑于2022年，星期六MST性质：性质：设设G=G=（V,EV,E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的一的一个子集。若（个子集。若（u,vu,v）是）是G G中所有的一个端点在中所有的一个端点在U U（即（即u u U U）里，）里
37、，另一个端点不在另一个端点不在U U（即（即v v V-U V-U）里的边中，具有最小权值的一条边，）里的边中，具有最小权值的一条边，则一定存在则一定存在G G的一棵最小生成树包含此边的一棵最小生成树包含此边（u,vu,v）。）。UV-U反正法证明：反正法证明：假设假设G中任何一棵最小生中任何一棵最小生成树中都不包含边成树中都不包含边（u,vu,v）。）。vuvu设设T T是一棵最小生成树，不包（是一棵最小生成树，不包（u,vu,v）,一定要包含一条边（一定要包含一条边（u u,v,v）。）。若用（若用（u,vu,v）取代（）取代（u u,v,v）得到一棵新的）得到一棵新的生成树生成树T T,
38、由于由于W W（u,vu,v）W W（u,vu,v），则），则T T的权的权TT的权，与假设矛盾。的权，与假设矛盾。第35页，共43页，编辑于2022年，星期六535642571561463525461356242361657 756643255普里姆普里姆(Prim)算法算法 基本思想：基本思想：基本思想：基本思想：设连通网络设连通网络设连通网络设连通网络 N N=(=(V V,E E)，最小生成树最小生成树最小生成树最小生成树T=(U,TE)T=(U,TE)（1 1）初始状态：）初始状态：）初始状态：）初始状态：U=vU=v0 0,TE=,TE=。（2 2）选择满足）选择满足）选择满足）选
39、择满足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。第36页，共43页，编辑于2022年，星期六55351246142360657 755632143564257156035241 0 6 1 5 6 0 5 3 1 5 0 7
40、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。当当lowcosti 0:顶点顶点i未被吸收未被吸收V-U。当当0lowcosti：存储存储顶点顶点i与顶点与顶点closesti之间的权值。之间的权值。当当lowcosti
41、=：顶点顶点i未与已吸收的顶点之间没有关系（边）。未与已吸收的顶点之间没有关系（边）。第37页，共43页，编辑于2022年，星期六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(j=0;jn;j+)if(lowcostj!=0&costkjvi可达的距离0 10 2 记录到达vi的路径1 1 1 1 1 1 1
42、最小最小(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页，编辑于2022年，星期六小小 结结一、图的定义：一、图的定义：G=(V,E)G=(V,E)二、图的逻辑结构：非线性结构二、图的逻辑结构：非线性结构 多多-多多三、图的概念及术语：有向图与无向图三、图的概念及术语：有向图与无向图 邻接点，顶点的度，子图，网络，路径及路径长度邻接点，顶点的度，子图，网络，路径及路径长度 连通图与连通分量（无），强连通图与强连通分量连通图与连通分量（无），强连通图与强连通分量四、图的存储结构：邻接矩阵法、邻接表法、四、图的存储结构：邻接矩阵法、邻接表法、十字链表和多重邻接表十字链表和多重邻接表五、图的遍历：深度优先搜索遍历和广度优先搜索遍历五、图的遍历：深度优先搜索遍历和广度优先搜索遍历六、图的应用：最小生成树、最短路径六、图的应用：最小生成树、最短路径第43页，共43页，编辑于2022年，星期六