数据结构与算法设计ppt课件

1、;第 2 页7.1 7.1 图的术语与定义图的术语与定义l图的定义图的定义l图图(Graph)图图G是由两个集合是由两个集合 V(G) 和和E(G) 组成的，记为组成的，记为 G=(V,E)l 其中：其中：V(G) 是顶点的非空有限集是顶点的非空有限集l E(G) 是边的有限集合，边是顶是边的有限集合，边是顶点的无序对或有序对。点的无序对或有序对。l图的分类图的分类l 有向图有向图l 无向图无向图;第 3 页7.1 7.1 图的术语与定义图的术语与定义l图的定义图的定义l有向图有向图有向图有向图G是由两个集合是由两个集合 V(G) 和和E(G) 组成的。组成的。l 其中：其中：l V(G) 是

2、顶点的非空有限集。是顶点的非空有限集。l E(G) 是有向边也称弧的有限是有向边也称弧的有限集合，弧是顶点的有序对，记为集合，弧是顶点的有序对，记为 ，v、w是顶点，是顶点，v为弧尾，为弧尾，w为弧头。为弧头。;第 4 页7.1 7.1 图的术语与定义图的术语与定义l例如：例如：l G1 = l V1 = A, B, C, D, E l E1 = , , , , , , EACBD;第 5 页7.1 7.1 图的术语与定义图的术语与定义l图的定义图的定义l无向图无向图无向图无向图G是由两个集合是由两个集合 V(G) 和和E(G) 组成的。组成的。l其中：其中：l V(G) 是顶点的非空有限集。

3、是顶点的非空有限集。l E(G) 是边的有限集合，边是顶点是边的有限集合，边是顶点的无序对，记为的无序对，记为 (v, w) 或或 (w, v)，并且，并且 (v, w) = (w, v)。;第 6 页7.1 7.1 图的术语与定义图的术语与定义l例如：例如：l G2 = l V2 = v0, v1, v2, v3, v4 lE2 = (v0, v1), (v0, v3), (v1, v2), (v1, v4), (v2, v3), (v2, v4) V0V4V3V1V2;网网(Network)弧或边带权弧或边带权(Weight)的图分别称有向网和无向的图分别称有向网和无向网网ABCDE134

4、1423906617.1 7.1 图的术语与定义图的术语与定义;第 8 页7.1 7.1 图的术语与定义图的术语与定义l图的运用举例图的运用举例l例例1. 交通图公路、铁路交通图公路、铁路l 顶点：地点顶点：地点边：衔接地边：衔接地点的路点的路l例例2. 电路图电路图l 顶点：元件顶点：元件边：衔接元边：衔接元件之间的线路件之间的线路l例例3. 通讯线路图通讯线路图l 顶点：通讯站点顶点：通讯站点边：站边：站点间的连线点间的连线l例例4. 各种流程图各种流程图l如产品的消费流程图。如产品的消费流程图。l 顶点：工序顶点：工序边：各道工边：各道工序之间的顺序关系序之间的顺序关系;第 9 页7.1

5、 7.1 图的术语与定义图的术语与定义图的根本术语图的根本术语邻接点及关联边邻接点及关联边 邻接点：边的两个顶点互为邻接点邻接点：边的两个顶点互为邻接点 关联边：假设边关联边：假设边 e = (v, u), 那么称顶点那么称顶点v、u 关连边关连边 e。顶点顶点V的度的度 = 与与V相关联的边的数目相关联的边的数目e eV0V4V3V1V2;第 10 页7.1 7.1 图的术语与定义图的术语与定义l顶点的度、入度、出度顶点的度、入度、出度在有向图中：在有向图中： l 顶点顶点V的出度的出度 = 以以V为起点的有向边数为起点的有向边数l 顶点顶点V的入度的入度 = 以以V为终点的有向边数为终点的

6、有向边数l 顶点顶点V的度的度 = V的出度的出度+V的入度的入度l ABCDE设图设图G 的顶点数为的顶点数为 n，边数为，边数为 e 图的一切顶点的度数和图的一切顶点的度数和 = 2*e;假设图中有假设图中有 n 个顶点，个顶点，e 条边，那么条边，那么 含有含有e=n(n-1)/2 条边的无向图称作完全图条边的无向图称作完全图(Completed graph) 含有含有e=n(n-1) 条弧的有向图称作条弧的有向图称作 有向完全图有向完全图 假设边或弧的个数假设边或弧的个数 enlogn，那么称作稀疏图，那么称作稀疏图(Sparse graph)，否那么称作稠密图，否那么称作稠密图(De

7、nse graph).BADEC7.1 7.1 图的术语与定义图的术语与定义;第 12 页7.1 7.1 图的术语与定义图的术语与定义l途径、回路途径、回路l 假设假设v1, v2, ,vk为图为图 G=V，E的顶点的顶点序列，假设序列，假设 G为无向图，那么有为无向图，那么有(vi,vi+1)E；或；或者者G为有向图，那么有为有向图，那么有 E；其中；其中(1 i=1k)，v=v1, u=vk，那么称该序列是从顶点，那么称该序列是从顶点v到到顶点顶点u的途径；途径上边的数目称作途径长度。的途径；途径上边的数目称作途径长度。l假设第一个顶点和最后一个顶点一样，那假设第一个顶点和最后一个顶点一样

