数据结构图结构动态.pptx

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

1、1 图（Graph）是一种较线性表和树更为复杂的）是一种较线性表和树更为复杂的非线性结构非线性结构。在在线性结构线性结构中，结点之间的关系是中，结点之间的关系是线性关系线性关系，除开始结点，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。和终端结点外，每个结点只有一个直接前趋和直接后继。在在树形结构树形结构中，结点之间的关系实质上是中，结点之间的关系实质上是层次关系层次关系，同层，同层上的每个结点可以和下一层的零个或多个结点（即孩子）上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结相关，但只能和上一层的一个结点（即双亲）相关（根结

2、点除外）。点除外）。然而在然而在图形结构图形结构中，对结点（图中常称为顶点）的前趋和中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即后继个数都是不加限制的，即结点之间的关系是任意的结点之间的关系是任意的。图中任意两个结点之间都可能相关。图中任意两个结点之间都可能相关。图的图的应用应用极为广泛，特别是近年来的迅速发展，已渗透到极为广泛，特别是近年来的迅速发展，已渗透到诸如诸如语言学、逻辑学、物理、化学、电讯工程、计算机科语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。学以及数学的其它分支中。第1页/共141页2 7.1 图的定义 7.2 图的存储结构 7.3

3、图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 第七章 图第2页/共141页3v 图定义 图G由两个集合V和E组成，记为 G=(V,E)其中，V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常V(G)和E(G)分别称为图的顶点集合和边集合。注：E(G)可以为空集。7.1 图的定义和术语第3页/共141页47.1 7.1 图的定义和术语v 图的数据结构的形式化定义 （p156）G=(V,E)其中 V=x|x dataobject E=VR VR=|p(x,y)(x,y V)VR是两顶点间的关系的集合，即边的集合。第4页/共141页5图的图的

4、术语术语 有向图有向图有向图有向图:对一个图对一个图GG，若边集，若边集E(G)E(G)为有向边的集合，则称该图为有向图。为有向边的集合，则称该图为有向图。G1G1=（V，E）V=v1,v2,v3,v4E=,其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)x弧尾y弧头第5页/共141页6图的图的术语术语 无向图无向图无向图无向图:对一个图对一个图GG，若边集，若边集E(G)E(G)为无向边的集合，则称该图为无向图。为无向边的集合，则称该图为无向图。G2 G2=（V，E）V=v1,v2,v3,v4,v5E=(v1,v2),(v1,v3),(v2,v3),

5、(v3,v4),(v2,v5),(v3,v5)其中，(x,y)表示x与y之间的一条连线，称为边（edge）第6页/共141页7图的术语设n为顶点数，e为边或弧的条数 对无向图有：0 e n(n-1)/2 有向图有：0 e n(n-1)证明：对有向图，每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但对无向图，每条边连接2个顶点，故最多为n(n-1)/2 第7页/共141页8图的图的术术语语端点和邻接点端点和邻接点 在一个无向图中，若存在一条边在一个无向图中，若存在一条边v,则称则称v vi i，v vj j为该边的两个为该边的两个端点端点，并称它们互为并称它

6、们互为邻结点邻结点。21453G2第8页/共141页9图的图的术语术语 起点和终点起点和终点起点和终点起点和终点 在一个有向图中，若存在一条边在一个有向图中，若存在一条边,则称该则称该边是顶点边是顶点v vi i的一条的一条出边出边，是，是v vj j的一条的一条入边入边，称，称v vi i是起始端点（或是起始端点（或起点起点），称），称v vj j是终止端点（或是终止端点（或终点终点）,并称它们并称它们互为邻结点互为邻结点.2134G1第9页/共141页10图的图的术术语语 度度度度 图中每个顶点的度是以该顶点为一端点的边的数目。图中每个顶点的度是以该顶点为一端点的边的数目。记为记为 D(V

7、)。入度和出度入度和出度入度和出度入度和出度 对于有向图，入度为以该顶点为终点的边的数对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的数目。目，出度为以该顶点为起点的边的数目。例 D(v1)=3 无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v 为弧头的弧数与以顶点v为弧尾的弧数之和21453G22134G1例 D(v1)=2 第10页/共141页11图的图的术术语语子图子图 设有两个图设有两个图G=（V，E）G=（V，E）中，若中，若V是是V的子集，的子集，E是是E的子集，的子集，则称则称G是是G子图。子图。G2 第11页/共141页12图的图的术术语语 简单

