数据结构07章_图

1、7.1 图的术语图的术语ADT Graph D_Object: V = 具有相同特性的数据元素的集具有相同特性的数据元素的集 合合，即：，即：V为顶点集。为顶点集。 D_Relation: R = VR VR = | v, wV且且P(v, w), 表示从表示从v到到w的弧，谓词的弧，谓词 P(v, w)定义了弧的意义或信息定义了弧的意义或信息 B_OP: (共共13种种) ADT Graph一个图G由两个集合V和R组成，用G=(V, R)表示，其中：V为有限非空顶点(Vertex)集，即：V=v|vElemSet(顶点：图中的数据元素)；R是边(Edge)(或弧(Arc)的有限集，即：R =

2、 VR, VR = | P(v, w), 且v, wV。 有时,图G的顶点集记为V(G)；边(或弧)的集记为E(G)(或A(G)，边(或弧)的集在不明确是何种图时通常记为R(G)。(Digraph) ：若图G中的每一条边都用箭头指明了方向，则称G为有向图有向图。有向图中的边称为弧弧(Arc)，弧的集合记为A(G)或A，且G记为G = (V, A)。在有向图G中，若vi, vjV(G), A(G), 则称是G中的从vi到vj的一条弧，且称vi为弧尾弧尾(Tail)(或初始点(Initial Node)，vj为弧头弧头(Head)(或终端点(Terminal Node)；若A(G), 则vj是弧尾

3、，vi是弧头，且。设图G中有n个顶点，则G中弧的条数最多为n(n1)条。例：例：G11234V(G1)=v1, v2, v3, v4A(G1)=, , ：图中的边没有指明方向。即以无序对(vi, vj)代替和两个序偶表示图G中的一条边。此时可视(vi, vj)=(vj, vi)。边的集合记为E(G)或E，且G记为G = (V, E)。注：1) 无论是有向图，还是无向图，若(vi, vj)R(G)，则要求vivj如：就不能出现在图中，即不能认为是图中的边(或弧)。2) 图中两个顶点之间不允许多次出现同一条边(或弧)，否则就不是图，而称为多重图。如：不是图3) 用n表示图中顶点的数目，用e表示边(

4、或弧)的数目，那么，对于无向图，0en(n1)/2；对于有向图，0en(n1)。无向图例：V(G)=v1, v2, v3, v4E(G)=(v1, v2), (v1, v3), (v1, v4) , (v2, v3), (v2, v4) ,(v3, v4)1324此图中边数共6条，即：62) 14(41) 有向完全图：n个顶点的有向图中若有n(n1)条弧，则称该图为有向完全图。2) 无向完全图：n个顶点的无向图中有2) 1( nn条边，则称该图为无向完全图。13241324 具有n个顶点的图G中边(或弧)的条数很少(如enlogn)的图称为稀疏图稀疏图(Sparse Graph)，反之称为稠密

5、图稠密图(Dense Graph)。(边的条数究竟少于多少才称为稀疏图，并无确切的限定)带权的图 把一组与图中的边(或弧)相关的数称作图中相应边(或弧)的权权(Weight)(或权值)。带权的图称为网网(Network)。：若有两个图G=(V, R)和 G=(V, R)，且满足条件： V(G)V(G)，且R(G)R(G) 则称G是G的子图。图等。 1) 对于无向图G = (V, E)，如果边(vi, vj)E(G)，则称顶点vi和vj互为邻接点邻接点(Adjacent)，即： vi和vj 相互邻接；称边(vi, vj)依附依附 (Incident) (或关联关联)于顶