8、，那么称该序列为回路。么称该序列为回路。l序列中顶点不反复出现的途径定义为简单序列中顶点不反复出现的途径定义为简单途径途径l构成回路的简单途径称其为简单回路构成回路的简单途径称其为简单回路;第 13 页7.1 7.1 图的术语与定义图的术语与定义l例如例如l 在图在图G1中，中，V0, V1, V2, V3 是是 V0 到到 V3 的途径，而且是简单途径；的途径，而且是简单途径；V0, V1, V2, V3, V0 是简单回路。是简单回路。无向图无向图G1有向图有向图G2V0V4V3V1V2V0V1V2V3 在图在图G2中，中，V0, V2, V3 是是 V0 到到 V3 的简的简单途径；单途

9、径； V0, V2, V3, V0 是简单回路。是简单回路。;第 14 页7.1 7.1 图的术语与定义图的术语与定义l连通图连通图l 在无向图在无向图 G= 中，假设对中，假设对任何两个顶点任何两个顶点 v、u 都存在从都存在从 v 到到 u 的的途径，那么称途径，那么称G是连通图。是连通图。 G2: G2: 非连通图非连通图G1: G1: 连通图连通图V0V2V3V1V5V4V0V4V3V1V2;第 15 页7.1 7.1 图的术语与定义图的术语与定义l子图子图l 设有两个图设有两个图 G=(V，E)，G1=(V1，E1)，假设假设 V1 V且且E1 E，那么称，那么称 G1 是是 G 的

10、的子图。子图。l例例(a)(a)(b)(b)(c)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2 (b)、(c) 是是 (a) 的子图的子图;第 16 页7.1 7.1 图的术语与定义图的术语与定义l假设无向图为非连通图，那么各个极大连通假设无向图为非连通图，那么各个极大连通子图称作此图的连通分量。子图称作此图的连通分量。l极大连通子图含义：该子图是极大连通子图含义：该子图是G的连通子的连通子图，将图，将G的任何不在该子图中的顶点参与，的任何不在该子图中的顶点参与，子图不再连通。子图不再连通。连通分量连通分量非连通图非连通图V0V2V3V1V5V4;第 17 页7.1 7.

11、1 图的术语与定义图的术语与定义l强连通图强连通图l 在有向图在有向图 G= 中，假设对中，假设对任何两个顶点任何两个顶点 v、u 都存在从都存在从 v 到到 u 的的途径，那么称途径，那么称G是强连通图。是强连通图。 强连通图强连通图 非强连通图非强连通图V0V1V2V3V0V1V2V3;第 18 页7.1 7.1 图的术语与定义图的术语与定义l假设有向图为非强连通图，它的各个极大强连假设有向图为非强连通图，它的各个极大强连通子图称为它的强连通分量。通子图称为它的强连通分量。l 极大强连通子图含义：该子图是极大强连通子图含义：该子图是 D 的强的强连通子图，将连通子图，将 D 的任何不在该子

12、图中的顶点的任何不在该子图中的顶点参与，子图不再是强连通的。参与，子图不再是强连通的。强连通分量强连通分量 V0 V0 V2 V2 V3 V3 V1 V1V0V1V2V3;第 19 页7.1 7.1 图的术语与定义图的术语与定义l生成树生成树l连通图连通图 G中，包含一切顶点的极小连通子中，包含一切顶点的极小连通子图称为图称为G的生成树。的生成树。l 极小连通子图含义：该子图是极小连通子图含义：该子图是G的连通的连通子图，在该子图中删除任何一条边，子图不子图，在该子图中删除任何一条边，子图不再连通。再连通。l假设假设T是是G的生成树当且仅当的生成树当且仅当T满足如下条满足如下条件：件：lT包含

