华东理工大学数据结构第7章.ppt

《华东理工大学数据结构第7章.ppt》由会员分享，可在线阅读，更多相关《华东理工大学数据结构第7章.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的基本概念图的基本概念 图的存储结构图的存储结构 图的遍历图的遍历 最小生成树最小生成树2002-11-121mmmm7.1图的基本概念图的基本概念图定义图定义图是由顶点集合图是由顶点集合(vertex)及顶点间的关及顶点间的关系系边（或者弧边（或者弧)集合组成的一种数据结构集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象是顶点的有穷是顶点的有穷非空集合；非空集合；E=或或(v,w)|v,w V 是顶点之间关系的有穷集合，谓词是顶点之间关系的有穷集合，谓词P(v,w)定义了定义了弧弧的意义或信息的意义或信息,谓词是用来刻划个体词的性谓词是用来刻划个体

2、词的性谓词是用来刻划个体词的性谓词是用来刻划个体词的性质或事物之间关系的词质或事物之间关系的词质或事物之间关系的词质或事物之间关系的词.2002-11-122mmmm 有向图与无向图有向图与无向图 若图若图G G中的每条边都是有方中的每条边都是有方向向的，则称的，则称G G为为有向图有向图。有向边也称为。有向边也称为弧弧。若图。若图G G中的每条边都是没有方向中的每条边都是没有方向(x,y)的，的，则称则称G G为为无向图无向图.(x,y)称为边。称为边。V1V1V3V3V4V4V5V5V2V2V4V4V3V3V2V2V1V1无向图无向图无向图无向图G1G1有向图有向图有向图有向图G2G2G2

3、=(V2,E2)G2=(V2,E2)V2=v1,v2,v3,v4V2=v1,v2,v3,v4E2=,E2=,G1=G1=(V V,E E)集合集合集合集合V Vv1,v2,v3,v4,v5v1,v2,v3,v4,v5 集合集合集合集合E E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。2002-11-123mmmm权权权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权称之为权。在实际应用中，权值可以有某种含义。比如，在实际应用中，权值

4、可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。到后一个工程所需要的时间等等。带权图叫做网带权图叫做网。有向网、无向网。有向网、无向网。2002-11-124mmmm12356874ABDCE10

5、796671231516603045358040752002-11-125mmmm完全图完全图 对有对有n n个顶点的图，若为有向图个顶点的图，若为有向图且边数为且边数为n(n-1)n(n-1)，则称其为则称其为有向完全图有向完全图。若为无向图且边数为若为无向图且边数为n(n-1)/2n(n-1)/2，则称其则称其为为无向完全图无向完全图；边或弧数；边或弧数 nlognnlogn为为稀疏稀疏图图，反之为，反之为稠密图稠密图 邻接顶点邻接顶点 在无向图中，若（在无向图中，若（v vi i,v vj j）是一是一条边，则称顶点条边，则称顶点v vi i和和v vj j互为互为邻接点邻接点，或称，或

6、称v vi i和和v vj j相邻接相邻接，并称边（，并称边（v vi i,v vj j）关联于顶关联于顶点点v vi i和和v vj j，或称或称（v vi i,v vj j）与顶点与顶点v vi i和和v vj j相相关联关联。在有向图中，若有。在有向图中，若有 ,称v vi i邻接到邻接到v vj j，弧弧 关联于顶点关联于顶点v vi i和和v vj j.2002-11-126mmmmn n顶点的度顶点的度顶点的度顶点的度 一个顶点一个顶点一个顶点一个顶点v v的度是与它相关联的边的条的度是与它相关联的边的条的度是与它相关联的边的条的度是与它相关联的边的条数。数。数。数。记作记作记作记