8、图简单图简单图简单图 对不含多重边和自环的图。对不含多重边和自环的图。2145321453简单图非简单图第12页/共141页13图的术语完全图 边达到最大的图 无向完全图：无向完全图：具有具有n(n-1)/2n(n-1)/2条边的简单图条边的简单图称为无向完全图称为无向完全图 有向完全图：有向完全图：具有具有n(n-1)n(n-1)条边的有向图。条边的有向图。稀疏图：稀疏图：边或弧很少的图。边或弧很少的图。稠密图：稠密图：边或弧很多的图。边或弧很多的图。权：权：与图的边或弧相关的数。与图的边或弧相关的数。网：网：边或弧上带有权值的图。边或弧上带有权值的图。第13页/共141页14图的术语路径

9、非空有限点、弧交替序列，W=v0,a1,v1,ak,vk 使得i=1,2,k,弧ai的头vi,尾为vi-1 。路径长度：路径上边或弧的数目第14页/共141页15图的术语简单路径：除首尾两点外，其他各点都不相同的路径称为简单路径。简单路径第15页/共141页16图的术语回路:无重复边的闭路径。环：闭的简单路径，称为环。回路但不是环环第16页/共141页17图的术语连通图：任何两点都有路径的图。无向图：若图中任意两个顶点vi,vj都是连通 的，则称该图是连通图(vivj)有向图：若图中任意两个顶点vi,vj，都存在 从vi到vj 和从 vj到vi的路径，则称 该有向图为强连通图 (vivj)第1

10、7页/共141页18图的术语连通分量：无向图：无向图中极大连通子图，称为 连通分量 有向图：有向图中极大强连通子图，称为 强连通分量第18页/共141页19生成树图的术语生成树 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。有向树 如果一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵有向树。第19页/共141页20生成树、生成森林生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的 是连通图的极小连通子图 包含图中的所有顶点 有且仅有n-1n-1条边 非连通图的生成树则组成一个生成森林

11、。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。第20页/共141页21图有两种存储结构 邻接矩阵 邻接表7.2 7.2 图的存储结构第21页/共141页227.2.1 7.2.1 邻接矩阵邻接矩阵 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。7.2 图的存储结构 无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。在有向图中：在有向图中：第第 i 行行 1 的个数就

12、是顶点的个数就是顶点 i 的出度，的出度，第第 j 列列 1 的个数就是顶点的个数就是顶点 j 的入度。的入度。在无向图中在无向图中,第第 i 行行(列列)1 的个数就是顶点的个数就是顶点i 的度。的度。第22页/共141页23一、邻接矩阵（用二维数组表示）例如：G1的邻接矩阵例如：G2的邻接矩阵无向图的邻接矩阵为对称矩阵G212345G11234第23页/共141页24 对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。对有向图，弧和表示方向不同的两条弧，Aij和Aji表

13、示不同的弧，所以有向图的邻接矩阵一般不具有对称性。邻接矩阵表示法适合于以顶点为主的运算。第24页/共141页25 对于有向图，顶点vi的出度OD(vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID(vi)等于邻接矩阵第i列元素之和，即：对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：OD(vOD(vi i)=)=ID(vID(vi i)=)=TD（vi）=第25页/共141页26 若G是网（有权图），邻接矩阵定义为V2V1V3V435214如图：如图：Wij 若 或 E(G)A i，j =0或 若其它V1 V2 V3 V4V1 V2 V3 V4第26页/共141页27 顶点表顶点表

14、:一个记录各个顶点信息的一维数组，一个记录各个顶点信息的一维数组，邻接矩阵邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数：一个表示各个顶点之间的关系（边或弧）的二维数组。组。使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下：#define MAX_VERTEX_NUM 20 /最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点表AdjMatrix ar

15、cs;/邻接矩阵int vexnum，arcnum;/图的顶点数和弧数 MGraph;由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。第27页/共141页28 邻接表邻接表 图的链式存储结构 1)为每个顶点建立一个单链表，2)第i个单链表中包含顶点Vi的所有邻接顶点。邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。第28页/共141页2925341543533412212123451.无向图邻接表G2123