13、包含G的一切顶点的一切顶点lT是是G的连通子图的连通子图l T中无回路中无回路连通图连通图G1G1G1G1的生成树的生成树V0V4V3V1V2V0V4V3V1V2;207.1 7.1 图的根本操作图的根本操作1、构造的建立和销毁、构造的建立和销毁2、对顶点的访问操作、对顶点的访问操作3、对邻接点的操作、对邻接点的操作4、插入或删除顶点、插入或删除顶点5、插入和删除弧、插入和删除弧6、遍历、遍历;217.1 7.1 图的根本操作图的根本操作构造的建立和销毁构造的建立和销毁CreatGraph(&G, V, VR):按定义按定义(V, VR) 构造图构造图DestroyGraph(&

14、;G):销毁图销毁图对顶点的访问操作对顶点的访问操作LocateVex(G, u); 假设假设G中存在顶点中存在顶点u，那么前往该顶点在图中，那么前往该顶点在图中“位置位置 ；否那么前往其它信息否那么前往其它信息GetVex(G, v); 前往前往 v 的值的值PutVex(&G, v, value);对对 v 赋值赋值value;227.1 7.1 图的根本操作图的根本操作对邻接点的操作对邻接点的操作FirstAdjVex(G, v); 前往前往 v 的的“第一个邻接点第一个邻接点 。假设该顶点在假设该顶点在 G 中没有邻接点，那么前往中没有邻接点，那么前往“空空NextAdjVex

15、(G, v, w); 前往前往 v 的相对于的相对于 w 的的 “下一个邻接点。下一个邻接点。假设假设 w 是是 v 的最后一个邻接点，那么前往的最后一个邻接点，那么前往“空。空。插入或删除顶点插入或删除顶点InsertVex(&G, v); 在图在图G中增添新顶点中增添新顶点vDeleteVex(&G, v);删除删除G中顶点中顶点v及其相关的弧及其相关的弧;237.1 7.1 图的根本操作图的根本操作插入和删除弧插入和删除弧DeleteVex(&G, v);删除删除G中顶点中顶点v及其相关的弧及其相关的弧DeleteArc(&G, v, w); 在在G中删除