7、作TD(TD(v v)。顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(ID(v v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以是以是以 v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记作记作 OD(OD(v v)。n n子图子图子图子图 设有两个图设有两个图设有两个图设有两个图 GG(V V,E E)和和和和 GG(V V,E E)。若若若若 V V V V 且且且且 E E E E,则称

8、则称则称则称 图图图图GG是是是是 图图图图GG的子图的子图的子图的子图。52002-11-127mmmm 路径路径路径路径 在图在图 G G(V V,E E)中中,若存在一个顶点序列若存在一个顶点序列 v vp p1 1,v vp p2 2,v vpmpm，使得使得(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)均属于均属于E E，则称顶点则称顶点v vi i到到v vj j存在一存在一 条路径。若一条路径上除了条路径。若一条路径上除了v vi i 和和v vj j 可以相同外，可以相同外，其余顶点均不相同，则称此路径为一

9、条其余顶点均不相同，则称此路径为一条简单路径简单路径 。起点和终点相同的路径称为。起点和终点相同的路径称为回路或环回路或环,其余顶点均其余顶点均不相同，称为不相同，称为简单回路简单回路62002-11-128mmmm图的连通图的连通 在在无向图无向图G G中，若两个顶点中，若两个顶点v vi i和和v vj j之间有之间有 路径存在，则称路径存在，则称v vi i 和和v vj j 是连通的。若是连通的。若G G中任意两中任意两 个顶点都是连通的，则称个顶点都是连通的，则称G G为为连通图连通图。非连通图的非连通图的极大连通子图叫做连通分量。极大连通子图叫做连通分量。BEADCFBAFEDC2

10、002-11-129mmmmn n强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量在有向图中在有向图中,若对于每一若对于每一对顶点对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是则称此图是强连通图强连通图。非强连通图的极大强连通。非强连通图的极大强连通子图叫做子图叫做强连通分量强连通分量。V2V2V4V4V3V3V1V1V4V4V3V3V2V2V1V12002-11-1210mmmm 生成树生成树一个连通图的生成树是它的极小一个连通图的生成树是它的极小连通子图，含图中连通子图，含图中n个顶点，有个顶点，有n-1

11、条条边。边。V1V1V3V3V4V4V5V5V2V2V1V1V3V3V4V4V5V5V2V2含图中含图中含图中含图中n n个顶点，有个顶点，有个顶点，有个顶点，有n n-1-1条边的图一定生成树吗？条边的图一定生成树吗？条边的图一定生成树吗？条边的图一定生成树吗？2002-11-1211mmmm生成森林生成森林在非连通图中，由每个连通分量在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个树。这些连通分量的生成树就组成了一个非连通图的生成森林非连通图的生成森林。BEADCFBAFEDC2002-11-1212m

12、mmm基本操作基本操作基本操作基本操作P P：结构的建立和销毁结构的建立和销毁结构的建立和销毁结构的建立和销毁:CreateGraphCreateGraph(&G,V,VR);/(&G,V,VR);/按按按按V V和和和和VRVR的定义的定义的定义的定义构造图构造图构造图构造图GG。DestroyGraphDestroyGraph(&G);/(&G);/销毁图销毁图销毁图销毁图GG。对顶点的访问操作对顶点的访问操作对顶点的访问操作对顶点的访问操作:LocateVexLocateVex(G,u);/(G,u);/若若若若GG中存在顶点中存在顶点中存在顶点中存在顶点u u，则返回则返回则返回则返回

13、该顶点在图中该顶点在图中该顶点在图中该顶点在图中位置位置位置位置；否则返回其它信息。；否则返回其它信息。；否则返回其它信息。；否则返回其它信息。GetVexGetVex(G,v);/(G,v);/返回返回返回返回v v的值。的值。的值。的值。PutVexPutVex(&G,v,value);/(&G,v,value);/对对对对v v赋值赋值赋值赋值valuevalue。2002-11-1213mmmm对邻接点的操作对邻接点的操作对邻接点的操作对邻接点的操作:FirstAdjVexFirstAdjVex(G,v);/(G,v);/返回返回返回返回v v的的的的第一个邻接点第一个邻接点第一个邻接

14、点第一个邻接点。若该顶点若该顶点若该顶点若该顶点/在在在在GG中没有邻接点，则返回中没有邻接点，则返回中没有邻接点，则返回中没有邻接点，则返回“空空空空”。NextAdjVexNextAdjVex(G,v,w);/(G,v,w);/返回返回返回返回v v的（相对于的（相对于的（相对于的（相对于w w的）的）的）的）下一个下一个下一个下一个 邻接点邻接点邻接点邻接点。若。若。若。若w w是是是是v v的最后一个邻接点，的最后一个邻接点，的最后一个邻接点，的最后一个邻接点，则返回则返回则返回则返回“空空空空”。插入或删除顶点插入或删除顶点插入或删除顶点插入或删除顶点 InsertVexInsert

15、Vex(&G,v);/(&G,v);/在图在图在图在图GG中增添新顶点中增添新顶点中增添新顶点中增添新顶点v v。DeleteVexDeleteVex(&G,v);/(&G,v);/删除删除删除删除GG中顶点中顶点中顶点中顶点v v及其相关的及其相关的及其相关的及其相关的弧。弧。弧。弧。2002-11-1214mmmm插入和删除弧插入和删除弧插入和删除弧插入和删除弧InsertArcInsertArc(&G,v,w);/(&G,v,w);/在在在在GG中增添弧中增添弧中增添弧中增添弧 v,w，若若若若GG是无向的，则还增添对称弧是无向的，则还增添对称弧是无向的，则还增添对称弧是无向的，则还增添

16、对称弧 w,v。DeleteArcDeleteArc(&G,v,w);/(&G,v,w);/在在在在GG中删除弧中删除弧中删除弧中删除弧 v,w，若若若若GG是无是无是无是无 向的，则还删除对称弧向的，则还删除对称弧向的，则还删除对称弧向的，则还删除对称弧 w,v。遍历遍历遍历遍历DFSTraverseDFSTraverse(G,v,Visit();/(G,v,Visit();/从顶点从顶点从顶点从顶点v v起起起起深度优深度优深度优深度优先先先先遍历图遍历图遍历图遍历图GG，并对每个顶点调用函数并对每个顶点调用函数并对每个顶点调用函数并对每个顶点调用函数VisitVisit一次且一次且一次且

17、一次且仅一次。仅一次。仅一次。仅一次。BFSTraverseBFSTraverse(G,v,Visit();/(G,v,Visit();/从顶点从顶点从顶点从顶点v v起起起起广度优广度优广度优广度优先先先先遍历图遍历图遍历图遍历图GG，并对每个顶点调用函数并对每个顶点调用函数并对每个顶点调用函数并对每个顶点调用函数VisitVisit一次且一次且一次且一次且仅一次。仅一次。仅一次。仅一次。2002-11-1215mmmm 二、图的存储结构二、图的存储结构在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个记录各个记录各个顶点信息顶点信息的的顶点表顶点表，还有一个，还有一个表示各个顶表示各

18、个顶点之间关系点之间关系的的邻接矩阵邻接矩阵。设图设图A=(V,E)是一个有是一个有n 个顶点的图，则个顶点的图，则图的邻接矩阵是一个二维数组图的邻接矩阵是一个二维数组A.Edgenn，定义：定义：无向图的邻接矩阵是对称的，有向图的邻无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。接矩阵可能是不对称的。1.邻接矩阵邻接矩阵(AdjacencyMatrix)162002-11-1216mmmm在无向图中在无向图中在无向图中在无向图中,统计第统计第统计第统计第 i i 行行行行(列列列列)1)1的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点i i 的度。的度。的度。的度。在有向

19、图中在有向图中在有向图中在有向图中,统计第统计第统计第统计第 i i 行行行行11的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点 i i 的出度，的出度，的出度，的出度，统计第统计第统计第统计第 j j 列列列列11的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点 j j 的入度。的入度。的入度。的入度。2002-11-1217mmmm网的邻接矩阵网的邻接矩阵2002-11-1218mmmm邻接矩阵表示法中图的描述邻接矩阵表示法中图的描述#definen6/*图的顶点数图的顶点数*/#definee8/*图的边数图的边数*/typedefcharvextype;/*顶点的数据

20、类型顶点的数据类型*/typedeffloatadjtype;/*权值类型权值类型*/typedefstructvextypevexsn;adjtypearcsnn;graph;2002-11-1219mmmm214352002-11-1220mmmmBADCE2002-11-1221mmmm2153462030504070802002-11-1222mmmm邻接矩阵表示法中无向网的建立算法邻接矩阵表示法中无向网的建立算法CREATEGRAPH(graph*ga)inti,j,k;floatw;for(i=0;ivexsigetchar();/*读入顶点信息，建立顶点表读入顶点信息，建立顶点表

21、*/for(i=0;in;i+)for(j=0;jarcsij0;/*邻接矩阵初始化邻接矩阵初始化*/for(k=0;karcsijw;ga-arcsjiw;2002-11-1223mmmm2.邻接表存储结构邻接表存储结构(AdjacencyList)无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表 把同一个顶点发出的边链接在同一个边链表中，链表把同一个顶点发出的边链接在同一个边链表中，链表把同一个顶点发出的边链接在同一个边链表中，链表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存的每一个结点代表一条边，叫做边结点，结点中保存的每一个结点代

22、表一条边，叫做边结点，结点中保存的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标有与该边相关联的另一顶点的顶点下标有与该边相关联的另一顶点的顶点下标有与该边相关联的另一顶点的顶点下标 destdest 和指向同和指向同和指向同和指向同一链表中下一个边结点的指针一链表中下一个边结点的指针一链表中下一个边结点的指针一链表中下一个边结点的指针 linklink。2002-11-1224mmmm有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表在有向图的邻接表中，第在有向图的邻接表中，第i个邻接表链接的边个邻接表链接的边都是都是顶点顶点i发出的边发出的边。也叫做。也叫做出

23、边表出边表。在有向图的逆邻接表中，第在有向图的逆邻接表中，第i个邻接表链接的个邻接表链接的边都是边都是进入顶点进入顶点i的边的边。也叫做。也叫做入边表入边表。2002-11-1225mmmm带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值cost。顶点顶点i 的边链表的表头指针的边链表的表头指针adj 在顶点表的下标在顶点表的下标为为i 的顶点记录中，该记录还保存了该顶点的的顶点记录中，该记录还保存了该顶点的其它信息。其它信息。在邻接表的边链表中，在邻接表的边链表中，各个边结点的链入顺序各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。设图中有设图中有

24、n 个顶点，个顶点，e 条边，则条边，则用邻接表表示用邻接表表示无向图时无向图时，需要，需要n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用用邻接表表示有向图时邻接表表示有向图时，若不考虑逆邻接表，若不考虑逆邻接表，只需只需n 个顶点结点，个顶点结点，e 个边结点。个边结点。2002-11-1226mmmm邻接表的形式说明和建立算法邻接表的形式说明和建立算法typedefstructnode/*边表结点定义边表结点定义*/intadjvex;structnode*next;edgenode;typedefstruct/*顶点表结点定义顶点表结点定义*/vextypevertex;edg

25、enode*link;vexnode;vexnodegan;2002-11-1227mmmm网络(带权图)的邻接表2002-11-1228mmmm7.3图的遍历性图的遍历性从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历图的遍历图的遍历(GraphTraversa

26、l)GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。回到了曾经访问过的顶点。回到了曾经访问过的顶点。回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问为了避免

27、重复访问，可设置一个标志顶点是否被访问为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组过的辅助数组过的辅助数组过的辅助数组 visitedvisited，它的初始状态为它的初始状态为它的初始状态为它的初始状态为0 0，在图的，在图的，在图的，在图的遍历过程中，一旦某一个顶点遍历过程中，一旦某一个顶点遍历过程中，一旦某一个顶点遍历过程中，一旦某一个顶点 i i 被访问，就立即让被访问，就立即让被访问，就立即让被访问，就立即让 visitedvisited i i 为为为为1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。2002-11-1229mmm

28、m DFS DFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由后，由后，由 v v 出发，出发，出发，出发，访问它的访问它的访问它的访问它的任一邻接顶点任一邻接顶点任一邻接顶点任一邻接顶点 w w1 1；再从再从再从再从 w w11出发，访问与出发，访问与出发，访问与出发，访问与 w w1 1邻接但还没有访问过的顶点邻接但还没有访问过的顶点邻接但还没有访问过的顶点邻接但还没有访问过的顶点 w w2 2；然后再从然后再从然后再从然后再从 w w22出出出出发，进行类似的访问，发，进行类似的访问，发，进行类似的访问，发，进行类似的

29、访问，如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点 u u 为止。接着，为止。接着，为止。接着，为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻

30、接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。1.深度优先搜索深度优先搜索DFS(DepthFirst

31、Search)2002-11-1230mmmm深度优先搜索的示例深度优先搜索的示例2002-11-1231mmmm深度优先搜索算法深度优先搜索算法intvisitedn;graphg;DFS(inti)/*图用邻接矩阵表示图用邻接矩阵表示*/intj;printf(“node:%cn”,g.vexsi);visitedi=TRUE;for(j=0;jif(!visitedp-adjvexadjvex)DFSL(p-DFSL(p-adjvexadjvex););p=p-next;p=p-next;邻接表的形式说明邻接表的形式说明/*边表结点定义边表结点定义*/typedefstructnodei

32、ntadjvex;structnode*next;edgenode;/*顶点表结点定义顶点表结点定义*/typedefstructvextypevertex;edgenode*link;vexnode;2002-11-1233mmmm例子遍历结果：遍历结果：A A、C C、B B、D D深度优先深度优先2002-11-1234mmmm2.广度优先搜索广度优先搜索BFS(BreadthFirstSearch)广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树2002-11-1235mmmm使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起

33、始顶点v 之后，之后，由由v 出发，依次访问出发，依次访问v 的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点w1,w2,wt，然后再顺序访问然后再顺序访问w1,w2,wt 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，有还未被访问过的邻接顶点，如此做下去，如此做下去，直到图中所有顶点都被访问到为止。直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批

34、顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。是一个递归的过程，其算法也不是递归的。2002-11-1236mmmm为了实现逐层访问，算法中使用了一个队列，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组需要一个辅助数组visited，给被访问过的顶给被访问过的顶点加标记。点加标记。2002-11-1

35、237mmmm广度优先搜索算法广度优先搜索算法BSF(intk)/*图用邻接矩阵表示图用邻接矩阵表示*/inti,j;SETNULL(Q);printf(“%cn”,g.vexsk);visitedk=TRUE;ENQUEUE(Q,K);while(!EMPTY(Q)i=DEQUEUE(Q);for(j=0;jadjvex)printf(“%cn”,g1p-adjvex.vertex);visitedp-adjvex=TRUE;ENQUEUE(Q,p-adjvex);p=p-next;2002-11-1239mmmm例子遍历结果：遍历结果：A A、C C、B B、D D2002-11-1240

36、mmmm7.4无向图的连通性无向图的连通性当无向图为非连通图时，从图中某一顶点出发，利用当无向图为非连通图时，从图中某一顶点出发，利用当无向图为非连通图时，从图中某一顶点出发，利用当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到深度优先搜索算法或广度优先搜索算法不可能遍历到深度优先搜索算法或广度优先搜索算法不可能遍历到深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通图中的所有顶点，只能访问到该顶点所在的最大连通图中的所有顶点，只能访问到该顶点所在的最大连通图中的所有顶点，只能访问到该顶点所在的最大连通子图子

37、图子图子图(连通分量连通分量连通分量连通分量)的所有顶点。的所有顶点。的所有顶点。的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行若从无向图的每一个连通分量中的一个顶点出发进行若从无向图的每一个连通分量中的一个顶点出发进行若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。遍历，可求得无向图的所有连通分量。遍历，可求得无向图的所有连通分量。遍历，可求得无向图的所有连通分量。算法实现：算法实现：算法实现：算法实现：需要对图的每一个顶点进行检测：若已被需要对图的每一个顶点进行检测：若已被需要对图的每一个顶点进行检测：若已被需要对图的每一个顶点进行检测：若已被访

38、问过，则该顶点一定是落在图中已求得的连通分量访问过，则该顶点一定是落在图中已求得的连通分量访问过，则该顶点一定是落在图中已求得的连通分量访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得上；若还未被访问，则从该顶点出发遍历图，可求得上；若还未被访问，则从该顶点出发遍历图，可求得上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。图的另一个连通分量。图的另一个连通分量。图的另一个连通分量。2002-11-1241mmmm对于非连通的无向图，所有连通分量的生成树组成了对于非连通的无向图，所有连通分量的生成树组成了对于非连通的无向图，所有连通分

39、量的生成树组成了对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。非连通图的生成森林。非连通图的生成森林。非连通图的生成森林。2002-11-1242mmmm非连通图的遍历 非连通图的遍历必须多次调用深度优先搜索或非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法，以广度优先搜索算法，以DFSDFS为例：为例：TRAVER()/*遍历用邻接矩阵表示的非连通图遍历用邻接矩阵表示的非连通图*/inti;for(i=0;in;i+)visitedi=FALSE;/*标志数组初始化标志数组初始化*/for(i=0;in;i+)if(!visitedi)DFS(i);/*从顶点出发

40、遍历一个连从顶点出发遍历一个连通分量通分量*/printf(“compendn”);2002-11-1243mmmm四、最小生成树(minimum cost spanning tree)按照生成树的定义，按照生成树的定义，n 个顶点的连通网络个顶点的连通网络的生成树有的生成树有n 个顶点、个顶点、n-1条边。条边。生成树是连通图的极小连通子图。所谓生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变出现一个回路；若去掉一条边，将会使之变成非连通图。成非连通图。2002-11-1244mmmm用不同的

41、遍历图的方法，可以得到不同的生用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。成树。V1V1V3V3V4V4V5V5V2V2V1V1V3V3V4V4V5V5V2V2V1V1V3V3V4V4V5V5V2V22002-11-1245mmmm对于无向网，对于无向网，生成树各边的生成树各边的权值总和权值总和称称为生成树的权。权最小的生成树称为为生成树的权。权最小的生成树称为最最小生成树。小生成树。构造最小生成树的准则：必须只使用该构造最小生成树的准则：必须只使用该网中的边来构造最小生成树；必须使用网中的边来构造最小生成树；

42、必须使用且仅使用且仅使用n-1条边来联结网络中的条边来联结网络中的n 个个顶点；不能使用产生回路的边顶点；不能使用产生回路的边,权值总和权值总和最小最小。2002-11-1246mmmm问题：假设要在问题：假设要在n个城市之间建立通讯联个城市之间建立通讯联络网，则连通络网，则连通n个城市只需要修建个城市只需要修建n-1条条线路，线路，如何在最节省经费的前提下建立如何在最节省经费的前提下建立这个这个通讯网通讯网？该问题等价于：构造网的一棵最小生成该问题等价于：构造网的一棵最小生成树，即：在树，即：在e条带权的边中选取条带权的边中选取n-1条条（不构成回路），使（不构成回路），使“权值之和权值之和

43、”为最为最小。小。2002-11-1247mmmm最小生成树的重要性质：最小生成树的重要性质：设设 G=G=（V V，EE）是一个连通网，是一个连通网，U U 是是顶点集顶点集 V V 的的一个非空子集。若（一个非空子集。若（u u，v v）具具有最小权值的一条边，有最小权值的一条边，u u是在是在U U中，中，v v不在不在U U 中，则一定存在中，则一定存在 G G 的一棵最小生成树包含的一棵最小生成树包含（u u，v v）边。边。uvUVU2002-11-1248mmmm证明（反证法）：证明（反证法）：假设假设 G G 中任何一棵最小生成树中都不包含中任何一棵最小生成树中都不包含(u u

44、，v)v)。设设T T是一棵最小生成树但不包含是一棵最小生成树但不包含(u u，v)v)。由于由于T T是最小生成树，所以是最小生成树，所以 T T 是连通的，因是连通的，因此有一条从此有一条从u u到到v v的路径，且该路径上必有一条的路径，且该路径上必有一条连接两个顶点集连接两个顶点集 U U、V V 的边的边(u u，v v)，其中其中u uUU，v vV-UV-U。当把边当把边(u u，v)v)加入到加入到 T T 中后，得到中后，得到一个含有边一个含有边(u u，v)v)的回路。删除边的回路。删除边(u u，v v)，上上述回路即被消除。由此得到另一棵生成树述回路即被消除。由此得到另

45、一棵生成树 T T，T T 和和 T T 的区别仅在于用边的区别仅在于用边(u u，v)v)代替了代替了(u u，v v)。由于由于(u u，v)v)的权的权=(=(u u，v v)的权，所以，的权，所以，T T的的权权=T T的权，与假设矛盾。的权，与假设矛盾。2002-11-1249mmmmuvUVUuv2002-11-1250mmmm普里姆(Prim)算法普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络N=V,E中的某一顶点中的某一顶点u0出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到将其顶点加入到生成树的顶点集合生成

46、树的顶点集合U中。以后每中。以后每一步从一步从一个顶点在一个顶点在U中中，而，而另一个顶点不在另一个顶点不在U中中的各条边中选择的各条边中选择权值最小的边权值最小的边(u,v),把它的顶点把它的顶点加入到加入到集合集合U中。如此继续下去，直到网络中的中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合所有顶点都加入到生成树顶点集合U中为止。中为止。2002-11-1251mmmm用普里姆算法构造最小生成树的过程用普里姆算法构造最小生成树的过程1234655651732546123465513242002-11-1252mmmm克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法的基本思想：克

47、鲁斯卡尔算法的基本思想：设有一个有设有一个有n 个顶点的连通网络个顶点的连通网络N=V,E,最初先构造一个只有最初先构造一个只有n 个顶点，没有边的非连通个顶点，没有边的非连通图图T=V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。当在当在E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的若该边的两个顶点落在不同的连通分量上，则将此边加入两个顶点落在不同的连通分量上，则将此边加入到到T 中；否则将此边舍去，重新选择一条权值最中；否则将此边舍去，重新选择一条权值最小的边。小的边。如此重复下去，直到所有顶点在同一个连通如此重复下去，直到所有顶点在同一个连通分量上为止。分量上为止。2002-11-1253mmmm用克鲁斯卡尔算法构造最小生成树的过程用克鲁斯卡尔算法构造最小生成树的过程1234655651732546123465513242002-11-1254mmmm上机及作业上机及作业(1)：邻接矩阵表示法建立无向图，深邻接矩阵表示法建立无向图，深度优先搜索输出各顶点值的算法。度优先搜索输出各顶点值的算法。作业作业(2)：7.72002-11-1255mmmm