6、点vi和vj, 或者说边(vi, vj)与顶点vi和vj相关联。注：注：邻接邻接表示顶点之间的逻辑关系，表示顶点之间的逻辑关系，关联关联表示边表示边与顶点之间的关系。与顶点之间的关系。 2) 对于有向图G = (V, A)，如果弧A(G)，则称顶点vi邻接到邻接到顶点vj，或顶点vj邻邻接自接自顶点vi；又称弧与顶点vi和vj相关联。 在无向图中，与顶点vi(viV(G)相关联的边的条数称为vi的度度，记为TD(vi)。 在有向图中，顶点vi的度TD(vi) = ID(vi) + OD(vi)。即：顶点的入度、出度之和，其中：入度(InDegree)：ID(vi)等于以vi为头的边的数目。出度

7、(OutDegre)：OD(vi)等于以vi为尾的边的数目。注：一个有注：一个有n个顶点、个顶点、e条边条边(或弧或弧)的无向图的无向图(或有向或有向图图)的顶点的度，均满足下列关系：的顶点的度，均满足下列关系：niiivTDe)(21(n为图为图G的顶点数的顶点数)a) 若G是无向图，如果(vp, vi 1), (vi 1, vi2), (vin, vq)E(G)，则顶点序列(vp, vi1, vi2, ，vin，vq)是顶点vp到vq的一条路径路径。若G是有向图，则路径也是有向的，其顶点序列应满足：，A(G)。b) 路径长度：路径上边(或弧)的条数。c) 简单路径：不重复出现同一顶点的路径

8、。d) 回路(环)：第一个顶点和最后一个顶点相同的路径。e) 简单回路(或简单环)：除第一个和最后一个顶点之外，路径上其余顶点不重复出现的回路。a) 连通：若从顶点vi到vj存在一条路径，则称vi与vj是连通的连通的。(注：有向图中，vi与vj连通，不一定有vj与vi连通)b) 若G中的任意两个不同顶点vi和vj都是连通的，则称G是连通图连通图。即：(vi, vjv(G), vivj), vi, vj是连通的，则G是连通图。132413241423连通图14231234非连通图c) 连通分量：无向图中的一个极大连通子图极大连通子图(一个极大连通分支)。例例：G如132是G的一个连通子图但不是极

9、大连通子图。132456789上图G是一个非连通图，但它有三个连通分量，分别为：132478956和d) 强连通图：在有向图G中，若对于每一对顶点vi， vjV(G)， vivj，从vi到vj和从vj到vi都存在一条路径，则称G是强连通图强连通图。(注意：并不要求vi到vj或vj到vi存在弧)e) 强连通分量：有向图中的一个极大强连通子图极大强连通子图。例：例：123123存在两个强连通分量和图：123是强连通图7.2 图的存储结构图的存储结构图的存储结构通常有，用数组表示的邻接矩邻接矩阵、邻接表、十字链表阵、邻接表、十字链表和邻接多重表邻接多重表。以下分别介绍： 用两个数组分别存储数据元素(

10、顶点)(一维)的信息和边(或弧)(二维)的信息。其形式描述如下：P1611) 设图G=(V, R)是有n(n1)个顶点的图，则根据G中顶点间的邻接关系可用二维数组建立具有下列性质的nn阶的邻接矩阵作为G的存储结构。即：Aij =1 若或(vi,vj)R(G)0 反之例：例：42310 1 1 11 0 1 11 1 0 11 1 1 0 无向图：对称邻接矩阵0 1 01 0 10 0 0231 有向图：非对称邻接矩阵借助邻接矩阵可判定图中任意两个顶点vi、vj之间是否有边(或弧)相连，即：无向图中各顶点的度无向图中各顶点的度: 第第i行行(或第或第j列列)元素之和。即：元素之和。即：1 -n0