16、弧中删除弧假设假设G是无向的，那么还删除对称弧是无向的，那么还删除对称弧遍历遍历DFSTraverse(G, v, Visit(); 从顶点从顶点v起深度优先遍历图起深度优先遍历图G并对每个顶点调用函数并对每个顶点调用函数Visit一次且仅一次一次且仅一次BFSTraverse(G, v, Visit(); 从顶点从顶点v起广度优先遍历图起广度优先遍历图G，并对每个顶点调用函数并对每个顶点调用函数Visit一次且仅一次一次且仅一次;247.2 7.2 图的存储表示图的存储表示 1、图的数组、图的数组(邻接矩阵邻接矩阵)存储表示存储表示 2、图的邻接表存储表示、图的邻接表存储表示 3、有向图的十

17、字链表存储表示、有向图的十字链表存储表示 4、无向图的邻接多重表存储表示、无向图的邻接多重表存储表示;第 25 页7.2 7.2 图的存储构造图的存储构造一、数组表示法邻接矩阵表示一、数组表示法邻接矩阵表示 邻接矩阵：邻接矩阵：G的邻接矩阵是满足如下条件的邻接矩阵是满足如下条件的的n阶矩阵：阶矩阵：Aij=Aij=1 1 假设假设(vi,vj)(vi,vj)E E 或或 E E0 0 否那么否那么0 1 0 1 00 1 0 1 00 1 0 10 1 0 10 1 0 1 10 1 0 1 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0在数组表示法中，用邻接在数组表示法中

18、，用邻接矩阵表示顶点间的关系矩阵表示顶点间的关系0 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 10 0 00 0 0V1V2V3V4V1V5V4V2V3vivi的度？的度？第第 i i 行行 ( (列列) 1 ) 1 的个数。的个数。vivi的出度的出度? ?vi vi 的入度？的入度？;第 26 页7.2 7.2 图的存储构造图的存储构造二、邻接表二、邻接表邻接表是图的链式存储构造邻接表是图的链式存储构造1、无向图的邻接表、无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一顶点：通常按编号顺序将顶点数据存储在一维数组中；维数组中； 边节点：对于每个顶点

19、，用线性边节点链表边节点：对于每个顶点，用线性边节点链表存储关联邻接点编号。存储关联邻接点编号。 0 0 1 1 2 2 3 3 4 4m-1m-1V1V1V2V2V3V3V4V4V5V51 13 3V1V5V4V2V30 02 24 41 13 34 40 02 21 12 2邻接点邻接点的位置的位置共有多少边节点？共有多少边节点？2*e;第 27 页7.2 7.2 图的存储构造图的存储构造ltypedef struct ArcNode / 边结点定义边结点定义l int adjvex; / 邻接点域，邻接点域，l/ 存放与存放与Vi邻接的点在表头数组中的位置邻接的点在表头数组中的位置l s

20、truct ArcNode *next; / 链域，下一条边或链域，下一条边或弧弧l ArcNode;adjvex nextvexdata firstarcltypedef struct tnode/顶点结点定义顶点结点定义l int vexdata; / 存放顶点信息存放顶点信息l ArcNode * firstarc; / 指向第一个边或弧指向第一个边或弧l VNode, AdjList MAX_VERTEX_NUM ;ltypedef struct /图的定义图的定义l AdjList vertices; lint vexnum, arcnum; / 顶点数和顶点数和弧数弧数lint k

21、ind; / 图的种类图的种类l;第 28 页7.2 7.2 图的存储构造图的存储构造l无向图的邻接表的特点无向图的邻接表的特点l 1顶点顶点v的度：等于的度：等于v对应线性链表的对应线性链表的长度；长度；l 2断定两顶点断定两顶点v ，u能否邻接：要看能否邻接：要看v对应线性链表中能否存在对应线性链表中能否存在u 。l 3在在G中增减边：要在两个单链表插中增减边：要在两个单链表插入、删除结点；入、删除结点；l 4设存储顶点的一维数组大小为设存储顶点的一维数组大小为 mm图的顶点数图的顶点数n，图的边数为，图的边数为 e，G占占用存储空间为：用存储空间为：m个点个点+2*e个表节点。个表节点。

22、G占占用存储空间与用存储空间与G的顶点数、边数均有关；适的顶点数、边数均有关；适用于边稀疏的图。用于边稀疏的图。;第 29 页7.2 7.2 图的存储构造图的存储构造二、邻接表二、邻接表2、有向图的邻接表、有向图的邻接表顶点：用一维数组存储按编号顺序顶点：用一维数组存储按编号顺序以同一顶点为起点的弧：用线性出边节点链以同一顶点为起点的弧：用线性出边节点链表存储弧头位置表存储弧头位置1234v1v3v4v2vexdata firstarc 3 2 4 1adjvex nextV1V2V3V4弧头的弧头的位置位置顶点顶点 i 的出度的出度?顶点顶点 i 的出边表长度的出边表长度共有多少边节点？共有

23、多少边节点？e出边表出边表;第 30 页7.2 7.2 图的存储构造图的存储构造二、邻接表二、邻接表3、有向图的逆邻接表、有向图的逆邻接表顶点：用一维数组存储按编号顺序顶点：用一维数组存储按编号顺序以同一顶点为终点的弧：用记录弧尾位置的以同一顶点为终点的弧：用记录弧尾位置的线性入边节点链表存储。线性入边节点链表存储。1234v1v3v4v2vexdatafirstarc 4 1 1 3V1V2V3V4弧尾的弧尾的位置位置顶点顶点 i 的入度的入度?顶点顶点 i 的入边表长度的入边表长度共有多少边节点？共有多少边节点？e入边表入边表;第 31 页7.2 7.2 图的存储构造图的存储构造三、有向图

24、的十字链表表示法三、有向图的十字链表表示法弧结点：弧结点：typedef struct ArcBox int tailvex, headvex; / 弧尾、弧头在表头数组中位置弧尾、弧头在表头数组中位置 struct arcnode *hlink； / 指向弧头一样的下一条弧指向弧头一样的下一条弧 struct arcnode *tlink; / 指向弧尾一样的下一条弧指向弧尾一样的下一条弧 ArcBox;tailvex headvex hlink tlink顶点结点：顶点结点：typedef struct VexNode VertexType data; / 存与顶点有关信息存与顶点有关信息

25、 ArcBox *firstin； / 指向以该顶点为弧头的第指向以该顶点为弧头的第1个弧结点个弧结点 ArcBox *firstout; / 指向以该顶点为弧尾的第指向以该顶点为弧尾的第1个弧结点个弧结点 VexNode;VexNode OLGraphM; data firstin firstout;第 32 页7.2 7.2 图的存储构造图的存储构造三、有向图的十字链表表示法三、有向图的十字链表表示法例例bdacab cd12341 31 23 43 14 34 24 1一样一样弧尾弧尾一样一样弧头弧头;第 33 页7.2 7.2 图的存储构造图的存储构造四、无向图的邻接多重表表示法四、无

26、向图的邻接多重表表示法顶点结点：顶点结点：typedef struct VexBox VertexType data; / 存与顶点有关的信息存与顶点有关的信息 EBox * firstedge; / 指向第一条依靠于该顶点的边指向第一条依靠于该顶点的边 VexBox;VexBox AMLGraphM;data firstedge边结点：边结点：typedef struct node VisitIf mark; / 标志域，记录能否曾经搜索过标志域，记录能否曾经搜索过 int ivex, jvex; / 该边依靠的两个顶点在表头数组中位置该边依靠的两个顶点在表头数组中位置 struct EBo

27、x * ilink, * jlink; /分别指向依靠于分别指向依靠于ivex和和jvex的下一条边的下一条边 EBox;mark ivex ilink jvex jlink;第 34 页7.2 7.2 图的存储构造图的存储构造四、无向图的邻接多重表表示法四、无向图的邻接多重表表示法例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2;第 35 页7.3 7.3 图的遍历图的遍历l图的遍历图的遍历l访遍图中一切的顶点，并且使图中的每个访遍图中一切的顶点，并且使图中的每个顶点仅被访问一次。顶点仅被访问一次。l遍历本质遍历本质l遍历一切连通分量，遍历一切连通分量，l对

28、于连通子图：根据邻接关系遍历一切顶对于连通子图：根据邻接关系遍历一切顶点。点。l设置数组设置数组visited0,n区分未访问的子图区分未访问的子图信息信息l搜索途径搜索途径l深度优先遍历深度优先遍历DFSl广度优先遍历广度优先遍历BFS;第 36 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历DFSl深度优先遍历连通图的过程类似于树的先深度优先遍历连通图的过程类似于树的先根遍历，从图中某个顶点根遍历，从图中某个顶点V 出发，访问此顶出发，访问此顶点，然后依次从点，然后依次从V的各个未被访问的邻接点出的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中一切和发深度优先搜索遍历图

29、，直至图中一切和V有有途径相通的顶点都被访问到途径相通的顶点都被访问到Vw1SG1SG2w2w3w2V;第 37 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历DFS例：例：achdekfach dkfe achkfed访问次序访问次序bg;第 38 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历DFS例：例：bgabchdekfach dkfe achkfedbg访问次序访问次序b g;第 39 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历DFSV1V2V4V5V3V7V6V8例例1深度遍历深度遍历1：V1V2 V4 V8 V5 V6 V3 V7由

30、于没有规定访问邻接点的顺序，所以深度优先由于没有规定访问邻接点的顺序，所以深度优先序列不独一。序列不独一。深度遍历深度遍历2：V1V3 V7 V8 V6 V5 V2 V4;第 40 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历DFS算法算法7.4和和7.5开场开场标志数组初始化标志数组初始化V=0V访问过访问过?DFS(g,v)V=V+1VVexNum终了终了NYYNDFS开场开场访问访问V,置标志置标志求求V邻接点邻接点有邻接点有邻接点w求下一邻接点求下一邻接点W访问过访问过终了终了NYNYDFS(G,w);第 41 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍

31、历DFS递归算法递归算法lvoid DFSTrav ( Graph G, lVoid ( * Visit ) ( VertexType e ) )l l for ( v=0; v G.vexnum; +v ) l visitedv = FALSE;l for ( v=0; vG.vexnum; +v )l if ( ! visited v ) l DFS( G, v, Visit );l /DFSTrav访问标志数组：访问标志数组：int visited 全局变量，初始时一切分量全为全局变量，初始时一切分量全为FALSE;第 42 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历D

32、FS递归算法递归算法lvoid DFS( Graph G, int v,l void ( * Visit ) ( VertexType e ) )l /* 从从v出发出发v是顶点位置，深度优先遍历是顶点位置，深度优先遍历v所在所在的连通分量的连通分量 */l visitedv = TRUE;l Visit( v ); /先根遍历先根遍历l for ( w = FirstAdjVex( G, v ); w;l w = NextAdjVex( G, v, w ) )l if ( ! visited w ) l DFS( G, w, Visit( w ) ); l /DFS;第 43 页7.3 7.

33、3 图的遍历图的遍历l图的深度遍历图的深度遍历DFS递归算法递归算法V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V4;第 44 页7.3 7.3 图的遍历图的遍历l图的深度遍历图的深度遍历DFS递归算法递归算法V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：深度遍历：V1

34、V3 V7 V6 V2 V4 V8 V5;第 45 页7.3 7.3 图的遍历图的遍历l深度优先遍历的时间复杂度深度优先遍历的时间复杂度lDFS对每一条边处置一次无向图的对每一条边处置一次无向图的每条边从两个方向处置，每个顶点访问每条边从两个方向处置，每个顶点访问一次。一次。l邻接表表示总代价为：邻接表表示总代价为：O( 点数点数n + 边数边数e )l邻接矩阵表示邻接矩阵表示l查询单个顶点的一切邻接点信息，需求查询单个顶点的一切邻接点信息，需求O(n)的时间，所以总代价为的时间，所以总代价为 O(n2) 。;第 46 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFSl从图中

35、某顶点从图中某顶点v出发：出发：l 1)访问顶点访问顶点v；l 2)访问访问v一切未被访问的邻接点一切未被访问的邻接点w1,w2,wk；l 3)依次从这些邻接点出发，访问其一依次从这些邻接点出发，访问其一切未被访问的邻接点。依此类推，直至图切未被访问的邻接点。依此类推，直至图中一切和中一切和V0有途径相通的顶点都被访问到。有途径相通的顶点都被访问到。;第 47 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS例：例：abchdekfgacdef h k achkfed访问次序访问次序;第 48 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS递归算法递归算法