16、45adjvex nextarcvexdata firstarc第29页/共141页302.有向图邻接表234143121234如图G1的邻接表为：G11234第30页/共141页31 在邻接表的在邻接表的边链表边链表中，各个边结点的链入顺序中，各个边结点的链入顺序任意任意，视，视边结点输入次序而定。边结点输入次序而定。设图中有设图中有 n n 个顶点，个顶点，e e 条边，则用邻接表表示条边，则用邻接表表示无向图无向图时，时，需要需要 n n 个顶点结点，个顶点结点，2 2e e 个边结点；用邻接表表示个边结点；用邻接表表示有向图有向图时，时，若不考虑逆邻接表，只需若不考虑逆邻接表，只需 n

17、 n 个顶点结点，个顶点结点，e e 个边结点。个边结点。建立邻接表的建立邻接表的时间复杂度时间复杂度为为O(n*e)O(n*e)。若顶点信息即为顶若顶点信息即为顶点的下标，则点的下标，则时间复杂度时间复杂度为为O(n+e)O(n+e)。第31页/共141页32存储表示存储表示typedef struct ArcNodetypedef struct ArcNodeint adjvex;/int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置struct ArcNode *nextarc;/struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 in

18、t int *info;/info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;/ArcNode;/边结点类型边结点类型typedef struct VNodetypedef struct VNodeVertexType data;/VertexType data;/顶点信息顶点信息ArcNode*firstarc;/ArcNode*firstarc;/指向第一条依附该顶点的弧的指针指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;/VNode,AdjListMAX_VERTEX_NUM;/邻接表邻接表typedef structtypedef

19、structAdjList vertices;AdjList vertices;int vexnum,arcnum;/int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 int kind;int kind;/图的种类标志图的种类标志ALGraph;ALGraph;第32页/共141页3325341543533412212123451.无向图邻接表二、邻接表二、邻接表G212345adjvex nextarcvexdata firstarc第33页/共141页341.无向图邻接表对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域

20、.其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息；链域（nextarc）指向下一个与顶点Vi邻接的链表p结点每个链表设一个头结点，头结点结构为：其中：vexdata存放顶点信息（姓名、编号等）；firstarc指向链表的第一个结点。二、邻接表二、邻接表adjvex nextarcvexdata firstarc第34页/共141页35二、邻接表（adjacency list）如图G2的邻接表为：2534154353341221212345G212345第35页/共141页36BACDFE例 20 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2

21、3第36页/共141页372.有向图邻接表234143121234特点：1.n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2.第 i 条链表上的结点数，为 Vi 的出度 （求顶点的出度易，求入度难）（求顶点的出度易，求入度难）如图G1的邻接表为：G11234第37页/共141页381 4230 120 1 2 3 4 A B C D E2.有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。第38页/共141页393.有向图逆邻接表123411431234此时，第i条链表上的结点数，为Vi的入度如图G1的逆邻接表为：G1第39页/共141页40ABECD有向图的逆

22、邻接表A B C D E 30342001234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。在有向图的在有向图的邻接表邻接表中，第中，第 i i 个链表中结点的个数是顶点个链表中结点的个数是顶点ViVi的的出度出度。在有向图的在有向图的逆邻接表逆邻接表中，中，第第 i i 个链表中结点的个数是个链表中结点的个数是顶点顶点ViVi 的的入度入度。第40页/共141页414.带权有向图的邻接表链表中每个结点为三个域.邻接点 权带权图的边结点中带权图的边结点中infoinfo保存该边上的权值保存该边上的权值 。第41页/共141页42ABECD4.带权有向图的邻接表A B C D E 0

23、12341 103 7 0 4 4 22 3 2 8 1022548371 25 顶点顶点 Vi Vi 的边链表的头结点存放在下标为的边链表的头结点存放在下标为 i i 的顶点数组中。的顶点数组中。第42页/共141页43 十字链表十字链表 十字链表十字链表十字链表十字链表(Orthogonal List)(Orthogonal List)是是是是有向图有向图有向图有向图的另一种链式的另一种链式的另一种链式的另一种链式存储结构。存储结构。存储结构。存储结构。可看作是将有向图的邻接表和逆邻接表结合的一种链表。可看作是将有向图的邻接表和逆邻接表结合的一种链表。可看作是将有向图的邻接表和逆邻接表结合

