数据结构——第7章 图和广义表1.ppt

《数据结构——第7章 图和广义表1.ppt》由会员分享，可在线阅读，更多相关《数据结构——第7章 图和广义表1.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构的内容数据结构的内容1图的特点图的特点 顶点的前驱和后继个数无限制顶点的前驱和后继个数无限制 图的应用图的应用顶点之间的关系是任意的顶点之间的关系是任意的 图中任意两个顶点之间都可能相关图中任意两个顶点之间都可能相关 图（图（Graph）是一种）是一种非线性结构非线性结构。语语 言言 学学逻逻 辑辑 学学物物 理理化化 学学电信工程电信工程 数数 学学 计算机科学计算机科学 多对多多对多多对多多对多 北京北京 西安西安 南京南京 杭州杭州 开封开封 洛阳洛阳 27.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 连通网的最小连

2、通网的最小生生成树成树7.57.5 单源单源最短路径最短路径7.6 7.6 拓朴排序拓朴排序7.7 7.7 关键路径关键路径7.8 7.8 广义表广义表第第7 7章章 图和广义表图和广义表37.1 7.1 图的基本术语图的基本术语图：图：记为记为 G(V,E)其中：其中：V 是是G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E 是是G的边的边集合，是有穷集。集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每

3、条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；vv若若若若 n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n(n n-1)/2-1)/2 条边条边条边条边,称为称为称为称为无向完全图无向完全图无向完全图无向完全图vv若若若若 n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图有n n(n-n-1)1)条边条边条边条边,称为称为称为称为有向完全图有向完全图有向完全图有向完全图V=vertex E=edge4例：例：判断下列

4、判断下列4种图形各属什么类型？种图形各属什么类型？无向图无向图 无向图无向图(树树)有向图有向图有向图有向图n n(n n-1)/2-1)/2 条边条边条边条边n n(n n-1)-1)条边条边条边条边 完全图完全图 完全图完全图5设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。子子 图：图：带权图：带权图：即边上带权的图。其中即边上带权的图。其中权权是指每条边可以标上是指每条边可以标上具有某种含义的数值（即与边相关的数）。具有某种含义的数值（即与边相关的数）。带权图（带权的有向图与无向图）带权图（带权的有向图与

5、无向图）网网 络：络：6顶点顶点v v的度的度是与它相关联的边的条数。记作是与它相关联的边的条数。记作TD(v)TD(v)。在在有向图有向图中中,顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点 v v 的入度的入度是以是以 v v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(vID(v););顶点顶点 v v 的出度的出度是以是以 v v 为始点的有向边的条数为始点的有向边的条数,记作记作 OD(v)OD(v)。问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的其余顶点的入度均为入度均为1 1，此时是何形状？，此