36、开场开场标志数组初始化标志数组初始化V=0V访问过访问过BFSV=V+1VVexnum终了终了NYYN;第 49 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS递归算法递归算法lvoid BFSTraverse ( Graph G, l void (* Visit) ( VertexType ) ) ll /本算法对图本算法对图G进展广度优先遍历进展广度优先遍历l for ( v=0; vG.vexnum; +v )l visitedv = FALSE; / 访问标志数组初始化访问标志数组初始化l for ( v=0; vG.vexnum; +v )l if ( ! vis

37、itedv )l BFS( G, v, Visit );l /BFSTraverse;第 50 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS算法算法7.6开场开场访问访问V0,置标志置标志求求V邻接点邻接点ww存在吗存在吗V下一邻接点下一邻接点ww访问过访问过终了终了NYNYBFS初始化队列初始化队列V0入队入队队列空吗队列空吗队头队头V出队出队访问访问w,置标志置标志w入队入队NY;第 51 页7.3 7.3 图的遍历图的遍历void BFS( Graph G, int v, void(* Visit) (VertexType e) ) / 从第从第v个顶点出发个顶点出

38、发 InitQueue(Q); / 建立辅助空队列建立辅助空队列Q Visit(v); visitedv=TRUE; / 访问访问u，访问标志数组，访问标志数组 EnQueue(Q,v); / v入队入队 while ( ! QueueEmpty( Q ) ) DeQueue(Q,u); / 队头元素出队，并赋值给队头元素出队，并赋值给u for ( w=FirstAdjVex(G,u); w; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) Visit(w); visitedw=TRUE; / 访问访问u EnQueue(Q,w); /while /BFS;第

