数据结构第9章图学习教案.pptx

《数据结构第9章图学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第9章图学习教案.pptx（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)第第9章图章图第一页，共58页。图的基本概念图的基本概念n n图图(Graph)图是由顶点集合图是由顶点集合(vertex)及顶及顶点间的关系集合组成的一种数据结构点间的关系集合组成的一种数据结构(sh j ji u)：n n Graph(V,E)n n其中其中:V=x|x 某个数据对象某个数据对象是顶点是顶点的有穷非空集合；的有穷非空集合；n n E=(x,y)|x,y V n n或或 E=|x,y V是顶点之间关是顶点之间关系的有穷集合。系的有穷集合。125634abcd无向无向(w xin)图图有向图有向图V=1,2,3,4,5,6E=(1,

2、2),(1,5),(1,6),(2,3),(2,4),(3,4),(4,5),(4,6)（边）（边）V=a,b,c,dE=,（弧）（弧）第1页/共58页第二页，共58页。ADT Graph 数据对象数据对象:D=ai|1i n,n 0,ai属属Elemtype类型类型 数据关系数据关系:R1=|ai,aj D,1i n,1j n,每个元素可以有多个直接前驱和可以每个元素可以有多个直接前驱和可以有多个直接后继有多个直接后继 基本基本(jbn)运算运算:InitGraph(t);ClearGraph(t);DSF(t);BSF(t);抽象数据类型数的定义(dngy)第2页/共58页第三页，共58页

3、。n n完全完全(wnqun)(wnqun)图图 若有若有 n n 个个顶点的无向图有顶点的无向图有 n(n-1)/2 n(n-1)/2 条条边边,则此图为完全则此图为完全(wnqun)(wnqun)无无向图。有向图。有 n n 个顶点的有向图有个顶点的有向图有n(n-1)n(n-1)条边条边,则此图为完全则此图为完全(wnqun)(wnqun)有向图。有向图。abc1234邻接顶点邻接顶点邻接顶点邻接顶点 如果如果如果如果(u,v)(u,v)是是是是 E(G)E(G)中中中中的一条的一条的一条的一条(y tio)(y tio)边，则称边，则称边，则称边，则称 u u 与与与与 v v 互为互