11、jiAij)TD(v10j)TD(vor nijiA当Aij =1 (vi和vj之间有边(或弧)相连)0 (vi和vj之间无边(或弧)并可求得：有向图中各顶点的度有向图中各顶点的度: 第第i行元素之和为顶点行元素之和为顶点vi的出度的出度OD(vi)，第，第j列元素之和为顶点列元素之和为顶点vj的入度的入度ID(vj)，即：，即：1010iii)OD(v)ID(v)TD(vnjnjijAjiA2) 网的邻接矩阵可定义为：wij为边(vi, vj) or 弧上的权值。在无向图中根据其对称性，若要检测图中有多少条边，只需检测其上三角矩阵或下三角矩阵即可。Aij =wij (Vi,Vj)orR(G)

12、 反之例：见P162页图7.9邻接表是图的一种链式存储结构。它是将图中的每一个顶点建立一个带表头结点的单链表，第i个单链表中的结点表示依附于顶点vi的边(有向图中是以vi为尾的弧)以及与vi相邻接的所有顶点；每个表头结点有序地存储在一个一维数组中，主要用于存储顶点的有关信息及指向该顶点对应的单链表的指针。1) 邻接表中链表结点结构：邻接点域：邻接点域：与顶点与顶点vi邻接的点在图中邻接的点在图中的位置的位置(序号序号)链域链域 ：指示下一指示下一条边或弧的邻接点条边或弧的邻接点adjvexnextarcinfo数据域：数据域：边或弧相边或弧相关的信息或权值等关的信息或权值等datafirsta

13、rc数据域：数据域：与与vi有有关的信息关的信息(序号序号)链域：链域：指示链指示链表中第一结点表中第一结点b) 头结点：头结点：顶点在图中位置是人为的编排的，顶点在图中顶点在图中位置是人为的编排的，顶点在图中并没有顺序关系。并没有顺序关系。a) 表结点：表结点：2) 邻接表的存储结构如下： P163/-图的邻接表存储表示图的邻接表存储表示-typedef struct VNode Vnode, AdjListMAX_VERTEX_NUM;#define MAX_VERTEX_NUM 20 / 最大值顶点数最大值顶点数/ 指向第一条依附该顶点的弧的指针指向第一条依附该顶点的弧的指针typede

14、f struct ALgraph;int vexnum, arcnum; / 图的当前顶点数和弧数图的当前顶点数和弧数AdjList vertices; int kind; / 图的种类标志图的种类标志ArcNode *firstarc；int adjvex；typedef struct ArcNode ArcNode;InfoType *info; / 该弧相关信息的指针该弧相关信息的指针/ 该弧所指向的顶点的位置该弧所指向的顶点的位置/ 指向下一条弧的指针指向下一条弧的指针struct ArcNode *nextarc；vertexType data； / 顶点信息顶点信息3) 结点结构：

15、为简便起见，我们采用两个域的结点结构来建立邻接表： 注意：为使表头结点和表结点同构，我们均采用同注意：为使表头结点和表结点同构，我们均采用同一种结点结构来建立邻接表，省略表结点中的一种结点结构来建立邻接表，省略表结点中的info域。域。例：例：v1v2v3v4无向图邻接表：无向图邻接表：v10123v20123v301v4230123表头数组有向图邻接表：有向图邻接表：v2v3v12v1v2v301120表头数组注：注： 无向图中无向图中n个顶点，个顶点，e条边，则其邻接表需条边，则其邻接表需n个个头结点和头结点和2e个表结点。个表结点。 表结点中，表结点中，adjvex域存放顶点在数组中的序

16、域存放顶点在数组中的序号。习惯上由大到小排列。号。习惯上由大到小排列。由邻接表可得：在无向图的邻接表中的第i个链表中的结点数等于顶点vi的度。而对于有向图，第i个链表中的结点数是顶点的vi的出度。若要求顶点vi的入度，则要遍历整个邻接表，求得邻接表中表结点的邻接点域adjvex的值=i1(顶点vi在数组中的序号)的结点的个数，即得顶点vi的入度。显然比较麻烦。为方便起见，我们可以建立另一个邻接表逆邻逆邻接表接表，即：对每个顶点vi建立一个以vi为弧头的邻接表，其表结点是连接vi的尾顶点，其头结点与上相同。例例：上图的逆邻接表：注：注： 第第i个链表中的结点数即为个链表中的结点数即为vi的入度；