24、的一种链表。可看作是将有向图的邻接表和逆邻接表结合的一种链表。在在在在十字链表十字链表十字链表十字链表中，为每个顶点中，为每个顶点中，为每个顶点中，为每个顶点v v v vi i i i设置一个结点，它包含数设置一个结点，它包含数设置一个结点，它包含数设置一个结点，它包含数据域据域据域据域datadatadatadata和两个链域和两个链域和两个链域和两个链域firstoutfirstoutfirstoutfirstout、firstinfirstinfirstinfirstin，称为，称为，称为，称为顶点结点顶点结点顶点结点顶点结点。数据域数据域数据域数据域datadatadatadata用

25、于存放顶点用于存放顶点用于存放顶点用于存放顶点v v v vi i i i的有关信息；链域的有关信息；链域的有关信息；链域的有关信息；链域firstinfirstinfirstinfirstin指向指向指向指向以顶点以顶点以顶点以顶点v v v vi i i i为弧头的第一个弧结点；链域为弧头的第一个弧结点；链域为弧头的第一个弧结点；链域为弧头的第一个弧结点；链域firstoutfirstoutfirstoutfirstout指向以顶点指向以顶点指向以顶点指向以顶点v v v vi i i i为弧尾的第一个弧结点。为弧尾的第一个弧结点。为弧尾的第一个弧结点。为弧尾的第一个弧结点。弧结点弧结点弧

26、结点弧结点包括四个域：尾域包括四个域：尾域包括四个域：尾域包括四个域：尾域tailvextailvextailvextailvex、头域、头域、头域、头域headvexheadvexheadvexheadvex，链，链，链，链域域域域hlinkhlinkhlinkhlink和和和和tlinktlinktlinktlink。hlinkhlink指向弧头相同的下一条弧，指向弧头相同的下一条弧，tlinktlink指向弧尾相同的下一条弧；指向弧尾相同的下一条弧；datadata顶点信息，顶点信息，firstinfirstin以该顶以该顶点为头的第一个弧结点，点为头的第一个弧结点，firstoutfi

27、rstout以该结点为尾的第一个弧以该结点为尾的第一个弧结点。结点。起点vi 终点vj hlink tlink弧结构顶点结构 data firstin firstout第43页/共141页44图图7-8 7-8 十字链表十字链表 图图7-87-8为图为图7-6(7-6(a)a)有向图的十字链表。见右图有向图的十字链表。见右图 采采用用十十字字链链表表表表示示有有向向图图，很很容容易易找找到到以以顶顶点点v vi i为为弧弧尾尾的的弧弧和和以以顶顶点点v vi i为为弧弧头头的的弧弧，因因此此顶顶点点的的出出度度、入入度度都都很很容容易求得。易求得。第44页/共141页45十字链表的数据类型十字

28、链表的数据类型定义定义如下：如下：#define MAXV#define MAXV typedef struct Arcbox /typedef struct Arcbox /弧结点弧结点 int tailvex,headvex;/int tailvex,headvex;/弧尾和弧头顶点位置弧尾和弧头顶点位置 struct ArcNode*hlink,*tlink;struct ArcNode*hlink,*tlink;/弧头相同和弧尾相同的弧的链域弧头相同和弧尾相同的弧的链域 ArcBox;ArcBox;typedef struct VexNode /typedef struct VexNo

29、de /顶点结点顶点结点 VertexType data;/VertexType data;/顶点信息顶点信息 ArcNode*firstin,*firstout;ArcNode*firstin,*firstout;/分别指向该顶点的第一条入弧和出弧分别指向该顶点的第一条入弧和出弧 VexNode;VexNode;第45页/共141页467.2.4 7.2.4 邻接邻接多重表多重表 邻邻接接多多重重表表是是无无向向图图的的另另一一种种链链式式存存储储结结构构。在在邻邻接接多多重重表表中中设设置置一一个个边边结结点点表表示示图图中中的的一一条条边边。边边结结点点包包含含五个域，结构如下所示：五个

30、域，结构如下所示：其中其中:mark mark 域域 标志域，用于对该边进行标记；标志域，用于对该边进行标记；ivex ivex 域域 存放该边依附的一个顶点存放该边依附的一个顶点v vi i的位置信息；的位置信息；ilink ilink 域域 该链域指向依附于顶点该链域指向依附于顶点v vi i的另一条边的边结点；的另一条边的边结点；jvex jvex 域域 存放该边依附的另一个顶点存放该边依附的另一个顶点v vj j的位置信息；的位置信息；jlink jlink 域域 该链域指向依附于顶点该链域指向依附于顶点v vj j的另一条边的边结点。的另一条边的边结点。邻接多重表为邻接多重表为每个顶