6、时是何形状？答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！度度入度入度出度出度7简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,.,v vm m 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为则称这样的路径为回路或环回路或环。路径：在图在图在图在图 GG(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发,沿一些边经过一些沿一些边经过一些沿一些边经过一些沿一些边经过一些顶点顶点顶点顶点 v vp p1 1,

7、v vp p2 2,v vpmpm，到达顶点到达顶点到达顶点到达顶点v vj j。则称顶点序列则称顶点序列则称顶点序列则称顶点序列 (v vi i v vp p1 1 v vp p2 2.v vpmpm v vj j )为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的的的的路径路径路径路径。它经过的边。它经过的边。它经过的边。它经过的边(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)应当是属于应当是属于应当是属于应当是属于E E的边。的边。的边。的边。路径长度：非带权图的路径长度是指此

8、路径上非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数边的条数边的条数边的条数；带权图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上各边的权之和。各边的权之和。各边的权之和。各边的权之和。8在在在在无向无向无向无向图中图中图中图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径,则称顶点则称顶点则称顶点则称顶点v v1 1与与与与v v2 2是是是是连通连通连通连通的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的的。

9、如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的,则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图叫做叫做叫做叫做连通分量连通分量连通分量连通分量。在在在在有向有向有向有向图中图中图中图中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点v vi i和和和和v vj j,都存在一条都存在一条都存在一条都存在一条从从从从v vi i到到到到v vj j和和和和从从从从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此

10、图是强连通图强连通图强连通图强连通图。非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做叫做叫做强连通分量强连通分量强连通分量强连通分量。强连通图：连通图：生成树：生成树：是一个是一个是一个是一个极小连通子图极小连通子图极小连通子图极小连通子图，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有n n-1-1条边条边条边条边。vv如果在生成树上添加如果在生成树上添加如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。条

11、边，必定构成一个环。vv若图中有若图中有若图中有若图中有n n个顶点，却少于个顶点，却少于个顶点，却少于个顶点，却少于n n-1-1条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。生成森生成森林：林：由若干棵生成树组成，含全部顶点，但构成这些树由若干棵生成树组成，含全部顶点，但构成这些树由若干棵生成树组成，含全部顶点，但构成这些树由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。的边是最少的。的边是最少的。97.2 7.2 图的存储结构图的存储结构图的特点：非线性结构（图的特点：非线性结构（m:n m:n）邻接表邻接表邻接多重表邻接多重表十

12、字链表十字链表设计为邻接矩阵设计为邻接矩阵链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：无！无！（多个顶点，无序可言）（多个顶点，无序可言）但可但可用用数组数组数组数组描述元素间关系。描述元素间关系。可用多重链表可用多重链表重点介绍：重点介绍：邻接矩阵邻接矩阵(数组数组)表示法表示法邻接表邻接表(链式链式)表示法表示法107.2.1 7.2.1 邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法vv一个有一个有一个有一个有 n n 个顶点的图，可用个顶点的图，可用个顶点的图，可用个顶点的图，可用两个数组两个数组两个数组两个数组存储。其中一个存储。

13、其中一个存储。其中一个存储。其中一个 一维数一维数一维数一维数组存储数据元素组存储数据元素组存储数据元素组存储数据元素（顶点）（顶点）（顶点）（顶点）的信息，另一个的信息，另一个的信息，另一个的信息，另一个二维数组二维数组二维数组二维数组（邻接矩（邻接矩（邻接矩（邻接矩阵）存储数据元素之间的阵）存储数据元素之间的阵）存储数据元素之间的阵）存储数据元素之间的关系关系关系关系（边或弧）的信息。（边或弧）的信息。（边或弧）的信息。（边或弧）的信息。vv设图设图设图设图 G=(G=(V V,E E)有有有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接

14、矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数组组组组 A A n n n n，定义为：定义为：定义为：定义为：v1v2v3v5v4v4G例例例例1 1：邻接矩阵：A=（v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析分析分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是对称对称对称对称的；的；的；的；分析分析分析分析2 2：顶点顶点顶点顶点i i 的的的的度度度度第第第第 i i 行行行行(列列列列)中中中中1 1 的个数的个数的个数的个数；特别：特别：

15、特别：特别：完全图完全图完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余全，其余全，其余全，其余全1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：11例例2：有向图的邻接矩阵有向图的邻接矩阵分析分析分析分析1 1 1 1：有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。分析分析分析分析2 2 2 2：顶点的顶点的出度出度=第第i行元素之和行元素之和，OD(Vi)

16、=A i j 顶点的顶点的入度入度=第第i列元素之和列元素之和。ID(Vi)=A j i 顶点的顶点的度度=第第i行元素之和行元素之和+第第i列元素之和列元素之和,即：即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4G G G G邻接矩阵：A=(v1 v2 v3 v4)v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧(即入度边）。即入度边）。顶点

17、表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 12 容易实现图的操作，如：求某顶点的度、判断容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、顶点的邻接点等等。顶点之间是否有边（弧）、顶点的邻接点等等。n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率空间效率为为O(nO(n2 2)。对对稀疏图稀疏图而言尤其浪费空间。而言尤其浪费空间。特别讨论特别讨论：网（即有权图）的邻接矩阵网（即有权图）的邻接矩阵定义为：定义为：A i j=Wij 或（或（vi,vj）VR 无边

18、（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：N=(v1 v2 v3 v4 v5 v6 )邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：顶点表：5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 13数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院图的数组（邻接矩阵）存储表示：图的数组（邻接矩阵）存储表示：#define INFINITY INT_MAX/最大值最大值#define MAX_VERTEX_NUM 20/最大顶点个数最大顶点个数 typedef

19、enum DG,DN,AG,AN GraphKind;/有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef struct ArcCell VRType adj;/VRType是顶点关系类型。对无权图用是顶点关系类型。对无权图用1或或0表示相邻否；表示相邻否；/对带权图，则为权值类型。对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点向量顶点向量

20、AdjMatrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数 GraphKind kind;/图的种类标志图的种类标志 MGraph;数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院7.2.2 图的邻接表存储表示法（图的邻接表存储表示法（链式存储链式存储 ）头结点头结点 data firstarc 表结点表结点 adjvex nextarc info v2 v1 v3 v4 v5 G2 v1 v3 v4 v2 v5 0 1 2 3 4 3 1 4 2 0 4 3 1 2 0 2 1

21、链域链域链域链域，指示下一条边或弧。，指示下一条边或弧。特点：特点：若无向图中有若无向图中有 n 个顶点、个顶点、e 条边，则其邻接表需条边，则其邻接表需 n 个头个头 结点和结点和 2e 个个表结点。适宜存储稀疏图表结点。适宜存储稀疏图。无向图中顶点无向图中顶点 vi 的度为第的度为第 i 个单链表中的结点数。个单链表中的结点数。邻接点域邻接点域邻接点域邻接点域，存放与，存放与 vi 邻接的邻接的 顶顶点在表头数组中的位置。点在表头数组中的位置。数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院v2 v1 v3 v4 G1 0 1 2 3 2 1 3 0 v

22、1 v3 v4 v2 0 1 2 3 3 0 2 v1 v3 v4 v2 0 邻接表邻接表 逆邻接表逆邻接表 顶点顶点 vi 的的出度出度出度出度为第为第 i 个个 单链表中的结点个数。单链表中的结点个数。特点：特点：顶点顶点 vi 的的入度入度入度入度为整个为整个单单 链表中邻接点域值是链表中邻接点域值是 i-1 的结点个数的结点个数。找出度易，找出度易，找入度难。找入度难。找入度易，找入度易，找出度难。找出度难。顶点顶点 vi 的的入度入度入度入度为第为第 i 个个 单链表中的结点个数。单链表中的结点个数。顶点顶点 vi 的的出度出度出度出度为整个为整个单单 链表中邻接点域值是链表中邻接点

23、域值是 i-1 的结点个数的结点个数。数据结构数据结构 第七章第七章 图和广义表图和广义表韶关学院数信学院韶关学院数信学院图的邻接表存储表示：图的邻接表存储表示：#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息顶点信息 A

24、rcNode *firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 int kind;/图的种类标志图的种类标志 ALGraph;例例例例1 1：无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表v1v2v3v5v4v4例例例例2 2：有向图的邻接表有向图的邻接表有向图的邻接表有向图的邻接表v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V130

25、20逆邻接表逆邻接表(入边入边)注：注：注：注：邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表邻接表4321013341420v5v4v3v2v123142018例例例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！19分析分析1:对于对于n n个顶点个

26、顶点e e条边的无向图条边的无向图，邻接表中除了，邻接表中除了n n个个头结点外，只有头结点外，只有2e2e个表结点个表结点,空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(en2 2)，则比邻接矩阵表示法则比邻接矩阵表示法O(nO(n2 2)省空间。省空间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:在在有向图有向图中，邻接表中除了中，邻接表中除了n n个头结点外，只有个头结点外，只有e e个个表结点表结点,空间效率为空间效率为O(n+e)O(n+e)。若是稀疏图，则比邻接矩阵表示法若是稀疏图，则比邻接矩阵表示法合适。合适。它其实是对邻接矩阵法的一种改进

27、它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算无向图顶点的度？邻接表的邻接表的缺点：缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表需遍历全表邻接表的邻接表的优点：优点：TD(Vi)TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数I D(Vi)邻接点为邻接点为ViVi的弧个数的弧个数TD(Vi)=OD(Vi)+I D(Vi)空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接

28、点；判断两顶点间是否有边或弧，需搜索两结判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。点对应的单链表，没有邻接矩阵方便。20讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？【联系联系】邻接表中每个链表对应于邻接矩阵中的一行，链表中邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。结点个数等于一行中非零元素的个数。【区别区别】对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）

29、。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。【用途用途】邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)21数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中选择题选择题 1.在一个图中，所有顶点的度数之和等于所有边数的在一个图中，所有顶点的度数之和等于所有边数的()倍。倍。（A）1/2（B）1（C）2（D）4 2.在一个有

30、向图中，所有顶点的入度之和等于所有顶点的出度之和的在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。倍。（A）1/2（B）1（C）2（D）4 3.一个有一个有 n 个顶点的无向图最多有个顶点的无向图最多有()条边。条边。（A）n （B）n(n-1)（C）n(n-1)/2 （D）2n 4.具有具有 4 个顶点的无向完全图有个顶点的无向完全图有()条边。条边。（A）6 （B）12 （C）16 （D）20 5.具有具有 6 个顶点的无向图至少应有个顶点的无向图至少应有()条边才能确保是一个连通图。条边才能确保是一个连通图。（A）5（B）6（C）7（D）86.在一个具有在一个具有 n

31、个顶点的无向图中，要连通全部顶点至少需要个顶点的无向图中，要连通全部顶点至少需要()条边。条边。（A）n （B）n+1（C）n 1（D）n/2 数据结构数据结构 第七章第七章 图图制作：制作：计算机科学与技术学院 徐振中7.对于一个具有对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小矩阵的大小 8.为为()。（A）n （B）(n-1)2 （C）n-1 （D）n2 8.对于一个具有对于一个具有 n 个顶点和个顶点和 e 条边的无向图，若采用邻接表表示，条边的无向图，若采用邻接表表示，则表头数则表头数 9.组的大小为组的大小为()，所有邻

32、接表中的结点总数是，所有邻接表中的结点总数是()。（A）n （B）n+1 （C）n-1 （D）n+e（A）e/2 （B）e （C）2e （D）n+e 9.图的深度优先遍历算法类似于树的（图的深度优先遍历算法类似于树的（）。）。（A）先根遍历）先根遍历 （B）后根遍历）后根遍历 （C）按层遍历）按层遍历10.图的广度优先遍历算法类似于树的（图的广度优先遍历算法类似于树的（）。）。（A）先根遍历）先根遍历 （B）后根遍历）后根遍历 （C）按层遍历）按层遍历一、深度优先搜索二、广度优先搜索 7.3 图的遍历图的遍历遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍从已给的连通图中某一顶

33、点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图中所有的顶点，且使每个顶点仅被访问一次，就叫做图图图图的遍历的遍历的遍历的遍历，它是，它是，它是，它是图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可能与其它，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点到了曾经访问过的顶点。解决思路：解决思路：可设置一个可设置一个辅助数组辅助数组 visited n，

34、用来标记每个被用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0 0，在图的遍历过程中，在图的遍历过程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为1 1，防止，防止它被多次访问。它被多次访问。图常用的遍历：图常用的遍历：怎样避免重复访问？怎样避免重复访问？247.3.1 深度优先遍历（深度优先遍历（DFS）（）（类似树的先根遍历）类似树的先根遍历）方法：方法：方法：方法：1、访问指定的起始顶点；访问指定的起始顶点；2、若、若当前访问的顶点当前访问的顶点的邻接顶点有的邻接顶点有未被访问的未被访问的未被访问的未被访问的，则任选，

35、则任选 一个访问之；反之，一个访问之；反之，退回退回退回退回到最近访问过的顶点；直到到最近访问过的顶点；直到 与起始顶点相通的全部顶点都访问完毕；与起始顶点相通的全部顶点都访问完毕；3、若此时图中尚有顶点未被访问，则再选其中一个顶点若此时图中尚有顶点未被访问，则再选其中一个顶点 作为起始顶点并访问之，转作为起始顶点并访问之，转 2；反之，遍历结束。反之，遍历结束。例：例：V1 V1V2V4V5V3V7V6V8顶点访问次序：顶点访问次序：V2 V4 V8 V5 V3 V6 V7 V1 V2 V5 V8 V4 V3 V6 V7 V1 V2 V4 V8 V5 V3 V7 V6 V1 V2 V5 V8

36、 V4 V3 V7 V6 V1 V3 V6 V7 V2 V4 V8 V5 连通图的深度优先遍历类似于树的先根遍历连通图的深度优先遍历类似于树的先根遍历 25abchdekfga c h dfke b g顶点访问次序顶点访问次序:例：例：a c h dfke g ba c h fked b g解决办法：解决办法：为每个顶点设立一个为每个顶点设立一个“访问标志访问标志”。如何判别如何判别V的邻接点是否被访问？的邻接点是否被访问？首先将图中每个顶点的访问标志设为首先将图中每个顶点的访问标志设为 FALSE,之后搜索图之后搜索图 中每个顶点，如果未被访问，则以该顶点为起始点，进行深度中每个顶点，如果未

37、被访问，则以该顶点为起始点，进行深度 优先遍历，否则继续检查下一顶点。优先遍历，否则继续检查下一顶点。26 1 3 7 0 V1 V2 V4 V8 V5 V3 0 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 3 1 5 6 7 7 6 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V6 5 V7 6 V1V2V4V5V3V7V6V84 1 1 1 1 1 1 1 1 277.3.2 广度优先遍历（广度优先遍历（BFS）（类似于树的按层遍历）（类似于树的按层遍历）方法：方法：方法：方法：从图的某一结点出发，首先依次访问该结点的所有邻从

38、图的某一结点出发，首先依次访问该结点的所有邻 接顶点接顶点 Vi1,Vi2,Vin 再按这些顶点被访问的先后次序依次访问再按这些顶点被访问的先后次序依次访问 与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶 点均被访问为止。点均被访问为止。例：例：V1V2V4V5V3V7V6V8广度优先遍历：广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8 V1 V3 V2 V7 V6 V5 V4 V8 V1 V2 V3 V5 V4 V7 V6 V8 28abchdekfga c d e fh k bg顶点访问次序顶点访问次序:例：例

39、：a c d e fh k gb29 1 3 4 0 V1 V2 V3 V4 V5 V6 实现：实现：V1V2V4V5V3V7V6V80 1 2 3 4 5 6 7 V1 V2 V3 V4 V5 V6 V7 V8 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V7 5 V8 F R R F R R F R R F 6 7 F F F F F R R R 1 1 1 1 1 1 1 1 307.4 7.4 连通网的最小生成树连通网的最小生成树1.概念概念生成树：生成树：是一个极小连通子图，它含有图中全部

40、顶点，但只有是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边。生成森林：生成森林：由若干棵由若干棵生成树生成树组成，含全部顶点，但构成这些树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。思考1：对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的得到的将是一个极小连通子图，即图的生成树生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：对非连通图进行遍历，得到的是什么？得到的将是

41、各连通分量的生成树，即图的得到的将是各连通分量的生成树，即图的生成森林生成森林！31例例1：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图32DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林DEABCFJLM33V1V6V5V4V3V26513566425V1V6V5V4V3V265134V1V6V5V4V3V26513219 17 2 构造最小生成树构造最小生成树 最小生

42、成树：最小生成树：给定一个无向网络，在该网的所有生成给定一个无向网络，在该网的所有生成 树中，使得各边权数之和最小的那棵生成树称为该网的最树中，使得各边权数之和最小的那棵生成树称为该网的最 小生成树，也叫小生成树，也叫最小代价生成树最小代价生成树。34 要在要在 n 个城市间建立通信联络网。个城市间建立通信联络网。顶点顶点：表示城市，表示城市，权：权：城市间通信线路的花费代价。希望此通信网花费代价最小。城市间通信线路的花费代价。希望此通信网花费代价最小。问题提出：问题提出：问题提出：问题提出：答案只能从生成树中找，因为要做到任何两个城市之答案只能从生成树中找，因为要做到任何两个城市之 间有线路

43、可达，间有线路可达，通信网必须是连通的通信网必须是连通的；但对长度最小的要求可以；但对长度最小的要求可以 知道知道网中显然不能有圈网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连，如果有圈，去掉一条边后，并不破坏连 通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。希望找到一棵生成树，它的每条边上的权值之和（即建立希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小该通信网所需花费的总代价）最小 最小代价生成树。最小代价生成树。问题分析：问题分析：问题分析：问题分析：结论：结论：结论：结论：35讨论

44、：如何求得最小生成树？讨论：如何求得最小生成树？有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：最小生成树的最小生成树的最小生成树的最小生成树的 MST MST 性质如下：性质如下：性质如下：性质如下：vPrim（普里姆普里姆）算法）算法 vKruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法PrimePrime算法特点算法特点:将顶点归并将顶点归并，与边数无关，适于，与边数无关，适于稠密网稠密网。KruskalKruskal算法特点：算法特点：将边归并将边归并，适于求，适于求稀疏网稀疏网的最小生成树。的最小生成树。这两个算法，都是利用这两个算法，都是利用MST 性质来构造最小

45、生成树的。性质来构造最小生成树的。若若U集是集是V的一个非空子集，若的一个非空子集，若(u0,v0)是一条是一条最小权值的边最小权值的边，其中其中u0 U，v0 V-U；则：则：(u0,v0)必在必在最小生成树上最小生成树上。36构造最小生成树方法：构造最小生成树方法：方法一：普里姆方法一：普里姆(Prim)算法。算法。V1V6V5V4V3V26513566425算法思想：算法思想：算法思想：算法思想：设设 N=(V,E)是连通网，是连通网，TE 是是 N 上最小生成树中上最小生成树中边的集合边的集合。初始令初始令 U=u0,(u0 V),TE=。在所有在所有 u U,v V-U 的边的边(u

46、,v)E 中，中，找一条代价最小的边找一条代价最小的边(u0,v0)。将将(u0,v0)并入集合并入集合 TE，同时同时 v0 并入并入 U。重复上述操作直至重复上述操作直至 U=V 为止，则为止，则 T=(V,TE)为为 N 的最的最 小生成树。小生成树。V1V3V6V4V2V537例：例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 23 36 64 42 25 51 1 注注：在最小生成树的生成过程中，所选的边都是：在最小生成树的生成过程中，所选的边都是 一端在一端在V-U中，另一端在中，另一端在U中。中。38方法二：克鲁斯卡尔方法二：克鲁

47、斯卡尔(Kruskal)算法。算法。V1V6V5V4V3V26513566425算法思想：算法思想：算法思想：算法思想：设连通网设连通网 N=(V,E)，令最小生成树令最小生成树初初始状态为始状态为只有只有 n 个个顶点顶点而而无边无边的非连通图的非连通图 T=(V,)，每个顶点自成一个连通分量。每个顶点自成一个连通分量。在在 E 中选取代价最小的边，若该边依附中选取代价最小的边，若该边依附 的顶点落在的顶点落在 T 中不同的连通分量上（即：中不同的连通分量上（即：不能形成环不能形成环），则将此边加入到），则将此边加入到 T 中；否中；否 则，舍去此边，选取下一条代价最小的边则，舍去此边，选取

48、下一条代价最小的边。依此类推，直至依此类推，直至 T 中所有顶点都在同一中所有顶点都在同一 连通分量上为止。连通分量上为止。5 5V1V6V5V4V3V215 52345N T 最小生成树最小生成树 可能不惟一可能不惟一 39KruskalKruskal（克克鲁斯卡尔鲁斯卡尔）算法）算法例例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 640例：应用克鲁斯卡尔算法构造最小生成树的过程例：应用克鲁斯卡尔算法构造最小生成树的过程41一顶点到其余各顶点一顶点到其余各顶点7.5.7.5.

49、单源最短路径单源最短路径两种常见的最短路径问题：两种常见的最短路径问题：一、一、单源最短路径单源最短路径用用Dijkstra（迪杰斯特拉）迪杰斯特拉）算法算法二、所有顶点间的最短路径二、所有顶点间的最短路径用用Floyd（弗洛伊德）弗洛伊德）算法算法典型用途：典型用途：交通问题。如：城市交通问题。如：城市A A到城市到城市B B有多条线路，但每条有多条线路，但每条线路的交通费（或所需时间）不同，那么，线路的交通费（或所需时间）不同，那么，如何选择一条线路，如何选择一条线路，使总费用（或总时间）最少？使总费用（或总时间）最少？问题抽象：问题抽象：在在带权有向图带权有向图中中A A点（源点）到达点

50、（源点）到达B B点（终点）的多点（终点）的多条路径中，寻找一条条路径中，寻找一条各边权值之和最小各边权值之和最小的路径，即最短路径。的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含（注：最短路径与最小生成树不同，路径上不一定包含n n个顶点）个顶点）任意两顶点之间任意两顶点之间42求单源最短路径求单源最短路径 (Dijkstra算法算法)目的：目的：设一设一有向图有向图G=G=（V,EV,E），），已知各边的权值，以某指已知各边的权值，以某指定点定点v v0 0为源点，求从为源点，求从v v0 0到图的其余各点的最短路径。到图的其余各点的最短路径。限定各限定各边上的权值大