17、的入度； 邻接邻接表容易找出顶点之间的邻接点，但要判断表容易找出顶点之间的邻接点，但要判断vi和和vj之间是之间是否存在边否存在边(或弧或弧)，则要搜索第，则要搜索第i或第或第j个链表，不及邻接个链表，不及邻接矩阵方便。矩阵方便。2v1v2v301101表头数组 是有向图有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来所得的一种链表。1) 结点结构：结点结构：每条弧有一个结点，每个顶点也有一个结点。 弧头顶点弧头顶点指示弧头指示弧头相同的下相同的下一条弧一条弧弧相关的弧相关的信息或权信息或权值等值等a) 表表(弧弧)结点：结点：tailvexheadvexhlinktl

18、inkinfo弧尾顶点弧尾顶点指示弧尾指示弧尾相同的下相同的下一条弧一条弧指向以该指向以该顶点为弧顶点为弧头的第一头的第一个弧结点个弧结点b) 头头(顶点顶点)结点：结点：datafirstinfirstout与顶点相与顶点相关的信息关的信息指向以该指向以该顶点为弧顶点为弧尾的第一尾的第一个弧结点个弧结点2) 有向图的十字链表存储表示如下：有向图的十字链表存储表示如下： P165 /-有向图的十字链表存储表示有向图的十字链表存储表示-typedef struct vexNode vexnode;#define MAX_VERTEX_NUM 20 / 最大值顶点数最大值顶点数/ 分别指向该顶点的

19、第一条入弧和出弧分别指向该顶点的第一条入弧和出弧typedef struct OLgraph;int vexnum, arcnum; / 有向图的当前顶点数和弧数有向图的当前顶点数和弧数vexNode xlistMAX_VERTEX_NUM; / 表头数组表头数组 ArcBox *firstin, *firstout；int tailvex, headvex；typedef struct ArcBox ArcBox;InfoType *info; / 该弧相关信息的指针该弧相关信息的指针/ 该弧的尾和头顶点的位置该弧的尾和头顶点的位置/ 分别为弧头相同和弧尾相同的弧的链域分别为弧头相同和弧尾相

20、同的弧的链域struct ArcBox *hlink, *tlink；vertexType data； / 顶点信息顶点信息 是无向图无向图的另一种链式存储结构。从无向图的邻接表可以看出，每条边(vi, vj)是两个顶点vi和vj表示，而它们分别在第i个链表和第j个链表中，这给某些图的操作带来不便。例如，某些应用中需要对边进行操作，如对已搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。对于这类操作采用邻接多重表作为图的存储结构更为适宜。1) 结点结构：结点结构：邻接多重表的结构和十字链表类似，每条边用一结点表示，每个顶点也用一结点表示。mark：标志域，标记该条边是否被搜索

21、过。：标志域，标记该条边是否被搜索过。ivex, jvex：为该边依附的两个顶点序号：为该边依附的两个顶点序号(在图在图中的位置中的位置)ilink, jlink：指针域，分别指向下一条依附于顶点：指针域，分别指向下一条依附于顶点ivex和顶点和顶点jvex的边。的边。a) 表表(边边)结点：结点：markivex ilink jvex jlink infoinfo：数据域，存储与边相关的信息的指针域。：数据域，存储与边相关的信息的指针域。指针域：指示第一条指针域：指示第一条依附于该顶点的边依附于该顶点的边b) 头头(顶点顶点)结点：结点：datafirstedge数据域：存储与数据域：存储与

22、顶点相关的信息顶点相关的信息v4v2v3v1e1e2e6e5e4e31v1v2v3v421 32 3 01020 3如：如：0123e1e2e4e3e5e6v1：e1 e2 e3v2：e1 e4 e5v3：e2 e4 e6v4：e4 e5 e6或：或：0 e2 1 e40 e1 2 e40 3 e51 e5 2e61 3 e62 3 v1v2v3v4e1e2e3e4e5e6 对于加权图也同样可以邻接表和邻接多重表来作为存储结构，只要加一个存放权值的域即可。 除增加一个标志域外，邻接多重表所需存储空间与邻接表相同；各种基本操作也相似。 邻接多重表与邻接表的差别：仅在于同一条边在邻接表中用两个结点