39、 52 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS例例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：遍历序列：10 1 2 3 4 54fr遍历序列：遍历序列：1 40 1 2 3 4 54 3fr遍历序列：遍历序列：1 4 3;第 53 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS例例142350 1 2 3 4 54 3 2fr遍历序列：遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：遍历序列：1 4

40、3 20 1 2 3 4 5 3 2 5fr遍历序列：遍历序列：1 4 3 2 512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 2;第 54 页7.3 7.3 图的遍历图的遍历l图的广度遍历图的广度遍历BFS例例142350 1 2 3 4 5 2 5fr遍历序列：遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：遍历序列：1 4 3 2 512341342vexdata firstarc 5 5 4 3adjvex next55 1 5

41、 1 1 4 3 2 2;第 55 页7.3 7.3 图的遍历图的遍历l遍历的运用遍历的运用l求两个顶点之间的最短途径长度求两个顶点之间的最短途径长度l 广度优先搜索访问顶点的次序是按广度优先搜索访问顶点的次序是按“途途径长度渐增的次序。求途径长度最短的途径长度渐增的次序。求途径长度最短的途径可以基于广度优先搜索遍历进展。径可以基于广度优先搜索遍历进展。abchdekfg;第 56 页7.4 7.4 图的最小生成树图的最小生成树l生成树生成树l 包含无向图包含无向图 G 一切顶点的极小连通子图一切顶点的极小连通子图称为称为G生成树，它只需生成树，它只需n-1条边，可以构成一条边，可以构成一棵树

42、。棵树。l 极小连通子图含义：该子图是极小连通子图含义：该子图是G的连通的连通子图，在该子图中删除任何一条边，子图不子图，在该子图中删除任何一条边，子图不再连通。再连通。l l 生成树生成树T的特点：的特点：l T是是G的连通子图的连通子图l T包含包含G的一切顶点的一切顶点l T中有中有n-1 条边条边l T中无回路中无回路l连通图连通图G1G1G1G1的生成树的生成树V0V4V3V1V2V0V4V3V1V2;第 57 页7.4 7.4 图的最小生成树图的最小生成树l问题提出问题提出l假设要在假设要在 n 个城市之间建立通讯联络个城市之间建立通讯联络网，那么连通网，那么连通 n 个城市只需求