31、点每个顶点设置一个结点，其结构如下：设置一个结点，其结构如下：第46页/共141页47图图7-9 7-9 邻接多重表邻接多重表 图7-9为图7-5(a)无向图的邻接多重表。由由邻邻接接多多重重表表可可以以看看出出，表表示示边边（v vi i，v vj j）的的边边结结点点通通过过链链域域ilinkilink和和jlinkjlink链链入入了了顶顶点点v vi i和和顶顶点点v vj j的的两两个个链链表表中中，实实现现了了用用一一个个边边结结点点表表示示一一个个边边的的目目的的，克克服服了了在在邻邻接接表表中中用用两两个个边边结结点点表表示示一一个个边边的缺点。因此邻接多重表是无向图的一种的缺

32、点。因此邻接多重表是无向图的一种很有效的存储结构很有效的存储结构。第47页/共141页48邻接多重表的结点数据类型邻接多重表的结点数据类型定义定义如下：如下：#define MAXV define MAXV typedef struct /typedef struct /边结点类型边结点类型 int mark;/int mark;/访问标识访问标识 int ivex,jvex;/int ivex,jvex;/该边的两个顶点位置信息该边的两个顶点位置信息 struct Enode*ilink,*jlink;struct Enode*ilink,*jlink;/分别指向依附这两个顶点的下一条边分别

33、指向依附这两个顶点的下一条边 Enode;Enode;typedef struct /typedef struct /顶点结点类型顶点结点类型 VertexType data;/VertexType data;/顶点数据域顶点数据域 ENode*firstedge;/ENode*firstedge;/指向第一条依附该顶点的边指向第一条依附该顶点的边 Vnode;Vnode;第48页/共141页497.3 图的遍历 和和树树的的遍遍历历相相似似，若若从从图图中中某某顶顶点点出出发发访访遍遍图图中中每每个个顶顶点点，且且每每个个顶顶点点仅仅访访问问一一次次，此此过过程程称称为为图图的的遍遍历历。(

34、Traversing Graph)Traversing Graph)。图的遍历远比树的遍历复杂。因为从树根到达树的某个结点只有一条路径，而图的两个顶点之间可能有多条路径。因此，在图的遍历过程中，可能会出现下面的现象，即在顺着一条路径访问了某个顶点后，可能会沿着另一条路径又回到该顶点。为避免一个顶点被多次访问，我们设置一个标志数组int visitedMAX_VERTEX_NUM;它的元素初值为0。一旦vi被访问了，便置相应数组元素为1.图的遍历方法有：这两种方法对无向图和有向图都适用。深度优先搜索遍历（简称DFS）广度优先搜索遍历（简称BFS）第49页/共141页50 深度优先搜索（深度优先搜

35、索（DFSDFS）1 深度优先搜索遍历过程遍历过程：DFS DFS 在在访访问问图图中中某某一一起起始始顶顶点点 v v 后后，由由 v v 出出发发，访访问问它它的的任任一一邻邻接接顶顶点点 w w1 1；再再从从w w1 1出出发发，访访问问与与 w w1 1邻邻接接但但还还没没有有访访问问过过的的顶顶点点 w w2 2；然然后后再再从从 w w2 2 出出发发，进进行行类类似似的的访访问问，如如此此进进行行下下去去，直直至至到到达达所所有有的的邻邻接接顶顶点点都都被被访访问问过过的的顶顶点点 u u 为止。为止。接接着着，退退回回一一步步，退退到到前前一一次次刚刚访访问问过过的的顶顶点点

36、，看看是是否否还还有有其其它它没没有有被被访访问问的的邻邻接接顶顶点点。如如果果有有，则则访访问问此此顶顶点点，之之后后再再从从此此顶顶点点出出发发，进进行行与与前前述述类类似似的的访访问问；如如果果没没有有，就就再再退退回回一一步步进进行行搜搜索索。重重复复上上述述过过程程，直直到到连连通通图图中中所所有有顶点都被访问过为止。顶点都被访问过为止。第50页/共141页51 深度优先搜索的深度优先搜索的深度优先搜索的深度优先搜索的示示示示例例例例 图图中中可可能能存存在在回回路路，且且图图的的任任一一顶顶点点都都可可能能与与其其它它顶顶点点相相通通，在在访访问问完完某某个个顶顶点点之之后后可可能