23、表示，而在邻接多重表中只用一个结点表示，还可通过表头结点，把任一顶点依附的边都 接出来。注：注：2) 无向图的邻接多重表存储结构如下： P167/-无向图的邻接多重表存储表示无向图的邻接多重表存储表示-typedef struct vexBox vexBox;#define MAX_VERTEX_NUM 20 / 最大值顶点数最大值顶点数/ 指向第一条依附该顶点的边指向第一条依附该顶点的边typedef struct AMLGraph;int vexnum, arcnum; / 无向图的当前顶点数和边数无向图的当前顶点数和边数vexBox adjmulistMAX_VERTEX_NUM; /

24、表头数组表头数组 EBox *firstedge；int ivex, jvex；typedef struct EBox EBox;InfoType *info; / 该边相关信息的指针该边相关信息的指针/ 该边依附的两个顶点的位置该边依附的两个顶点的位置/ 分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边struct EBox *ilink, *jlink；vertexType data； / 顶点信息顶点信息VisitIf mark; / 访问标记访问标记typedef emnu unvisited, visited VisitIf;7.3 图的遍历与求图的连通分量图的遍历与

25、求图的连通分量：对于图G=(V，R)，从任意顶点vi(viV(G)出发顺着G中的某些边(或弧)访问G中的每一个顶点，且只访问一次。在遍历图的过程中，访问某个顶点之后，可能顺着某条路径再次访问该顶点。为了避免多次访问同一顶点，需设置一个一维辅助数组标识图中的顶点是否已被访问过，若G有n个顶点，则该数组大小为n。即：即：Boolean visitedMAX;visitedi =TRUE 表示vi已被访问过FALSE 表示vi未被访问过 注：注： “ TRUE”亦可以是“1”，或者被访问时的次序号；“FALSE”亦可以是“0”。a) 深度优先搜索法深度优先搜索法(Depth-First Search

26、)(纵向优先搜索纵向优先搜索)基本思想：基本思想： 从图G(V, R)中某一顶点v1出发访问与v1相邻的任意顶点w1 再从w1出发，访问与w1邻接且未被访问过的顶点w2，再从w2出发，如此重复访问其未被访问的邻接点，直至一个所有邻接点都 被 访问过的顶点wk。然后逐步退回到wk-1，wk-2，w1找到一个还有邻接点未被访问过的顶点wj(与树的先根遍历类似，是其推广与树的先根遍历类似，是其推广) 从wj出发重复步，直至所有顶点都被访问过一次且仅一次。简称“DFS”。v1,v2,v4,v8,v7,v3,v6,v5或或v1v3v2v4v5v6v7v8例：例：P168从从V1出发可能得到的访问顺序有：

27、出发可能得到的访问顺序有：v1,v2,v5,v8,v4,v6,v3,v7v1,v3,v6,v8,v7,v5,v2,v4DFS递归算法如下：递归算法如下：P169void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图对图G作深度优先遍历作深度优先遍历VisitFunc = Visit; for (v=0; vG.vexnum; + +v)visitedv = FALSE; / 访问标志数组初始化访问标志数组初始化if (!visitedv) DFS(G, v); / DFSTraverse/ 使用全局变量使用全局变量VisitFunc,使使DF

28、S不必设函数指针参数不必设函数指针参数for (v=0; vG.vexnum; + +v)/- 算法使用的全局变量算法使用的全局变量-Boolean visitedMAX; / 访问标志数组访问标志数组Status (*VisitFunc)(int v); / 函数变量函数变量/ 对尚未访问的顶点调用对尚未访问的顶点调用DFS注：这是一个递归过程。附设访问标志数组注：这是一个递归过程。附设访问标志数组Visitedn，初值为初值为“FALSE”，一旦被访问，其值则为，一旦被访问，其值则为“TRUE”。void DFS (Graph G, int v) / 从第从第v个顶点出发递归地深度优先遍历