43、建筑个城市只需求建筑 n-1条线路，如何在最节省经费的前提下建条线路，如何在最节省经费的前提下建立这个通讯网？立这个通讯网？l问题分析和数学建模：问题分析和数学建模：l 顶点顶点表示城市表示城市l 权权城市间建立通讯线路所需破城市间建立通讯线路所需破费代价费代价l希望找到一棵生成树，它的每条边上希望找到一棵生成树，它的每条边上的权值之和即建立该通讯网所需破费的权值之和即建立该通讯网所需破费的总代价最小的总代价最小最小代价生成树最小代价生成树MST(Minimum cost Spanning Tree) l;7.4 7.4 图的最小生成树图的最小生成树l最小生成树最小生成树(Least weig

44、hted spanning tree)：权之和最小的生成树。权之和最小的生成树。V3V3V1V1V4V4V6V6V5V5V2V23 36 65 52 21 16 65 55 54 46 6V3V3V1V1V4V4V6V6V5V5V2V22415V3V3V1V1V4V4V6V6V5V5V2V2;第 59 页7.4 7.4 图的最小生成树图的最小生成树l最小生成树的最小生成树的MST 性质性质l 假设假设U集是集是V的一个非空子集，假设的一个非空子集，假设在一切联接在一切联接U和和V-U的边中，的边中， (u, v)权值权值最小，其中最小，其中uU，vV-U；那么：必有；那么：必有一棵最小生成树包

45、含一棵最小生成树包含(u, v)。 l典型算法典型算法l普里姆普里姆(Prim)算法算法l将顶点归并，与边数无关，适于稠密网。将顶点归并，与边数无关，适于稠密网。l克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法l将边归并，适于求稀疏网的最小生成树。将边归并，适于求稀疏网的最小生成树。;60l根本思想：根本思想：l从初始点从初始点u0开场开场l将将u0作为当前的最小生成树：作为当前的最小生成树：Tl向向T中添加一个节点：中添加一个节点：l从与从与T的节点相连的一切边中不包含两的节点相连的一切边中不包含两个顶点都在个顶点都在T内的边，找到最短的边，内的边，找到最短的边，将该边及相应节点参与将该边及

46、相应节点参与T中中l直到一切的节点都参与直到一切的节点都参与T中为止中为止7.4 7.4 图的最小生成树图的最小生成树;第 61 页7.4 7.4 图的最小生成树图的最小生成树 普里姆算法普里姆算法Prim设设 G=(V, GE) 为一个具有为一个具有 n 个顶点的个顶点的连通网络，连通网络，T=(U, TE) 为生成树。为生成树。(1) 初始时，初始时，U = u0，TE = ；(2) 在一切在一切 uU 且且 vV-U 的边的边 (u, v) 中选择一条权值最小的边，无妨设为中选择一条权值最小的边，无妨设为(u,v)；(3) (u,v) 参与参与TE，同时将，同时将 v 参与参与U；(4)

47、 反复反复(2)(3)，直到，直到 U=V 为止；为止；;第 62 页7.4 7.4 图的最小生成树图的最小生成树 普鲁姆算法普鲁姆算法Prim教材教材P175V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 6V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 12 2V3V3V1V1V4V4V6V6V5V5V2V21 14 4V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 42 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21

48、 14 45 52 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 45 53 3U= V1 U= V1 U= V1,V3 U= V1,V3 U= V1,V3,V6U= V1,V3,V6U= V1,V3,V6,V4 U= V1,V3,V6,V4 U= V1,V3,V6,V4,V2 U= V1,V3,V6,V4,V2 U= V1,V3,V6,V4,V2,V5 U= V1,V3,V6,V4,V2,V5 ;第 63 页7.4 7.4 图的最小生成树图的最小生成树l辅助数组辅助数组closedge 对不在生成树中的每个对不在生成树中的每个顶点，记录其和生成树顶点相关

49、联且代价最顶点，记录其和生成树顶点相关联且代价最小的边：小的边：l struct VertexType Adjvex; / 相关顶相关顶点点l VRType lowcost; / 最小边的权最小边的权值值l closedge MAX_VERTEX_NUM ; closedge. Adjvex v ： 顶点顶点v到子集到子集U中权最小边中权最小边 (v, u) 相关联的顶点相关联的顶点u closedge.lowcostv： 顶点顶点v到子集到子集U权最小边权最小边 (v, u) 的权值的权值(间隔间隔);第 64 页7.4 7.4 图的最小生成树图的最小生成树 V1 V1 V1 V1 V1 V

50、1 V1 V1 0 6 1 5 max max 0 6 1 5 max max 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost 3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1 V1 V3 V1 V1 V3 V3 V1 V3 V1 V1 V3 V3 0 5 0 5 6 4 0 5 0 5 6 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost3 36 65