37、能会会沿沿着着某某些些边边又又回回到到了了曾曾经经访访问问过过的的顶点。顶点。为为了了避避免免重重复复访访问问，可可设设置置一一个个标标志志顶顶点点是是否否被被访访问问过过的的辅辅助助数数组组 visitedvisited ，它它的的初初始始状状态态为为 0 0，在在图图的的遍遍历历过过程程中中，一一旦旦某某一一个个顶顶点点 i i 被被访访问问，就就立立即即让让 visitedvisited i i 为为 1 1，防防止止它它被被多多次访问。次访问。第51页/共141页52 对上图，对上图，深度优先搜索深度优先搜索遍历的遍历的顺序顺序（之一）为：（之一）为：v v1 1 v v2 2v v4

38、 4 v v8 8 v v5 5v v6 6v v3 3v v7 7。图图7-10 7-10 深度优先搜索深度优先搜索 第52页/共141页53深度优先搜索深度优先搜索算法：算法：int visitedMAX_VERTEX_NUM;void DFS(ALGraph G,int v)ArcNode*p;printf(%c,G.verticesv.data);visitedv=1;p=G.verticesv.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/从第v个顶点出发DFS第53页/共141页54整个图的DFS

39、遍历void DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;v0 dowhile f0 do(i)delete(Queue,f,r,x);/(i)delete(Queue,f,r,x);/队首元素出队并赋于队首元素出队并赋于x x(ii)(ii)对所有对所有x x的邻接点的邻接点w w if visitedw=0 then if visitedw=0 then（a a）访问访问w;w;（b b）visitedw=1;visitedw=1;（c c）insert(Queue,f,r,w);/winsert(Qu

40、eue,f,r,w);/w进队列进队列 第57页/共141页58 void BFSseach(Graph G,int Visited,int n)for(v=0;vn;+v)visitedv=0;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问 visitedv=1;Visit(v);/访问u EnQueue(Q,v);/v入队列 while(!QueueEmpty(Q)u=DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdj

41、Vex(G,u,w)if(!visitedw)visitedw=1;Visit(w);EnQueue(Q,w);/访问的顶点w入队列 /if /while /BFSTraverse第58页/共141页59课堂练习练习1、写出右图的邻接矩阵表示。ACBDEF第59页/共141页60课堂练习练习2、写出右图的邻接表表示。ACBDEF543210FE DCBA 1 2 0 4 5 3 5 3 4第60页/共141页61课堂练习练习3、根据右图的如下存储表示，写出以顶点A为出发点进行DFS的顶点访问序列。ACBDEF543210FE DCBA 1 2 0 4 5 3 5 3 4A，B，D，E，F，C第

42、61页/共141页62课堂练习ACBDEF543210FE DCBA 1 2 0 4 5 3 5 3 4A，B，C，D，E，F练习4、根据右图的如下存储表示，写出以顶点A为出发点进行BFS的顶点访问序列。第62页/共141页63n n使用不同的遍历图的方法，可以得到不同的生成树；从不使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。同的顶点出发，也可能得到不同的生成树。n n按照生成树的定义，按照生成树的定义，n n n n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n n n n 个顶点、个顶点、n-n-n-n-1 1 1 1 条边。条边。n

43、 n构造最小生成树的准则构造最小生成树的准则n n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n n n n-1-1-1-1 条边来联结网络中的条边来联结网络中的 n n n n 个顶点；个顶点；n n不能使用产生回路的边；不能使用产生回路的边；n n各边上的权值的总和达到最小。各边上的权值的总和达到最小。最小生成树最小生成树 第63页/共141页64普里姆普里姆(Prim)(Prim)(Prim)(Prim)算法算法n n普里姆算法的普里姆算法的基本思想基本思想：从连通网络从连通网络 N N N N=V V V V,E E E E 中的某一顶点中的某一顶点 u u u u0 0 0

44、0 出发出发,选择与它选择与它关联的关联的具有具有最小权值的边最小权值的边(u u u u0 0 0 0,v v v v),),),),将其将其顶顶点加入点加入到生成树顶点集合到生成树顶点集合U U U U中。中。以后每一步从一个顶点在以后每一步从一个顶点在 U U U U 中中,而另一个顶点不在而另一个顶点不在 U U U U 中的各条边中中的各条边中选择权值最小的边选择权值最小的边(u u u u,v v v v),),),),把它的顶点加把它的顶点加入到集合入到集合 U U U U 中。如此中。如此继续继续下去下去,直到网络中的所有顶点直到网络中的所有顶点都加入到生成树顶点集合都加入到生