29、图个顶点出发递归地深度优先遍历图Gfor (w=FirstAdjvex(G, v); w; w=NextAdjvex(G,v,w)visitedv = TRUE; VisitFunc(v); / 访问第访问第v个顶点个顶点if (!visitedw) DFS(G, w); / DFS/ 对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS函数函数DFS算法如下：算法如下：P169DFS非递归算法如下：非递归算法如下：(补充补充)void DFSTraverse(Graph G, Status (*Visit)(int v) / 按深度优先按深度优先非递归非递归遍历图遍历图G。

30、/ 使用辅助栈使用辅助栈S和访问标志数组和访问标志数组visited。InitStack(S); / 置空辅助栈置空辅助栈Sfor (v=0; vG.vexnum; v)visitedv = FALSE; / 访问标志数组初始化访问标志数组初始化if (!visitedv) / v尚未访问尚未访问 / DFSTraversefor (v=0; vG.vexnum; v)visitedv = TRUE; Visit(v); GetTop(S, u); / 栈顶元素出栈并置为栈顶元素出栈并置为uwhile ( !StackEmpty(S) for (w=FirstAdjvex(G, u); w;

31、w=NextAdjvex(G, u, w)if (!visitedw) / w为为u的尚未访问的邻接点的尚未访问的邻接点visitedw = TRUE; Visit(w); Push(S, v); / v入栈入栈Push(S, w); break; /ifif (!w) Pop(S, w); / while / if例例：上图的邻接表：v1246777652 1 1 5310 0 43 72 v2v3v4v5v6v7v812345670头结点头结点表结点表结点：上图G的邻接表不是唯一的，以此邻接表为例图的存储结构，则执行DFSTraverse算法所得的顶点序列为：(从v1出发)v1，v3 ，v

32、7 ，v8 ，v6 ，v5 ，v2 ，v4 若从另一顶点出发，则遍历后可得另一序列。(此时算法要适当修改，如何修改？请思考此时算法要适当修改，如何修改？请思考)。b) 广度优先搜索广度优先搜索(Breadth-First Search)(横向优先搜索横向优先搜索)基本思想：基本思想： 从图G中的某一顶点v1出发，访问与顶点v1邻接的全部邻接顶点，w1，w2，wx； 依次访问与w1，w2，wx邻接且未被访问过的顶点，依此类推，直至所有顶点都 被访问为止。上例图进行广度优先搜索可得：v1，v2 ，v3 ，v4 ，v5 ，v6 ，v7 ，v8(与树的层序遍历类似，是其推广与树的层序遍历类似，是其推广

33、) 注：该遍历过程也要设一访问标志数组，并且为注：该遍历过程也要设一访问标志数组，并且为了顺次访问路径长度为了顺次访问路径长度为2，3，的顶点，还要设队的顶点，还要设队列，依次存储被访问的顶点。列，依次存储被访问的顶点。BFS算法如下：算法如下：P170void BFSTraverse(Graph G, Status (*Visit)(int v) / 按广度优先按广度优先非递归非递归遍历图遍历图G。/ 使用辅助队列使用辅助队列Q和访问标志数组和访问标志数组visited。InitQueue(Q); / 置空辅助队列置空辅助队列Qfor (v=0; vG.vexnum; v)visitedv

34、= FALSE; / 访问标志数组初始化访问标志数组初始化if (!visitedv) / v尚未访问尚未访问 / BFSTraversefor (v=0; vG.vexnum; v)visitedv = TRUE; Visit(v); DeQueue(Q, u); / 队头元素出队并置为队头元素出队并置为uwhile ( !QueueEmpty(Q) for (w=FirstAdjvex(G, u); w; w=NextAdjvex(G,u,w)if (!visitedw) / w为为u的尚未访问的邻接点的尚未访问的邻接点visitedw = TRUE; Visit(w); EnQueue(

35、Q, v); / v入队列入队列EnQueue(Q, w); / if / while / if求图的连通分量，实际上是图的遍历的一种应用。当无向图是非连通时，从图中的某一顶点v1为出发遍历图，只能访问到包含顶点v1的图的一个连通分量，而不能访问图中的所有顶点。若要求含n个顶点的图的所有连通分量的顶点序列集，则可从任一新的顶点vi(1i n) 出发，反复遍历图，即可求得该图的全部连通分量。检测图中的每一个顶点，若该顶点已被访问，则该顶点已落在图中已求得的某个连通分量上；若未被访问，则从该顶点出发遍历图，便可求得图的另一个连通分量。如此重复即可求得所有的连通分量。void component(G

36、) / 求具有求具有n个顶点的图个顶点的图G的所有连通分量的所有连通分量for (i=1; in; i) visitedi = FALSE;for (i=1; in; i)if (!visitedi)BFSTraverse(G, i); / component求图的连通分量求图的连通分量算法：算法：例：例：945101176有三个连通分量13827.4 生成树和最小生成树生成树和最小生成树设是一个有n个顶点的连通图。 它的生成树是一个极小连通子图，即：它含有图中的全部顶点，但只有足以构成一棵树的n1条边。如：G=(V,T)是一棵生成树，即G是的子图，且G中含中的全部顶点，仅有足以构成一棵树的n

37、1条边，则子图G是的一棵生成树。 如果在一棵生成树上添加一条边，必定构成一环。因此一棵有n个顶点的生成树有且仅有n1条边。 若少于n1条边，则是非连通图，若多于n1条边，则一定有环。1) 生成树生成树若从图中任一顶点出发遍历图时，必定将E(G)分成两个子集，分别记为B(G)和T(G)，其中B(G)为遍历过程中没有走过的边，T(G)为遍历过程中走过的边。则子图G=(V, T)就是一棵生成树。而按DFS方法得的生成树为深度优先生深度优先生成树成树，按BFS方法得到的生成树为广度优先生成广度优先生成树树。反之，不一定成立，即：有n1条边的图不一定是生成树。例：例：GDFS生成树：BFS生成树： 对于

38、非连通图，每个连通分量均可生成一棵树，构成该非连通图的生成森林。2) 生成森林生成森林 生成树及生成森林的算法：P171-1723) 算法算法作为图的应用，若在n个城市之间建立通讯网络，连通n个城市仅需n1条线路即可。而最大可能建立n(n1)/2条线路。每条线路的建立都必须花费一定的代价，为节约起见，在建立n个城市的通讯网络时，一般考虑： 建立n1条线路 建立花费代价最小的n1条线路我们可以用连通网来表示：把每一个城市作为一个顶点，每两个城市间的线路看成是关联两个顶点的边，则可绘制出n个城市间的通讯线路图正好是一棵生成树(一个生成树森林)，每个生成树的每条线路所花费的代价作为相应边的权，则生成

39、树称为代价生成树代价生成树。因此建立n个城市的通讯网问题就成为建立一最小代价生成最小代价生成树树(Minimum Cost Spanning Tree) (简称为“最小生成树”)的问题。注：对注：对n个城市所建立的个城市所建立的n 1条边的网络图不唯条边的网络图不唯一，可形成一个生成树森林一，可形成一个生成树森林。一棵代价生成树T的代价：则最小代价生成树的代价为：1n1iiGW(T)WSTT|(T)MinW)(TWGminG其中，ST为生成树森林。其中，Wi为第i条边的权值如何构造最小生成树？其算法有多种。我们必须寻求一种方法，使得所构造的生成树的代价最小。两种基本方法是：普里姆普里姆(Prim)算算法和克鲁斯卡尔法和克鲁斯卡尔(Kruskal)算法。算法。例例 ：给定如下图所示的网：12456356611162133141819设U(T)是已落在最小生成树T中的顶点集合，若顶点v和w都落在U(T)中，即v到w有一条连通路径，则边(v,w)加入T中必然构成回路。根据此思想，Prim提出了一种构造最小生成树的算法，用文字描述为： 设集合U(T)的初态为空， 在连通图上任选一顶点vi加入到U(T)中1) 普里姆普里姆(P