51、52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1;第 65 页7.4 7.4 图的最小生成树图的最小生成树 V3 V1 V1 V3 V3 V3 V1 V1 V3 V3 0 5 0 5 6 4 0 5 0 5 6 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) V3 V1 V6 V3 V3 V3 V1 V6 V3 V3 0 5 0 2 6 0 0 5 0 2 6 0closedge.Adj

52、vex closedge.Lowcost 3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V13 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1;第 66 页7.4 7.4 图的最小生成树图的最小生成树 V3 V1 V6 V3 V3 V3 V1 V6 V3 V3 0 5 0 0 6 0 0 5 0 0 6 0 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65

53、 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1 V3 V1 V6 V3 V3 V3 V1 V6 V3 V3 0 5 0 0 6 0 0 5 0 0 6 0 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6)closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1;第 67 页7.4 7.4 图的最小生成树图的最小生成树 V3 V1 V6 V3 V3 V3 V1 V6 V3 V3 0 0 0 0 3 0 0 0 0 0 3 0 0(V1)

54、 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V13 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1 V3 V1 V6 V3 V3 V3 V1 V6 V3 V3 0 5 0 0 6 0 0 5 0 0 6 0 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6)closedge.Adjvex closedge.Lowcost;第 68 页

55、7.4 7.4 图的最小生成树图的最小生成树 V3 V1 V6 V3 V3 V3 V1 V6 V3 V3 0 0 0 0 0 0 0 0 0 0 0 0 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6)closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V13 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1;第 69 页7.4 7.4 图的最小生成树图的最小生成树void MiniSpanTree_P

56、( MGraph G, VertexType u ) /用普里姆算法从顶点用普里姆算法从顶点u出发构造网出发构造网G的最小生成树的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化辅助数组初始化 if (j!=k) closedgej = u, G.arcskj ; closedgek.Lowcost = 0; / 初始，初始，Uu for ( i=1; iG.vexnum; +i ) 继续向生成树上添加顶点继续向生成树上添加顶点;第 70 页7.4 7.4 图的最小生成树图的最小生成树 k = minimum(

57、closedge); / 求出参与生成树的下一个顶点求出参与生成树的下一个顶点(k) printf(closedgek.Adjvex, G.vexsk); / 输出生成树上一条边输出生成树上一条边 closedgek.Lowcost = 0; / 第第k顶点并入顶点并入U集集 for (j=0; jG.vexnum; +j) /修正其它顶点到生成树修正其它顶点到生成树的最小边的最小边 if ( G.arcskj closedgej.Lowcost ) closedgej = G.vexsk, G.arcskj ; ;第 71 页7.4 7.4 图的最小生成树图的最小生成树l普里姆算法的性能普里

58、姆算法的性能l 设设n是图的顶点数，普鲁姆算法的是图的顶点数，普鲁姆算法的时间复杂度为时间复杂度为O(n2)。l 与边数无关，适用于求边稠密的与边数无关，适用于求边稠密的网的最小生成树。网的最小生成树。;第 72 页7.4 7.4 图的最小生成树图的最小生成树l克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法l设连通网设连通网 N = ( V, E )。l 1) 初始时最小生成树只包含图的初始时最小生成树只包含图的n个顶个顶点，每个顶点为一棵子树；点，每个顶点为一棵子树；l 2) 选取权值较小且所关联的两个顶点选取权值较小且所关联的两个顶点不在同一子树的边，将此边参与到最小生成不在同一子树的边，

59、将此边参与到最小生成树中；树中；l 3) 反复反复2n-1次，即得到包含次，即得到包含n个顶点个顶点和和n-1条边的最小生成树。条边的最小生成树。;第 73 页7.4 7.4 图的最小生成树图的最小生成树l克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法5 56 66 61 15 54 4V3V3V1V1V4V4V6V6V5V5V2V23 36 65 52 216543212345;7.4 7.4 克鲁斯卡尔算法克鲁斯卡尔算法构造非连通图构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数计选中的边数 while (kn-1) +i; 检查边集检查边集 E 中第中第 i

60、 条权值最小的边条权值最小的边(u,v); 假设假设(u,v)参与参与ST后不使后不使ST中产生回路，中产生回路， 那么那么 输出边输出边(u,v); 且且 k+;123456第 75 页7.4 7.4 图的最小生成树图的最小生成树l克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法16543212345datajihe124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222采用边集数组的方式保管图：采用边集数组的方式保管图：5 56 66 61 15 54 4V3V3V1V1V4V4V6V6V5V5V2V23 36