最新图的定义和基本术语图的存储结构图的遍历生成树最短路径幻灯片.ppt

一一 、图的定义、图的定义 本章介绍另一种非线性数据结构 图, 主要学习图的存储结构以及若干图的操作的实现。 图是一种多对多的结构关系，每个元素可以图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。有零个或多个直接前趋；零个或多个直接后继。 图图G由两个集合构成，记作由两个集合构成，记作G= (V, A) 其中其中V是顶点的非空有限集合，是顶点的非空有限集合， A 是边的有限是边的有限集合，其中边是顶点的无序对或有序对集合，其中边是顶点的无序对或有序对(此时此时的图称为的图称为无向图无向图或或有向图有向图) )。DFSTraverse(G, v, Visit() /深度优先遍历 初始条件初始条件: :图图G存在，存在，v 是是G中某个顶点，中某个顶点， Visit是顶点的应用函数是顶点的应用函数 。 操作结果操作结果: : 从顶点从顶点v起深度优先遍历图起深度优先遍历图G，并对每，并对每 个顶点调用函数个顶点调用函数Visit一次且仅一次。一次且仅一次。 一旦一旦Visit（）失败，则操作失败。（）失败，则操作失败。BFSTraverse(G, v, Visit() /广度优先遍历 初始条件初始条件: :图图G存在，存在，v 是是G中某个顶点，中某个顶点， Visit是顶点的应用函数是顶点的应用函数 。 操作结果操作结果: : 从顶点从顶点v起广度优先遍历图起广度优先遍历图G，并对每，并对每 个顶点调用函数个顶点调用函数Visit一次且仅一次。一次且仅一次。 一旦一旦Visit（）失败，则操作失败。（）失败，则操作失败。2 顶点的度、入度、出度顶点的度、入度、出度 顶点顶点v的度的度 TD(v)= 与与v相关联的边的数目。相关联的边的数目。 在有向图中在有向图中：顶点：顶点v的出度的出度OD(v) =以以v为起点有向边数；为起点有向边数； 顶点顶点v的入度的入度ID(v) =以以v为终点有向边数；为终点有向边数； TD(v) = OD(v) + ID(v) V0 V4 V3 V1 V2 V0 V1 V2 V3二、图的基本术语二、图的基本术语1 邻接点及关联边邻接点及关联边 邻接点：边的两个顶点；邻接点：边的两个顶点； 关联边：若边关联边：若边e= (v, u), 则称边则称边e与顶点与顶点 v和和u 相关联；相关联；设图设图G的顶点数为的顶点数为n，边数为，边数为e则图的所有顶点的度数之和则图的所有顶点的度数之和 = 2*e （每条边对图的所有顶点的度数之和（每条边对图的所有顶点的度数之和 “贡献贡献” 2度）度） 无向图无向图G1有向图有向图G2 V0 V4 V3 V1 V2 V0 V1 V2 V3 路径、回路路径、回路(环)无向图无向图G1=（V1，E1）中的顶点序列）中的顶点序列v1,v2, ,vk,若若(vi,vi+1) E1 ( i=1,2,k-1), v =v1, u =vk, 则称该则称该序列是从顶点序列是从顶点v到顶点到顶点u的路径；若的路径；若v=u，则称该，则称该序列为回路；在序列为回路；在G1中，中，v0,v1,v2,v3 是是v0到到v3的路径的路径； v0,v1,v2,v3 , v0是回路；是回路；有向图有向图G2=（V2，E2）中的顶点序列）中的顶点序列v1,v2, ,vk, E2 (i=1,2,k-1),若若v =v1, u =vk,则称该则称该序列是从顶点序列是从顶点v到顶点到顶点u的路径；若的路径；若v=u，则称该，则称该序序列为回路；在列为回路；在G2中，中，v0, v2, v3是是v0到到v3的路径的路径v0,v2,v3,v0是回路；是回路； 简单路径和简单回路简单路径和简单回路 在一条路径中在一条路径中, ,若所有顶点各不相若所有顶点各不相同同, ,则称该路径为简单路径；若除起点和终则称该路径为简单路径；若除起点和终点外点外, , 其余顶点各不相同的回路称为简单回路其余顶点各不相同的回路称为简单回路。 例例有向图有向图G2无向图无向图G1 V0 V4 V3 V1 V2 V0 V1 V2 V3在在图图G1中，中，V0,V1,V2,V3 是简单路径；是简单路径； V0,V1,V2,V4,V1不是简单路径；不是简单路径； 在在图图G2中，中，V0,V2,V3,V0是简单回路；是简单回路； 连通图（强连通图）连通图（强连通图） 在无（有）向图在无（有）向图G=( V, E )中，若对任何中，若对任何两个顶点两个顶点 v、u 都存在从都存在从v 到到 u 的路径，则称的路径，则称G是连通图（强连通图）是连通图（强连通图） 非连通图非连通图 连通图连通图 强连通图强连通图 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4 非强连通图非强连通图设有两个图设有两个图G=（V，E）、）、G1= （V1，E1），），若若V1 V，E1 E，E1关联的顶点都在关联的顶点都在V1中，中，则称则称 G1是是G的子图；的子图； (a)(b)(c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V25 子图子图例 下列 (b)、(c) 是 (a) 的子图 (强)连通分量连通分量 无向图无向图G的的极大连通子图极大连通子图称为称为G的连通分量。的连通分量。 极大连通子图意思是：该子图是极大连通子图意思是：该子图是 G 连通子图，将连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通；的任何不在该子图中的顶点加入，子图不再连通； 连通分量连通分量非连通图非连通图 V0 V2 V3 V1 V5 V4 V0 V2 V1非连通分量非连通分量有向图有向图D 的极大强连通子图的极大强连通子图称为称为D 的强连通的强连通分量。极大强连通子图意思是：该子图是分量。极大强连通子图意思是：该子图是D强连通子图，将强连通子图，将D的任何不在该子图中的顶的任何不在该子图中的顶点加入，子图不再是强连通的。点加入，子图不再是强连通的。强连通分量强连通分量 V0 V1 V2 V3 V0 V2 V3 V1非强连通图非强连通图7 生成树生成树 包含包含无向图无向图G 所有顶点所有顶点的的极小连通子图极小连通子图称为称为G 的的生成树。极小连通子图意思是：该子图是生成树。极小连通子图意思是：该子图是G 的连通子的连通子图，在该子图中删除任何一条边，子图不再连通。图，在该子图中删除任何一条边，子图不再连通。 G的生成树的生成树 V0 V4 V3 V1 V2连通图连通图 G V0 V4 V3 V1 V2 V0 V4 V3 V1 V2若若T是是G 的生成树当且仅当的生成树当且仅当T 满足如下条件：满足如下条件： T是是G 的连通子图；的连通子图； T包含包含G 的所有顶点；的所有顶点； T中无回路。中无回路。一棵一棵n n个顶点的生成树有且仅有足以构成树个顶点的生成树有且仅有足以构成树的的n-1n-1条边。条边。说明：说明：G的生成树的生成树 V0 V4 V3 V1 V2连通图连通图 G V0 V4 V3 V1 V2 V0 V4 V3 V1 V2若在一棵生成树上删除一条边，就不再连通。若在一棵生成树上删除一条边，就不再连通。 若在一棵生成树上添加一条边，必定构成一若在一棵生成树上添加一条边，必定构成一个环。个环。 不再连通不再连通构成环构成环 由于图中任意两个顶点之间都可能存在联由于图中任意两个顶点之间都可能存在联系，因此难以以数据元素在存储区中物理位置系，因此难以以数据元素在存储区中物理位置表示它们间的关系，仍可以借助数组表示之。表示它们间的关系，仍可以借助数组表示之。 另一方面，用也可以多重链表示图。但由另一方面，用也可以多重链表示图。但由于图中顶点的度可能相差悬殊，会因此造成空于图中顶点的度可能相差悬殊，会因此造成空间的浪费；反之，若按每个顶点的度设计不同间的浪费；反之，若按每个顶点的度设计不同的结点结构，又会造成操作上的不便。的结点结构，又会造成操作上的不便。 应根据具体的图和需要，设计恰当的结应根据具体的图和需要，设计恰当的结点结构和表结构。点结构和表结构。图的存储结构图的存储结构至少要保存两类信息：至少要保存两类信息： 1)1)顶点的数据；顶点的数据； 2)2)顶点间的关系顶点间的关系。 如何表示顶点间的关系？ V0 V4 V3 V1 V2 V0 V1 V2 V3常用图的存储表示常用图的存储表示一、图的数组一、图的数组(邻接矩阵)存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示邻接矩阵邻接矩阵：G的邻接矩阵是满足如下条件的的邻接矩阵是满足如下条件的n阶矩阵：阶矩阵： Aij=1 若若(vi,vj) E 或或 E0 否则否则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 01 10 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0 V0 V4 V3 V1 V2 V0 V1 V2 V3一、数组表示法一、数组表示法( (邻接矩阵表示邻接矩阵表示) )在数组表示法中，在数组表示法中，用邻接矩阵表示顶点间的关系用邻接矩阵表示顶点间的关系typedef struct ArcCell / 弧的定义 VRType adj;/VRType是顶点关系类型。对无权图， /用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell , AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM; / 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20/最大顶点个数typedef enumDG,DN,UDG, UDN graphkind； /有向图，有向网，无向图，无向网typedef struct /图的定义 VertexType vexsMAX_VERTEX_NUM; /顶点向量保存顶点数据 AdjMatrix arcs; /邻接矩阵保存顶点间关系 int vexnum, arcnum; /顶点数，弧数 GraphKind kind; /图的种类标志 MGraph;无向图数组表示法特点：无向图数组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；）无向图邻接矩阵是对称矩阵，同一条边表示了两次；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 01 10 1 1 0 00 1 1 0 0对对有向图有向图的数组表示法的数组表示法可做类似的讨论可做类似的讨论 V0 V4 V3 V1 V22）顶点）顶点v的度：等于二维数组对应行（或列）中的度：等于二维数组对应行（或列）中1的个数；的个数；3）判断两顶点）判断两顶点v、u是否为邻接点：只需判二维数组对应是否为邻接点：只需判二维数组对应分量是否非零；分量是否非零；4）顶点不变，在图中）顶点不变，在图中增加增加、删除删除边：只需对二维数组对边：只需对二维数组对应分量应分量赋非零值赋非零值或或清零清零；5）用二维数组存储顶点数为）用二维数组存储顶点数为 n的图的图, 占用存储空间只与它占用存储空间只与它的顶点数的顶点数n有关，与边数有关，与边数e无关。适用于边稠密的图。无关。适用于边稠密的图。 图的基本操作的实现图的基本操作的实现(采用数组表示法)：1）求无向图某顶点）求无向图某顶点vi的度：的度：(或有向图或有向图vi的出度的出度) Ai0 到到Ain-1中的非零个数，即数组中的非零个数，即数组A第第i行的行的非零元素的个数；非零元素的个数；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 01 10 1 1 0 00 1 1 0 0 V0 V4 V3 V1 V2 V0 V1 V2 V30 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 02）求有向图某顶点）求有向图某顶点vi 的的 入度：入度：A0i到到An-1i 中中的非零个数，即数组的非零个数，即数组A中第中第i列的非零元素的个数；列的非零元素的个数；3）求图中的总边数：扫描整个数组）求图中的总边数：扫描整个数组A，统计出数组，统计出数组中非零元素的个数。无向图的总边数为非零元素个中非零元素的个数。无向图的总边数为非零元素个数的一半，而有向图的总弧数为非零元素个数。数的一半，而有向图的总弧数为非零元素个数。图的构造操作的实现图的构造操作的实现(采用数组表示法)Status CreateGraph(Mgraph &G) /采用数组表示法, 构造图G scanf(&G.kind); switch(G.kind) case DG: return CreateDG(G); /构造有向图G case DN: return CreateDN(G); /构造有向网G case UDG: return CreateUDG(G);/构造无向图G case UDN: return CreateUDN(G);/构造无向网G default : return ERROR; / CreateGraph无向网的构造算法无向网的构造算法Status CreateUDN(Mgraph &G) /采用数组表示法, 构造无向网G scanf(&G.vexnum, &G.arcnum , &IncInfo); /IncInfo为0则各不含其它信息 for(i=0;i G.vexnum;+i) scanf(G.vexsi); /构造顶点向量 for(i=0;i G.vexnum;+i) /初始化邻接矩阵 for(j=0;j G.vexnum;+j) G.arcsij=INFINITY,NULL; for(k=0;k G.arcnum;+k) /构造邻接矩阵 scanf(&v1, &v2, &w); /输入一条边依附的顶点及权值 i=LocateVex(G,v1); j=LocateVex(G,v2); /确定v1和v2在G中位置 G.arcsij.adj=w; /弧的权值 if (IncInfo) input(* G.arcsij.info) /若弧含有相关信息,则输入 G.arcsji= G.arcsij /置的对称弧 return OK / CreateUDN例例V0V4V3V1V22 0 1 2 3 4V0V1V2V3V413422110034下标顶点头指针编号1 1 无向图的邻接表无向图的邻接表 顶点通常按编号顺序将顶点数据存储在一维顶点通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边用线性链表存储。数组中；关联同一顶点的边用线性链表存储。二、邻接表二、邻接表该结点表示边（该结点表示边（V4, Vj）,其中其中的的j是是Vj在一维数组中的位置在一维数组中的位置0 1 2 3 4 A B C D EABECD可见，在有向图的可见，在有向图的邻接表中不易找到邻接表中不易找到指向该顶点的弧指向该顶点的弧。1 4230 122 2 有向图的邻接表有向图的邻接表ABECD303420 在有向图的逆邻接在有向图的逆邻接表中，对每个顶点，链表中，对每个顶点，链接的是指向该顶点的弧接的是指向该顶点的弧。A B C D E 012343 3 有向图的有向图的逆逆邻接表邻接表typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; / 表结点弧的结点结构弧的结点结构adjvex nextarc info/ 图的邻接表存储表示图的邻接表存储表示typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附自该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; / 头结点、头结点数组类型 data firstarc顶点的结点结构顶点的结点结构typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;图的结构定义图的结构定义(邻接表)无向图的邻接表的特点无向图的邻接表的特点 1）在）在G邻接表中，同一条边对应两个表结点；邻接表中，同一条边对应两个表结点； 2）顶点）顶点v的度：等于的度：等于v对应线性链表的长度；对应线性链表的长度； 3）判定两顶点）判定两顶点v ，u是否邻接：要看是否邻接：要看v对应线性链表中对应线性链表中有无对应的结点有无对应的结点u ； 4）在）在G中增减边：在两个单链表插入、删除结点；中增减边：在两个单链表插入、删除结点； 5）设存储顶点的一维数组大小为）设存储顶点的一维数组大小为m(m 图的顶点数图的顶点数n), 图的边数为图的边数为e，G占用存储空间为：占用存储空间为：m+2e，与，与 G 的顶的顶点数、边数均有关，适用于边稀疏的图。点数、边数均有关，适用于边稀疏的图。 0 0 1 1 2 2 3 3 4 4V0V1V2V3V41 13 34 42 22 21 11 10 00 04 43 3邻接表的空间代价邻接表的空间代价与图的边及顶点数均有关与图的边及顶点数均有关 V0 V4 V3 V1 V22 2三、有向图的十字链表存储表示三、有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置弧尾顶点位置 弧头顶点位置弧头顶点位置 弧的相关信息弧的相关信息指向下一个有相指向下一个有相同同弧尾弧尾的结点的结点指向下一个有相指向下一个有相同同弧头弧头的结点的结点typedef struct ArcBox / 弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *tlink, *hlink; ArcBox;顶点的结点结构顶点的结点结构 顶点数据顶点数据 指向该顶点的指向该顶点的第一条第一条入弧入弧指向该顶点的指向该顶点的第一条第一条出弧出弧typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点表头向量 int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表) V1 V2 V3 V4v1v2v3v401232 3 3 2 2 03 13 00 10 2有向图的十字链表有向图的十字链表(图示） 若将有向图的邻接矩阵看成是若将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的链表存储结构。看成是邻接矩阵的链表存储结构。四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; / 分别依附于这两个顶点的下一条边 InfoType *info; / 该边信息指针 EBox;边的结构表示边的结构表示访问访问标记标记端点端点i i位置位置依附依附i i的的下一条边下一条边端点端点j j位置位置依附依附j j的的下一条边下一条边信息信息指针指针顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data; EBox *firstedge; /第一条依附该顶点的边的指针 VexBox;顶点的数据顶点的数据 第一条依附该顶点的边的指针第一条依附该顶点的边的指针 typedef struct / 邻接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;无向图的结构表示无向图的结构表示 V1 V2 V4 V5 V3v1v2v3v4v5012340 10 3 2 12 34 1 2 4 2 4 在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。 在图中，访问某个顶点后，可能沿着某在图中，访问某个顶点后，可能沿着某条路径又回到该顶点。为保证每一个顶点只被条路径又回到该顶点。为保证每一个顶点只被访问一次，必须记下已被访问顶点，访问一次，必须记下已被访问顶点， 有两种遍历方法：有两种遍历方法： 深度优先遍历深度优先遍历和和广度优先遍历广度优先遍历图的遍历算法是图的许多算法的基础。图的遍历算法是图的许多算法的基础。一一 深度优先遍历深度优先遍历1）从中某顶点）从中某顶点v（起始点）出发，访问该顶点；出发，访问该顶点；2）依次从）依次从v的未被访问的邻接点出发，继续对图的未被访问的邻接点出发，继续对图 进行深度优先遍历。进行深度优先遍历。直至图中所有和直至图中所有和v有路径有路径 相通的顶点都被访问到相通的顶点都被访问到； 3）若图中尚有顶点未被访问，则另选一个未被访）若图中尚有顶点未被访问，则另选一个未被访 问顶点作起始点，重复问顶点作起始点，重复1）、）、 2），），直至图中直至图中 所有顶点都被访问到为止所有顶点都被访问到为止。 V0 V7 V6 V5 V4 V3 V2 V1图图G步骤：步骤：说明：说明：( (强强) )连通连通图图的遍历只须执行的遍历只须执行1）和）和 2）两步。）两步。Vw1SG1SG2SG3W1、W2和和W3 均为均为 V 的邻接点，的邻接点，SG1、SG2 和和 SG3 分别为含顶点分别为含顶点W1、W2和和W3 的子图。的子图。访问顶点访问顶点 V ;for (W1、W2、W3 ) 若若该邻接点该邻接点Wi未被访问未被访问， 则则从从它它出发进行深度优先搜索遍历。出发进行深度优先搜索遍历。w2w3w2 V0 V7 V6 V5 V4 V3 V2 V1,V6例求图求图G以以V0起始点的的深度优先序列起始点的的深度优先序列V0V1V3V2V7V5 V4V0 ,V1 ,V4 ,V7 ,V3 ,V2 ,V5 ,V6 V0 ,V1,V3,V7,V4,V2,V5图图GV6由于没有规定访问邻接点的由于没有规定访问邻接点的顺序，深度优先序列不唯一顺序，深度优先序列不唯一 为保证每一个顶点只被访问一次，必为保证每一个顶点只被访问一次，必 须对顶点进行标记。须对顶点进行标记。一般用一个辅一般用一个辅助数组助数组 visited作为对顶点的标记，作为对顶点的标记，当顶当顶点点vi未被访问，未被访问，visitedi值为值为FALSE；当当vi已被访问，则已被访问，则visitedi值为值为TRUE或被访问时的次序号。或被访问时的次序号。说明： 从深度优先搜索遍历连通图的过程类从深度优先搜索遍历连通图的过程类 似于树的先根遍历似于树的先根遍历;如果将图的顶点的未被如果将图的顶点的未被访问邻接点看作树结点的孩子，访问邻接点看作树结点的孩子，图的深度优先遍历与树的图的深度优先遍历与树的先根遍历是先根遍历是类似类似的。的。 图的深度优先遍历图的深度优先遍历 从图中某顶点从图中某顶点v v出发：出发： （1 1）访问顶点）访问顶点v v； （2 2）依次从）依次从v v的未被访问的邻接点的未被访问的邻接点 出发，对图进行深度优先遍历。出发，对图进行深度优先遍历。树的先根遍历树的先根遍历 若树非空若树非空 （1 1）访问根结点；）访问根结点； （2 2）依次先根遍历各）依次先根遍历各 棵子树。棵子树。比较比较类似类似void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w2, V-w8 的路径长度为的路径长度为1;V-w7, V-w3, V-w5的的路径长度为路径长度为2 ; ;V-w6, V-w4 的路径长度为的路径长度为3。w1Vw2w7w6w3w8w5w4说明：在广度优先遍历图时， “先被访问的顶点的邻接点” 先于“后被访问的顶点的邻 接点”被访问。即以V为起 始点，由近至远，依次访问 和V有路径相通且路径长度 为1，2，的顶点。Q 在广度优先遍历中在广度优先遍历中, ,为使为使“先被访问的顶点先被访问的顶点, ,其邻其邻接点亦先被访问接点亦先被访问” ” , ,需附设队列需附设队列Q保存被访问过的顶点保存被访问过的顶点，并控制遍历顶点的顺序。并控制遍历顶点的顺序。V0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7 V0 V7 V6 V5 V4 V3 V2 V1 算法开始时算法开始时, ,将起始点访问后将起始点访问后插入插入Q中中, , 以后以后, ,当当Q不空不空时就从时就从Q中删除一个顶点中删除一个顶点, ,每每删除一个顶点删除一个顶点, ,就依次访问它的每一个未被访问过的邻就依次访问它的每一个未被访问过的邻接点接点, ,并令其进队。这样并令其进队。这样, ,当当Q为空为空时时, ,表明所有与起始表明所有与起始点有路径相通的顶点都已访问完毕。点有路径相通的顶点都已访问完毕。 V0 V7 V6 V5 V4 V3 V2 V1 V2void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 visitedv = TRUE; Visit(v); EnQueue(Q, v);/ v入队列 while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w ; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / BFSTraverse 图的广度优先遍历算法图的广度优先遍历算法求一条从顶点求一条从顶点 i 到顶点到顶点 s 的简单路径的简单路径abchdekfg 求从顶点求从顶点 b 到顶点到顶点 k 的的 一条简单路径。一条简单路径。 从顶点从顶点 b 出发进行出发进行深度优先搜索遍历深度优先搜索遍历例如例如: 假设找到的第一个邻接点是假设找到的第一个邻接点是a, 则得到的结点访问序列为则得到的结点访问序列为: b a d h c e k f g 假设找到的第一个邻假设找到的第一个邻接点是接点是c,则得到的结点则得到的结点访问序列为访问序列为: b c h d a e k f g遍历应用的一个例子遍历应用的一个例子无向连通图无向连通图G的生成树的生成树 生成树是一个图生成树是一个图G 的一个极小的连通子图，包含图的一个极小的连通子图，包含图G 的所有顶点，但只有的所有顶点，但只有n-1 条边。生成树可由遍历过条边。生成树可由遍历过程中所经过的边组成。程中所经过的边组成。深度优先遍历深度优先遍历得到的得到的生成树称生成树称为为深度优先深度优先生成树生成树；广广度优先遍历度优先遍历得到的得到的生成树称为生成树称为广广度优先度优先生成树生成树。 V0 V7 V6 V5 V4 V3 V2 V1 V3 V0 V7 V6 V5 V4 V2 V1深度优先深度优先生成树生成树(连通网的)广广度优先度优先生成树生成树 在在n个城市间建立通讯个城市间建立通讯联络网，要考虑的问题是联络网，要考虑的问题是:如何在保证如何在保证n点连通的前提点连通的前提下最节省经费下最节省经费3 36 65 52 21 16 65 55 5V5V4V2V0V3V14 46 6例例即要构造连通网N的最小生成树。这应在这应在 N的的所有所有带权的边中选取带权的边中选取 n1 条边条边（不构成回路），使权值之和为最小。（不构成回路），使权值之和为最小。最小生成树最小生成树（最小支撑树）最小生成树最小生成树是无向连通网的所有生成树中是无向连通网的所有生成树中边的权值之和最小的一棵生成树。的一棵生成树。最小生成树的构造算法最小生成树的构造算法nMST性质性质：多数最小生成树的构造算法都利用了下述多数最小生成树的构造算法都利用了下述性质。性质。 设设N=（V，E）是一个连通网，）是一个连通网，U V，U。若若（u , v）是一条具最小有权值的边，是一条具最小有权值的边，其中其中u U，v VU，则必存在一棵包含，则必存在一棵包含边边（u , v）的最小生成树。的最小生成树。（可用反证法证之）（可用反证法证之） 普里姆普里姆(Prim)算法和克鲁斯卡尔算法和克鲁斯卡尔(Kruskal )算法算法是利用是利用MST性质的两种构造最小生成性质的两种构造最小生成树的算法。树的算法。1. 普里姆算法普里姆算法的基本思想普里姆算法的基本思想:贪心算法贪心算法 任取一图任取一图N中顶点中顶点v 作为生成树的根，之作为生成树的根，之后后不断不断往往“生成树的顶点集生成树的顶点集”U上上添加顶点添加顶点 w ( VU ) 。新添的顶点新添的顶点 w 和已在和已在U的顶点的顶点v 之之间必定存在一条边间必定存在一条边(v , w) ： (v , w) 权值在所有权值在所有连通顶点连通顶点 v ( U )和和 w ( VU ) 之间的边中权之间的边中权值最小的，并将值最小的，并将(v , w)并入并入“生成树的边生成树的边集集”TE中。中。直至直至U =V （ TE中有中有 n-1条边）条边）为为止止。V3V1V4V6V5V26665551324V3V1V4V6V5V2普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程V3V1V4V6V5V2V3V1V4V6V5V2UV-UTEV3V1V4V6V5V2(v1,v3), (v3,v6), (v6,v4),(v3,v2), (v2,v5) 为实现此算法需设置辅助数组为实现此算法需设置辅助数组closedge ，对当前对当前VU中每个顶点，记录从中每个顶点，记录从U到到VU的代价最小的边：的代价最小的边：struct VertexType adjvex; / U集中的顶点序号 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM; 显然，对显然，对vi VU有有closedge i-1. lowcost =Mincost(u, vi)| u Uclosedge0123456AdjvexLowcostiabcdegf195141827168213127aaa19141814例如:e12ee8168d3dd7213c5 516e21edcbagfa b c d e f g所得生成树权值和所得生成树权值和= 14+8+3+5+16+21 = 67 a b c d e f g 0 1 2 3 4 5 6 19 14 1819 5 7 12 5 3 7 3 8 12 8 16 21 2718 16 27 构造最小生成树的构造最小生成树的普里姆算法普里姆算法void MiniSpantree_PRIM( mgraph G, VertexType u ) 辅助数组closedge的定义 k=LocateVex(G,u); for (j=0; jG.vexnum; +j) /辅助数组初始化 if(j!=k) closedgej= u,G.arcskj.arj ; closedgek.lowcost=0; / 起始点u并入U(=u)for (i=1; iG.vexnum; +i) /k=mininum(closedge); /求下一个顶点：第k顶点printf(closedgek.adjvex, G. vexsk) / 输出生成树的边closedgek.lowcost=0; /第k顶点并入Ufor (j=0; jG.vexnum; +j) / 重新选择最小边 if(G.arcskj.arj closedgej.lowcost) closedgej=G.vexsk,G.arcskj.arj 具体做法具体做法: 先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然后从权值最小的边开始，若它的添加，然后从权值最小的边开始，若它的添加不使不使SG 中产生回路，则在中产生回路，则在 SG 上加上这条边，上加上这条边，如此重复，直至加上如此重复，直至加上 n-1 条边为止。条边为止。考虑问题的出发点考虑问题的出发点: 为使生成树上为使生成树上边的权值之和达到最小，则应使生成树中每一条，则应使生成树中每一条边的权值尽可能地小。边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：abcdegf195141816821312727148531621例如例如: :7121819cdbaegf27一、从某个源点到各顶点的最短路径一、从某个源点到各顶点的最短路径V5 V4 1006053010V1 V2 V0 V3102050始始 终终 路径路径点点 点点 长度长度最短路径最短路径v0 v1 无无 v2 (v0,v2) 10v5 (v0,v4 ,v3,v5) 60v4 (v0, v4) 30v3 (v0,v4 ,v3) 50迪杰斯特拉迪杰斯特拉( Dijkstra )算法算法 迪杰斯特拉提出一个求迪杰斯特拉提出一个求按路径长度递增次按路径长度递增次序产生序产生的最短路径算法。其的最短路径算法。其基本思想为基本思想为: 设置设置S为已求得最短路径的终点的集合，并用为已求得最短路径的终点的集合，并用数组数组D记录当前所找到的从源点记录当前所找到的从源点v到每个终点的最到每个终点的最短特殊路径长度短特殊路径长度（特殊路径或是弧，或是中间只经特殊路径或是弧，或是中间只经过过S中顶点的路径中顶点的路径）。初始时，初始时， S为空；为空；Di值为源值为源v到每个顶点到每个顶点vi的权值。的权值。按以下方法不断扩充按以下方法不断扩充S：每每次从次从V S中取出具有最短特殊路径长度的顶点添中取出具有最短特殊路径长度的顶点添加到加到S中，同时对中，同时对D作必要的修改作必要的修改(若若Dj+ arcsjk Dk ，则则 Dk= Dj+ arcsjk ) 。一旦一旦S=V-v( S共扩充n-1次)，D就记录了从源就记录了从源v到其他顶点到其他顶点vi的最短路径长度的最短路径长度（若欲求相应的路径还应另设数组P）。 10 30 100 5 50 10 20 60 邻接矩阵邻接矩阵arcsij 10 30 100V5 V4 1006053010V1 V2 V0 V310205012345DiS iVi10V2, V4, V3V5 V4 V2 V0 V3603050905060, V5V2V4V3V5, V1 60V1源点迪杰斯特拉算法迪杰斯特拉算法 之一之一void ShortPath_DIJ( m