4、为互为互为邻接顶点。邻接顶点。邻接顶点。邻接顶点。例：存在例：存在例：存在例：存在(1,2)(1,2)，则顶点，则顶点，则顶点，则顶点1 1与与与与2 2互为邻互为邻互为邻互为邻接点。接点。接点。接点。存在存在存在存在,则顶点则顶点则顶点则顶点a a与与与与b b互为邻接互为邻接互为邻接互为邻接点。点。点。点。第3页/共58页第四页，共58页。125634abcdn n顶点的度顶点的度顶点的度顶点的度 一个一个一个一个(y)(y)顶点顶点顶点顶点v v的度是与它相的度是与它相的度是与它相的度是与它相关联的边的条数。记作关联的边的条数。记作关联的边的条数。记作关联的边的条数。记作TD(v)TD(

5、v)。n n在有向图中在有向图中在有向图中在有向图中,顶点的度顶点的度顶点的度顶点的度=入度入度入度入度+出度。出度。出度。出度。n n顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点为终点为终点为终点(zhngdin)(zhngdin)的有向的有向的有向的有向边的条数边的条数边的条数边的条数,记作记作记作记作 ID(v);ID(v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度 是以是以是以是以 v v 为为为为始点的有向边的条数始点的有向边的条数始点的有向边的条数始点的有向边的条数,记作记作记作记作 OD(v)OD(v)。TD(v)=ID(v)+O

6、D(v)TD(v)=ID(v)+OD(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第4页/共58页第五页，共58页。n n子图子图 设有两个设有两个(lin)图图 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。0123子图子图0130123023n n权权权权 某些图的边具有某些图的边具有某些图的边具有某些图的边具有与它相关的数与它相关的数与它相关的数与它相关的数,称为称为称为称为(chn wi)(chn wi)权。这

7、权。这权。这权。这种带权图叫做网络。种带权图叫做网络。种带权图叫做网络。种带权图叫做网络。任意图任意图(yt)都是其自身子图都是其自身子图abcd 8 1 93 4 11 23第5页/共58页第六页，共58页。n n路径路径(ljng)在图在图 G(V,E)中中,若从若从顶点顶点 vi 出发出发,沿一沿一些边经过一些顶点些边经过一些顶点 vp1,vp2,vpm，到达顶点到达顶点vj。则称顶。则称顶点序列点序列(vi vp1 vp2.vpm vj)为从顶点为从顶点vi 到顶点到顶点 vj 的路径的路径(ljng)。125634例：例：V1到到V3的路径的路径(ljng)：123 、123423、

8、16423、1544.n n路径路径路径路径(ljng)(ljng)长度长度长度长度 非带权图的路径非带权图的路径非带权图的路径非带权图的路径(ljng)(ljng)长度是指此路径长度是指此路径长度是指此路径长度是指此路径(ljng)(ljng)上边的条上边的条上边的条上边的条数。带权图的路径数。带权图的路径数。带权图的路径数。带权图的路径(ljng)(ljng)长度是指路径长度是指路径长度是指路径长度是指路径(ljng)(ljng)上各边的权之和。上各边的权之和。上各边的权之和。上各边的权之和。n n简单路径简单路径简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上各顶点

9、v v11,v v22,.,.,v vm m 均不均不均不均不 互相重复互相重复互相重复互相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。n n回路回路回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v vm m 重合重合重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。则称这样的路径为回路或环。路径长度：路径长度：2 、5 、4 、3 .第6页/共58页第七页，共58页。n n连通图与连

10、通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则则称顶点称顶点v1与与v2是连通的。如果是连通的。如果图中任意一对顶点都是连通的图中任意一对顶点都是连通的,则称此图是连通图。非连通图则称此图是连通图。非连通图的极大的极大(j d)连通子图叫做连连通子图叫做连通分量。通分量。n n生成树生成树生成树生成树 一个连通图的生一个连通图的生一个连通图的生一个连通图的生成树是其极小成树是其极小成树是其极小成树是其极小(j xio)(j xio)连连连连通子图。通子图。通子图。通子图。n n个顶点、个顶点、个顶点、个顶点、n-1n-1条条条条边、连通子图。

11、边、连通子图。边、连通子图。边、连通子图。12563441532连通连通(lintng)图图非连通图非连通图两个连通分量两个连通分量125634125634第7页/共58页第八页，共58页。n n强连通强连通强连通强连通(lintng)(lintng)图与强连通图与强连通图与强连通图与强连通(lintng)(lintng)分量分量分量分量 在有向图中在有向图中在有向图中在有向图中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点vivi和和和和vj,vj,都存在一条从都存在一条从都存在一条从都存在一条从vivi到到到到vjvj和从和从和从和从vjvj到到到到vivi的的的的路径

12、路径路径路径,则称此图是强连通则称此图是强连通则称此图是强连通则称此图是强连通(lintng)(lintng)图。图。图。图。非强连通非强连通非强连通非强连通(lintng)(lintng)图的极大强连通图的极大强连通图的极大强连通图的极大强连通(lintng)(lintng)子图叫做强连通子图叫做强连通子图叫做强连通子图叫做强连通(lintng)(lintng)分分分分量。量。量。量。abcd abcd 强连通强连通(lintng)图图非强连通非强连通(lintng)图图cabd 两个强连通分量两个强连通分量第8页/共58页第九页，共58页。图的存储图的存储(cn(cn ch)ch)表示表示

13、邻接矩阵邻接矩阵(Adjacency Matrix)(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 存储存储(cn ch)顶点顶点基本思想：利用基本思想：利用(lyng)矩阵矩阵A表示顶点之间的关系表示顶点之间的关系无向图的邻接矩阵是对称矩阵第9页/共58页第十页，共58页。aij=A=abcd 8 1 93 4 11 23 vexs1 2 3 4A=a b c

14、d 1111111000 0 00 0 00A=abef cd vexs1 2 3 4 5 6 a b c d e f 4 8 2 19 6 7 3 1084931 11 23419 841982 62633107107A=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邻接矩阵所占存邻接矩阵所占存储空间与顶点储空间与顶点(dngdin)数成数成正比正比但图中有无但图中有无(yu w)关系关系都分配存储空都分配存储空间间边的插入边的插入(ch r)和删除不影响存储和删除不影响存储空间大小空间大小0100？求顶点

15、的度？求顶点的度第10页/共58页第十一页，共58页。邻接矩阵的数据类型邻接矩阵的数据类型A=vexs1 2 3 4typedef struct int no;InfoType info;VertexTtypetypedef struct int edgesMAXVMAXV;/*各顶点各顶点(dngdin)之间的关系或权值之间的关系或权值*/int n,e;/*顶点顶点(dngdin)数，边（或弧）的个数数，边（或弧）的个数*/VertexType vexsMAXV;/*存储顶点存储顶点(dngdin)元素元素*/MGraph;第11页/共58页第十二页，共58页。建立建立(jinl)邻接矩阵

16、邻接矩阵*邻接矩阵初始化（置邻接矩阵初始化（置0或或 ）*输入输入(shr)顶点数，弧数顶点数，弧数 ga-n ga-e*输入输入(shr)各顶点信息存入各顶点信息存入ga-vexs*输入输入(shr)各边信息（或权值）存入各边信息（或权值）存入ga-edages A=vexs1 2 3 4第12页/共58页第十三页，共58页。邻接邻接邻接邻接(ln ji)(ln ji)表表表表 (Adjacency List)(Adjacency List)n n基本基本(jbn)思想：在无向图中，思想：在无向图中，将依附于某个顶点的所有边将依附于某个顶点的所有边（边结点）以单链表形式链接，（边结点）以单链

17、表形式链接，每个链表设立一个表头结点。每个链表设立一个表头结点。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 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注：在无向图中每个边生成两个结点注：在无向图中每个边生成两个结点？插入？插入(ch r)和删

18、除和删除(d,f)=(f,d)?求顶点的度求顶点的度第13页/共58页第十四页，共58页。data firstarc1234abcd 8 5 93 7 11 13邻接表：在有向图中，将以该顶点邻接表：在有向图中，将以该顶点作为作为(zuwi)弧尾顶点的所有弧链弧尾顶点的所有弧链接成单链表。接成单链表。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逆逆邻邻接接表表逆邻接表：逆邻接表：在有向图中，在有向图中，将以该顶点将以该顶点(dngdin)作作为弧头顶点为弧头顶点(dngd

19、in)的的所有弧链接成所有弧链接成单链表。单链表。？求顶点？求顶点(dngdin)的度的度第14页/共58页第十五页，共58页。邻接邻接(ln ji)表的结点结构和数据类型表的结点结构和数据类型 data firstarc表头结点表头结点typedef struct ANode int adjvex;/*邻接邻接(ln ji)点存储序号点存储序号*/InfoType info;/*若是网络存储权值若是网络存储权值*/struct ANode *nextarc;/*指向下一个边结点指向下一个边结点*/ArcNode;typedef struct Vertex data;/*存储顶点存储顶点(dn

20、gdin)元素元素*/ArcNode *firstarc;/*指向依附于该顶点指向依附于该顶点(dngdin)的第一边的第一边*/VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist;int n,e;ALGraph;adjvex nextarc边结点边结点adjvex info nextarc第15页/共58页第十六页，共58页。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

21、 319 10abef cd 4 8 2 19 6 7 3 10建立邻接表建立邻接表*邻接表初始化（置各单链表为空表邻接表初始化（置各单链表为空表 ga.firstarc=NULL）*输入各顶点信息输入各顶点信息(xnx)存入存入 ga.data*输入各边信息输入各边信息(xnx)，生成新结点，插入相应的单链中。，生成新结点，插入相应的单链中。第16页/共58页第十七页，共58页。abcd 8 5 93 7 11 13 data firstarc1234abcd 2 8 4 74 91 3 1 5 2 11 3 13邻接邻接(ln ji)表的基本操作表的基本操作插入插入(ch r)：*确定确定

22、(qudng)单链表单链表*生成新结点生成新结点63 6*头插链表头插链表注：注：有向图只插入有向图只插入(或删除）一个结点，而无向图需插入（或删除）两个结点。或删除）一个结点，而无向图需插入（或删除）两个结点。删除：删除：*确定结点确定结点*删除结点删除结点*释放结点释放结点 第17页/共58页第十八页，共58页。十字十字十字十字(sh z)(sh z)链表链表链表链表(有有有有向图向图向图向图)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 t

23、link info弧结点弧结点data firstin firstout顶点结点顶点结点第18页/共58页第十九页，共58页。data firstin firstout顶点结点顶点结点tailvex headvex hlink tlink info弧结点弧结点typedef struct ArcNode int tailvex,headvex;struct ArcNode*hlink,*tlink;InfoType info;ArcNode;typedef struct VexNode VertexType data;ArcNode*firstin,*firstout;VexNode;十字十字

24、(sh z)链表的数据类型链表的数据类型第19页/共58页第二十页，共58页。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)邻接邻接邻接邻接(ln(ln ji)ji)多重表多重表多重表多重表（无向图）（无向图）（无向图）（无向图）mark ivex ilink jvex jlink边结点边结点 data firstedge顶点结点顶点结点第20页/共58页第二十一页，共58页。data firstedge顶点结点顶点结

25、点 mark ivex ilink jvex jlink边结点边结点typedef struct ENode int mark;int ivex,jvex;struct ENode*ilink,*jlink;InfoType info;ENode;邻接邻接(ln ji)多重表的数据类型多重表的数据类型typedef struct VNode VertexType data;ENode*firstedge;VNode;第21页/共58页第二十二页，共58页。图的遍历图的遍历(bin l)(Graph(bin l)(Graph Traversal)Traversal)n n图的遍历从图中某一顶点出

26、发，图的遍历从图中某一顶点出发，沿着一沿着一 些边访遍图中所有些边访遍图中所有(suyu)的顶点，且使每个顶的顶点，且使每个顶点仅被访问一次。点仅被访问一次。n n为了避免重复访问，设置一个的辅助为了避免重复访问，设置一个的辅助为了避免重复访问，设置一个的辅助为了避免重复访问，设置一个的辅助(fzh)(fzh)数组数组数组数组 visited visited 标志各顶点是否被访问过。标志各顶点是否被访问过。标志各顶点是否被访问过。标志各顶点是否被访问过。n n图的遍历的分类：图的遍历的分类：图的遍历的分类：图的遍历的分类：深度优先搜索深度优先搜索深度优先搜索深度优先搜索 DFS(Depth F

27、irst Search)DFS(Depth First Search)广度优先搜索广度优先搜索广度优先搜索广度优先搜索 BFS(Breadth First Search)BFS(Breadth First Search)第22页/共58页第二十三页，共58页。12563478深度优先深度优先深度优先深度优先(yuxin)(yuxin)搜索搜索搜索搜索DFS(Depth First Search)DFS(Depth First Search)visited1 2 3 4 5 6 7 8DFS基本思想：基本思想：*访问顶点访问顶点v0。*依次从依次从v0未被访问的邻接点出发进未被访问的邻接点出发进

28、行深度行深度(shnd)优先搜索遍历。优先搜索遍历。遍历遍历(bin l)序列：序列：1231256414521426264545262653178177383883733780 0 0 0 0 0 0 01 111111 1注：注：访问访问v0的邻接点与访问的邻接点与访问v0方法一样，用递归方式实现。方法一样，用递归方式实现。12563478DFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问，则从则从w出发进行遍历出发进行遍历DFS(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点

29、都处理结束直到所有邻接点都处理结束 第23页/共58页第二十四页，共58页。DFS(v0)的主要的主要(zhyo)步骤：步骤：(1)访问顶点访问顶点v0(2)确定第一邻接点确定第一邻接点w(3)若若w未访问，未访问，则从则从w出发进行遍历出发进行遍历DFS(w)(4)确定下一个邻接点确定下一个邻接点w(5)重复重复(3)(4)直到所有邻接点都处理结束直到所有邻接点都处理结束 深度深度深度深度(shnd)(shnd)优先搜索优先搜索优先搜索优先搜索DFS(Depth First Search)DFS(Depth First Search)DFS(v0)visite(v0);visitedv0=1

30、;w=FIRST(v0);while(存在存在(cnzi)w)if (visitedw=0)DFS(w);w=NEXT(v0,w);第24页/共58页第二十五页，共58页。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(存在存在(cnzi)w)if (visitedv0=0)DFS(w);w=NEXT(v0,w);第一(dy)邻接点:p=G-adjlistv.firstarc下一个(y)邻接点：p=p-nextarc第25页

31、/共58页第二十六页，共58页。广度广度广度广度(gungd)(gungd)优先搜索优先搜索优先搜索优先搜索 BFS(Breadth First Search)BFS(Breadth First Search)12563478BFS基本思想：基本思想：*访问顶点访问顶点v0。*依次依次(yc)访问访问v0未被访问的邻未被访问的邻接点接点*依次依次(yc)从这些邻接点出发从这些邻接点出发进行广度优先搜索遍历。进行广度优先搜索遍历。注：为了从已访问的邻接点出发，设置队列注：为了从已访问的邻接点出发，设置队列(duli)保存结点保存结点visited1 2 3 4 5 6 7 8遍历序列：遍历序列：

32、1 2 3 4 5 7 8 612 223334 445557 7 7 888队列队列0 0 0 0 0 0 0 066611 1 111 111 112563478第26页/共58页第二十七页，共58页。BFS(v0)的主要步骤：的主要步骤：(1)访问顶点访问顶点v0(2)顶点顶点v0入队列入队列(3)取出队头取出队头v 确定第一邻接点确定第一邻接点w 若若w未访问，未访问，则访问则访问w，w入队列。入队列。确定下一个确定下一个(y)邻接点邻接点w 重复重复 直到所有邻接点都处理直到所有邻接点都处理(4)重复重复(3)直到队列空。直到队列空。广度优先广度优先广度优先广度优先(yuxin)(y

33、uxin)搜索搜索搜索搜索BFS(Breadth First Search)BFS(Breadth First Search)BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue(Q,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);while(存在存在(cnzi)w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NEXT(v,w);第27页/共58页第二十八页，共58页。BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue(Q

34、,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);while(存在存在(cnzi)w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NEXT(v,w);125634 data firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4第一(dy)邻接点:p=G-adjlistv.firstarc下一个(y)邻接点：p=p-nextarc第28页/共58页第二十九页，共58页。深深深深度度度度(shnd)(shnd)优优优优先先先先搜搜搜搜索索索索DFS DFS

35、(Depth Depth First First Search)Search)n n深度优先搜索过程深度优先搜索过程(guchng)的示例的示例ACDEGBFIHACDEGBFIH123456791234567889深度优先搜索深度优先搜索(su su)过程过程 深度优先生成树深度优先生成树前进回退第29页/共58页第三十页，共58页。广广广广度度度度优优优优先先先先(yuxin)(yuxin)搜搜搜搜索索索索BFS BFS(Breadth Breadth First First Search)Search)n n广度优先搜索广度优先搜索广度优先搜索广度优先搜索(su(su susu)的示例的

36、示例的示例的示例ACDEGBFIH123456789123456789广度优先广度优先(yuxin)搜索过程搜索过程 ACDEGBFHI广度优先生成树广度优先生成树第30页/共58页第三十一页，共58页。问题：当对非连通图遍历时问题：当对非连通图遍历时问题：当对非连通图遍历时问题：当对非连通图遍历时,从图中某一顶点从图中某一顶点从图中某一顶点从图中某一顶点出发出发出发出发(chf),(chf),利用深度优先搜索算法或广度优利用深度优先搜索算法或广度优利用深度优先搜索算法或广度优利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点先搜索算法不可能遍历到图中的所有顶点先搜索算法不可能遍

37、历到图中的所有顶点先搜索算法不可能遍历到图中的所有顶点,只只只只能访问到该顶点所在的最大连通子图能访问到该顶点所在的最大连通子图能访问到该顶点所在的最大连通子图能访问到该顶点所在的最大连通子图(连通分连通分连通分连通分量量量量)的所有顶点。的所有顶点。的所有顶点。的所有顶点。ACDEBFGIHJONMLK非连通(lintng)无向图要实现任意图的遍历，则要扫描图中的所有(suyu)顶点。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;

38、for(i=1;i=n;i+)if(visitedi=0)BFS(vi);第31页/共58页第三十二页，共58页。ACDEBFGIHJONMLK非连通无向图ACDEBFGHIJKONML非连通(lintng)图的连通(lintng)分量n n对于非连通对于非连通对于非连通对于非连通(lintng)(lintng)的无向图，所有连通的无向图，所有连通的无向图，所有连通的无向图，所有连通(lintng)(lintng)分量的生成树组成了非连通分量的生成树组成了非连通分量的生成树组成了非连通分量的生成树组成了非连通(lintng)(lintng)图的生成森林。图的生成森林。图的生成森林。图的生成森林

39、。第32页/共58页第三十三页，共58页。ACDEBFGIHJONMLK非连通无向图ACDEBFGIHJONMLK非连通(lintng)图的连通(lintng)分量第33页/共58页第三十四页，共58页。1624351624351624351251042312104312542深度(shnd)优先搜索遍历广度(gungd)优先搜索遍历遍历遍历(bin l)序列序列:123456遍历序列遍历序列:125634连连通通图图生生成成树树不同的遍历得到不同的生成树不同的遍历得到不同的生成树权值之和权值之和:20权值之和权值之和:14第34页/共58页第三十五页，共58页。最小生成最小生成最小生成最小生

40、成(shn(shn chn chn)树树树树 (minimum cost spanning tree)(minimum cost spanning tree)最小生成树最小生成树最小生成树最小生成树-在一个连通在一个连通在一个连通在一个连通(lintng)(lintng)(lintng)(lintng)网得到的所有网得到的所有网得到的所有网得到的所有生成树中生成树中生成树中生成树中,权值之和最小的生成树称为最小生成权值之和最小的生成树称为最小生成权值之和最小的生成树称为最小生成权值之和最小的生成树称为最小生成树树树树.3564257156146352nn使用且仅使用该网络中的使用且仅使用该网络

41、中的使用且仅使用该网络中的使用且仅使用该网络中的n-1 n-1 条边来联结网络中的条边来联结网络中的条边来联结网络中的条边来联结网络中的 n n 个必须顶点个必须顶点个必须顶点个必须顶点(dngdin)(dngdin)；nn不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；nn各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。应用应用:在若干个城市中建立通讯网。在若干个城市中建立通讯网。第35页/共58页第三十六页，共58页。MST性质：设性质：设G=（V,E）是一个连通网络）是一个连通网络(w

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

43、v）,一定要包含一条边（一定要包含一条边（u,vu,v）。）。若用（若用（u,vu,v）取代（）取代（u u,v,v）得到一棵新的生成树）得到一棵新的生成树T T,由于由于W W（u,vu,v）W W（u,vu,v），则），则T T的权的权TT的权，与假设矛盾。的权，与假设矛盾。第36页/共58页第三十七页，共58页。535642571561463525461356242361657 756643255普里姆普里姆普里姆普里姆(Prim)(Prim)算法算法算法算法(sun f)(sun f)nn基本思想：基本思想：基本思想：基本思想：nn 设连通网络设连通网络设连通网络设连通网络 N=(V,

44、E)N=(V,E)，nn 最小生成树最小生成树最小生成树最小生成树T=(U,TE)T=(U,TE)nn（1 1）初始状态：）初始状态：）初始状态：）初始状态：U=v0,TE=U=v0,TE=。nn（2 2）选择）选择）选择）选择(xunz)(xunz)满足满足满足满足MSTMST性质的一条边（性质的一条边（性质的一条边（性质的一条边（u,vu,v）,其中其中其中其中u uU U，v v V-UV-U，且边（，且边（，且边（，且边（u,vu,v）的权值最小。）的权值最小。）的权值最小。）的权值最小。nn（3 3）吸收）吸收）吸收）吸收v vU,U,吸收（吸收（吸收（吸收（u,vu,v）TETE。

45、nn（4 4）重复（）重复（）重复（）重复（2 2）（）（）（）（3 3），直到），直到），直到），直到U=VU=V。第37页/共58页第三十八页，共58页。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 :利用利用(lyng)邻接矩阵法存储图邻接矩阵法存储图 i=j:costij=0 closest

46、 和和lowcost 分别存储顶点分别存储顶点(dngdin)序号和权值，序号和权值，当当lowcosti=0:顶点顶点(dngdin)i已经吸收到已经吸收到U。当当lowcosti0:顶点顶点(dngdin)i未被吸收未被吸收V-U。当当0lowcostivi可达的距离0 10 2 记录(jl)到达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

47、6path=13467第42页/共58页第四十三页，共58页。10432101003050206010V0V1 V0V1 10V0V3 V0V3 30V0V2 V0V3 V2 50V0V4 V0V3 V2 V4 50第43页/共58页第四十四页，共58页。拓扑拓扑(tu p)排序排序(Topological Sort)(AOV网网)n n计划计划计划计划(jhu)(jhu)、施工过程、生产流程、程序流程等、施工过程、生产流程、程序流程等、施工过程、生产流程、程序流程等、施工过程、生产流程、程序流程等都是都是都是都是“工程工程工程工程”。除了很小的工程外，一般都把工。除了很小的工程外，一般都把工

48、。除了很小的工程外，一般都把工。除了很小的工程外，一般都把工程分为若干个叫做程分为若干个叫做程分为若干个叫做程分为若干个叫做“活动活动活动活动”的子工程。完成了这的子工程。完成了这的子工程。完成了这的子工程。完成了这些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。n n例如，计算机专业学生的学习就是一个工程，每例如，计算机专业学生的学习就是一个工程，每例如，计算机专业学生的学习就是一个工程，每例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中一门课程的学习就是整个工程的一些活动。其中一门课

49、程的学习就是整个工程的一些活动。其中一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有些课程要求先修课程，有些则不要求。这样在有些课程要求先修课程，有些则不要求。这样在有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地有的课程之间有领先关系，有的课程可以并行地有的课程之间有领先关系，有的课程可以并行地有的课程之间有领先关系，有的课程可以并行地学习。学习。学习。学习。第44页/共58页第四十五页，共58页。C1 C1 高等数学高等数学高等数学高等数学 C2 C2 程序设计程序设计程序设计程序设计(chn x sh j)(chn

50、 x sh j)基础基础基础基础 C3 C3 离散数学离散数学离散数学离散数学 C1,C2 C1,C2 C4 C4 数据结构数据结构数据结构数据结构 C3,C2 C3,C2 C5 C5 高级语言程序设计高级语言程序设计高级语言程序设计高级语言程序设计(chn x sh j)C2(chn x sh j)C2 C6 C6 编译方法编译方法编译方法编译方法 C5,C4 C5,C4 C7 C7 操作系统操作系统操作系统操作系统 C4,C9 C4,C9 C8 C8 普通物理普通物理普通物理普通物理 C1 C1 C9 C9 计算机原理计算机原理计算机原理计算机原理 C8 C8 C8C3C5C4C9C6C7