45、成树顶点集合 U U U U 中为止。中为止。n n采用采用邻接矩阵作为图的存储表示邻接矩阵作为图的存储表示。第64页/共141页65252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212第65页/共141页66普里姆普里姆(Prim)(Prim)(Prim)(Prim)算法算法n n在构造过程中，还设置了两个在构造过程中，还设置了两个在构造过程中，还设置了两个在构造过程中，还设置了两个辅助数组辅助数组辅助数组辅助数组：uu

46、 lowcost lowcost 存存存存放放放放生生生生成成成成树树树树顶顶顶顶点点点点集集集集合合合合内内内内顶顶顶顶点点点点到到到到生生生生成成成成树树树树外外外外各顶点的各边上的各顶点的各边上的各顶点的各边上的各顶点的各边上的当前最小权值当前最小权值当前最小权值当前最小权值；uu nearvex nearvex 记记记记录录录录生生生生成成成成树树树树顶顶顶顶点点点点集集集集合合合合外外外外各各各各顶顶顶顶点点点点距距距距离离离离集集集集合合合合内哪个顶点最近内哪个顶点最近内哪个顶点最近内哪个顶点最近(即即即即权值最小权值最小权值最小权值最小)。50461322810251424221

47、61812第66页/共141页67普里姆普里姆普里姆普里姆(Prim)(Prim)算法算法算法算法若选择从顶点若选择从顶点若选择从顶点若选择从顶点0 0出发，即出发，即出发，即出发，即u u0 0=0=0，则两个辅，则两个辅，则两个辅，则两个辅助数组的初始状态为：助数组的初始状态为：助数组的初始状态为：助数组的初始状态为：0 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 65046132281025142422161812第67页/共141页68然后然后然后然后反复反复反复反复做以下工作做以下工作做以下工作做以下工作n n在在 lowcost l

48、owcost 中选择中选择 nearvexi nearvexi -1&-1&lowcostilowcosti最小最小的边的边,用用 v v 标记它。则选中的标记它。则选中的权值最小的权值最小的边边为为(nearvexv,v),(nearvexv,v),相应的相应的权值权值为为 lowcostv lowcostv。n n将将 nearvexv nearvexv nearvexv nearvexv 改为改为-1,-1,-1,-1,表示它已加入生成树顶点集合表示它已加入生成树顶点集合,将边将边(nearvexv,v,lowcostv)(nearvexv,v,lowcostv)(nearvexv,v,

49、lowcostv)(nearvexv,v,lowcostv)加入加入生成树的边集生成树的边集合。合。n n取取 lowcosti=min lowcosti,Edgevi lowcosti=min lowcosti,Edgevi lowcosti=min lowcosti,Edgevi lowcosti=min lowcosti,Edgevi，即，即用生成树顶点集合外各顶点用生成树顶点集合外各顶点 i i i i 到刚加入该集合的新顶点到刚加入该集合的新顶点 v v v v 的的距离距离 Edgevi Edgevi Edgevi Edgevi 与与原来它们到生成树顶点集合中顶点的原来它们到生成树

50、顶点集合中顶点的最短距离最短距离lowcosti lowcosti lowcosti lowcosti 做做比较比较,取取距离近的作为这些集合外顶距离近的作为这些集合外顶点到生成树顶点集合内顶点的点到生成树顶点集合内顶点的最短距离最短距离。1.1.1.1.如果生成树顶点集合外顶点如果生成树顶点集合外顶点 i i i i 到刚加入该集合的新顶到刚加入该集合的新顶点点 v v v v 的的距离比距离比原来它到生成树顶点集合中顶点的原来它到生成树顶点集合中顶点的最短距离还最短距离还要近要近，则修改，则修改nearvexi:nearvexi=vnearvexi:nearvexi=vnearvexi:n