数据结构第七章关于图的存储、遍历、拓扑排序等

1、 欧拉欧拉17071707年出生在瑞士，年出生在瑞士，1919岁开始发表论文，直岁开始发表论文，直 到到7676岁。几乎每一个数学领域都可以看到欧拉的岁。几乎每一个数学领域都可以看到欧拉的 名字，从初等几何的欧拉线，多面体的欧拉定理，名字，从初等几何的欧拉线，多面体的欧拉定理， 立体解析几何的欧拉变换公式，四次方程的欧拉立体解析几何的欧拉变换公式，四次方程的欧拉 解法到数论中的欧拉函数，微分方程的欧拉方程，解法到数论中的欧拉函数，微分方程的欧拉方程， 级数论的欧拉常数，变分学的欧拉方程，复变函级数论的欧拉常数，变分学的欧拉方程，复变函 数的欧拉公式等等。据统计他的一生，共写下了数的欧拉公式等等

2、。据统计他的一生，共写下了 886886本书籍和论文，其中分析、代数、数论占本书籍和论文，其中分析、代数、数论占40%40%， 几何占几何占18%18%，物理和力学占，物理和力学占28%28%，天文学占，天文学占11%11%， 弹道学、航海学、建筑学等占弹道学、航海学、建筑学等占3%3%。 17331733年，年仅年，年仅 2626岁的欧拉担任了彼得堡科学院数学教授。岁的欧拉担任了彼得堡科学院数学教授。17411741 年到柏林担任科学院物理数学所所长，直到年到柏林担任科学院物理数学所所长，直到17661766 年，重回彼得堡，没有多久，完全失明。欧拉在年，重回彼得堡，没有多久，完全失明。欧拉

3、在 数学上的建术很多，对著名的哥尼斯堡七桥问题数学上的建术很多，对著名的哥尼斯堡七桥问题 的解答开创了图论的研究。的解答开创了图论的研究。 图论图论欧拉欧拉 能否从某个地方出发，穿过所有的桥仅一次能否从某个地方出发，穿过所有的桥仅一次 后再回到出发点？后再回到出发点？ 哥尼斯堡七桥问题哥尼斯堡七桥问题 C A D B 七桥问题的图模型七桥问题的图模型 哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉回路的判定规则：欧拉回路的判定规则： 1.如果通奇数桥的地方多于如果通奇数桥的地方多于 两个，则不存在欧拉回路；两个，则不存在欧拉回路； 2.如果只有两个地方通奇数如果只有两个地方通奇数 桥，可以从这两个地方

4、之一桥，可以从这两个地方之一 出发，找到欧拉回路；出发，找到欧拉回路； 3.如果没有一个地方是通奇如果没有一个地方是通奇 数桥的，则无论从哪里出发，数桥的，则无论从哪里出发， 都能找到欧拉回路。都能找到欧拉回路。 1 图的定义和术语图的定义和术语 3 图的遍历图的遍历 2 图的存储结构图的存储结构 4 图的连通性问题图的连通性问题 5 有向无环图及其应用有向无环图及其应用 6 最短路径最短路径 图的定义图的定义 1 图的定义和术语图的定义和术语 图是由图是由顶点顶点的的有穷非空有穷非空集合和顶点之间集合和顶点之间边边的集合组成的集合组成 ，通常表示为：，通常表示为： G=(V，E) 其中：其中

5、：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是图是图 G中顶点之间边的集合。中顶点之间边的集合。 在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表； 在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树； 在图中，顶点个数不能为零，但可以没有边。在图中，顶点个数不能为零，但可以没有边。 如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都 是是无向边，则称该图为无向边，则称该图为无向图无向图。 若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则 称这条边为称这条边为无向边无向边，表示为，表示为(vi

6、, ,vj)。 若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这 条边为条边为有向边有向边，表示为，表示为。 如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都 是是有向边，则称该图为有向边，则称该图为有向图有向图。 V1V2 V3 V4V5 V1V2 V3V4 1 图的定义和术语图的定义和术语 简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同 一条边不重复出现一条边不重复出现。 V3 V4V5 V1V2 V3 V4V5 V1V2 非简单图非简单图 非简单图非简单图 简单图简单图 V1V2 V3 V4V5 v 数据结构中讨论

7、的都是简单图。数据结构中讨论的都是简单图。 1 图的定义和术语图的定义和术语 邻接、依附邻接、依附 无向图无向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在边，若存在边 (vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为邻接点，同时称边互为邻接点，同时称边 (vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。 V1V2 V3 V4V5 V1的邻接点：的邻接点： V2 、 、V4 V2的邻接点：的邻接点： V1 、 、V3 、V5 1 图的定义和术语图的定义和术语 邻接、依附邻接、依附 有向图有向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，

8、若存在弧，若存在弧 ，则称顶点，则称顶点vi邻接到顶点邻接到顶点vj，顶点，顶点vj邻接自顶邻接自顶 点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj 。 V1V2 V3V4 V1的邻接点：的邻接点： V2 、 、V3 V3的邻接点：的邻接点： V4 1 图的定义和术语图的定义和术语 在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之间仅具有线性关系； 在树结构中，结点之间具有层次关系；在树结构中，结点之间具有层次关系； 在图结构中，任意两个顶点之间都可能有关系。在图结构中，任意两个顶点之间都可能有关系。 FECBAD 线性结构线性结构 A B C D E F

9、 树结构树结构 V1V2 V3 V4V5 图结构图结构 不同结构中逻辑关系的对比不同结构中逻辑关系的对比 在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为前驱前驱和和后继后继； 在树结构中，结点之间的关系为在树结构中，结点之间的关系为双亲双亲和和孩子孩子； 在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为邻接邻接。 FECBAD 线性结构线性结构 A B C D E F 树结构树结构 V1V2 V3 V4V5 图结构图结构 不同结构中逻辑关系的对比不同结构中逻辑关系的对比 无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间 都存在边，都

10、存在边，则称该图为无向完全图。则称该图为无向完全图。 有向完全图有向完全图：在有向图中，如果任意两个顶点之间：在有向图中，如果任意两个顶点之间 都存在方向相反的两条弧，都存在方向相反的两条弧，则称该图为有向完全图则称该图为有向完全图 。 V1V2 V3 V1V2 V3V4 1 图的定义和术语图的定义和术语 含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？ 含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？ 含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。 含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。

11、条边。 V1V2 V3 V1V2 V3V4 1 图的定义和术语图的定义和术语 稀疏图：稀疏图：称边数很少的图为稀疏图；称边数很少的图为稀疏图； 稠密图：稠密图：称边数很多的图为稠密图。称边数很多的图为稠密图。 顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶 点的边数，通常记为点的边数，通常记为TD (v)。 顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是指以该顶 点为弧头的弧的数目，点为弧头的弧的数目，记为记为ID (v)； 顶点顶点的的出度：出度：在有向图中，顶点在有向图中，顶点v的的出度出度是指以该顶是指以该顶

12、 点为弧尾的弧的数目，记为点为弧尾的弧的数目，记为OD (v)。 1 图的定义和术语图的定义和术语 V1V2 V3 V4V5 在具有在具有n个顶点、个顶点、e条边的无向图条边的无向图G中，各顶点中，各顶点 的度之和与边数之和的关系？的度之和与边数之和的关系？ = = = = n i i evTD 1 2)( 1 图的定义和术语图的定义和术语 V1V2 V3V4 在具有在具有n个顶点、个顶点、e条边的有向图条边的有向图G中，各顶点中，各顶点 的入度之和与各顶点的出度之和的关系？与边的入度之和与各顶点的出度之和的关系？与边 数之和的关系？数之和的关系？ evODvID i i i i = = =

13、= = =11 )()( nn 1 图的定义和术语图的定义和术语 权：权：是指对边赋予的有意义的数值量。是指对边赋予的有意义的数值量。 网：网：边上带权的图，也称网图。边上带权的图，也称网图。 V1V2 V3V4 2 7 8 5 1 图的定义和术语图的定义和术语 路径：路径：在无向图在无向图G=(V, E)中，从顶点中，从顶点vp到顶点到顶点vq之间的之间的 路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq)，其中，其中， (vij-1,vij)E（1jm）。若）。若G是有向图，则路径也是有是有向图，则路径也是有 方向的，顶点序列满足方向的，顶点序列满足E

14、。 V1V2 V3 V4V5 v一般情况下，图中的路径不惟一。一般情况下，图中的路径不惟一。 V1 到到V4的路径：的路径： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4 1 图的定义和术语图的定义和术语 路径长度：路径长度： 非带权图非带权图路径路径上边的上边的个数个数 带权图带权图路径上路径上各边的各边的权之和权之和 V1V2 V3 V4V5 V1 V4：长度为：长度为1 V1 V2 V3 V4 ：长度为：长度为3 V1 V2 V5V3 V4 ：长度为：长度为4 1 图的定义和术语图的定义和术语 路径长度：路径长度： 非带权图非带权图路径路径上边的上边的个数个数 带权图带

15、权图路径上路径上各边的各边的权之和权之和 V1 V4：长度为：长度为8 V1 V2 V3 V4 ：长度为：长度为7 V1 V2 V5V3 V4 ：长度为：长度为15 V1V2 V3 V4V5 2 5 6 3 2 8 1 图的定义和术语图的定义和术语 回路（环）回路（环）：第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。 简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。 简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点除了第一个顶点和最后一个顶点 外，其余顶点不重复出现的回路。外，其余顶点不重复出现的回路。 V1V2 V3

16、 V4V5 V1V2 V3V4 1 图的定义和术语图的定义和术语 子图：子图：若图若图G=（V，E），），G=（V，E），如果），如果V V 且且E E ，则称图，则称图G是是G的子图。的子图。 V1V2 V3 V4V5 V1V2 V3 V4V5 V1 V3 V4 1 图的定义和术语图的定义和术语 连通图：连通图：在无向图中，如果从一个顶点在无向图中，如果从一个顶点vi到另一个顶到另一个顶 点点vj(ij)有路径，则称顶点有路径，则称顶点vi和和vj是连通的。如果图中是连通的。如果图中 任意两个顶点都是连通的，则称该图是连通任意两个顶点都是连通的，则称该图是连通图。图。 连通分量：连通分量：非

17、连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量? ? 1.含有极大含有极大顶点顶点数；数； 2. 依附于这些顶点的所有依附于这些顶点的所有边边。 1 图的定义和术语图的定义和术语 连通分量连通分量1 V1V2 V3 V4V5 V6 V7 V1V2 V4V5 V3V6 V7 连通分量连通分量2 v连通分量是对无向图的一种划分。连通分量是对无向图的一种划分。 1 图的定义和术语图的定义和术语 强连通图：强连通图：在有向图中，对图中任意一对顶点在有向图中，对图中任意一对顶点vi和和vj (ij)，若从顶点，若从顶点

18、vi到顶点到顶点vj和从顶点和从顶点vj到顶点到顶点vi均有路径均有路径 ，则称该有向图是强连通图。，则称该有向图是强连通图。 强连通分量：强连通分量：非强连通图非强连通图的极大强连通子图。的极大强连通子图。 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量? ? 1 图的定义和术语图的定义和术语 V1V2 V3V4 强连通分量强连通分量1 强连通分量强连通分量2 V1 V3V4 V2 1 图的定义和术语图的定义和术语 生成树：生成树：n个顶点的连通图个顶点的连通图G的生成树是包含的生成树是包含G中中全全 部顶点部顶点的一个极小连通的一个极小连通子图。子图。 生成森林：生成森林：在

19、非连通图中，由每个连通分量都可以得在非连通图中，由每个连通分量都可以得 到一棵生成树，这些连通分到一棵生成树，这些连通分量的生成树就组成了一个量的生成树就组成了一个 非连通图的非连通图的生成森林生成森林。 多多构成回路构成回路 少少不连通不连通 含有含有n-1条边条边 1 图的定义和术语图的定义和术语 V1V2 V3 V4V5 V6 V7 V1V2V3 V4V5 V6 V7 V1V2 V3 V4V5 V1V2 V3 V4V5 生成树生成树 生成森林生成森林 1 图的定义和术语图的定义和术语 基本操作基本操作: CreatGraph( / 若G中存在顶点u，则返回该顶点在 / 图中“位置位置”

20、；否则返回其它信息。 GetVex(G, v); / 返回 v 的值。 PutVex( / 对 v 赋值value。 基本操作基本操作: 对邻接点的操作对邻接点的操作 FirstAdjVex(G, v); / 返回 v 的“第一个邻接点第一个邻接点” 。若该顶点 /在 G 中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); / 返回 v 的（相对于 w 的） “下一个邻接下一个邻接 / 点点”。若 w 是 v 的最后一个邻接点，则 / 返回“空”。 基本操作基本操作: 插入或删除顶点插入或删除顶点 InsertVex( /在图G中增添新顶点v。 DeleteVex( / 删

21、除G中顶点v及其相关的弧。 基本操作基本操作: 插入和删除弧插入和删除弧 InsertArc( / 在G中增添弧，若G是无向的， /则还增添对称弧。 DeleteArc( /在G中删除弧，若G是无向的， /则还删除对称弧。 基本操作基本操作: 遍遍 历历 DFSTraverse(G, v, Visit(); /从顶点v起深度优先深度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit(); /从顶点v起广度优先广度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。 基本操作基本操作: 2 图的存储表示图的存储表示 一、一、图

22、的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示 Aij= 0 (i,j)VR 1 (i,j)VR 一、一、图的数组(邻接矩阵)存储表示 B A C D FE 定义定义:矩阵的元素为矩阵的元素为 有向图的邻接矩阵有向图的邻接矩阵 为非对称矩阵为非对称矩阵 A BE CF 一、一、图的数组(邻接矩阵)存储表示 typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; /

23、 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM; 一、一、图的数组(邻接矩阵)存储表示 一、一、图的数组(邻接矩阵)存储表示 typedef struct / 图的定义图的定义 VertexType / 顶点信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph; Status CreateUDN(MGraph for (i=0; iG.vexnum; i+ ) sca

24、nf( / 构造顶点向量构造顶点向量 for (i=0; iG.vexnum; +i ) / 初始化邻接矩阵初始化邻接矩阵 for (j=0; jG.vexnum; +j ) G.arcsij.adj = INFINITY; /adj,info G.= NULL; for (k=0; kG.arcnum; +k ) / 构造邻接矩阵构造邻接矩阵 scanf( i = LocateVex(G, v1); j = LocateVex(G, v2); / 确定确定v1和和v2在在G中位置中位置 G.arcsij.adj = w; / 弧弧的权值的权值 if (IncInfo)

25、scanf(G.); / 输入弧含有相关信息输入弧含有相关信息 G.arcsji.adj = G.arcsij.adj; / 置置的对称弧的对称弧 return OK; / CreateUDN 无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？ 无向图的邻接矩阵无向图的邻接矩阵 V1 V3 V4 V2 V1 V2 V3 V4 vertex= 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 主对角线为主对角线为 0 且一定是对称矩阵。且一定是对称矩阵。 一、一、图的数组(邻接矩阵)存储表示 如何求顶点如

26、何求顶点i的度？的度？ 无向图的邻接矩阵无向图的邻接矩阵 V1 V3 V4 V2 V1 V2 V3 V4 vertex= 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。 一、一、图的数组(邻接矩阵)存储表示 如何判断顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？ 无向图的邻接矩阵无向图的邻接矩阵 V1 V3 V4 V2 V1 V2 V3 V4 vertex= 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0

27、0 arc= V1 V2 V3 V4 V1 V2 V3 V4 测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。 一、一、图的数组(邻接矩阵)存储表示 如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？ 无向图的邻接矩阵无向图的邻接矩阵 V1 V3 V4 V2 V1 V2 V3 V4 vertex= 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若arcij为为1，则，则 顶点顶点 j 为顶点为顶点 i 的邻接点。的邻接点。

28、 一、一、图的数组(邻接矩阵)存储表示 有向图的邻接矩阵有向图的邻接矩阵 V1V2 V3V4 V1 V2 V3 V4 vertex= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 有向图的邻接矩阵一定不对称吗？有向图的邻接矩阵一定不对称吗？ 不一定，例如有向完全图。不一定，例如有向完全图。 一、一、图的数组(邻接矩阵)存储表示 V1V2 V3V4 V1 V2 V3 V4 vertex= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 如何求顶点如

29、何求顶点 i 的出度？的出度？ 邻接矩阵的第邻接矩阵的第 i 行元素之和。行元素之和。 一、一、图的数组(邻接矩阵)存储表示 有向图的邻接矩阵有向图的邻接矩阵 V1V2 V3V4 V1 V2 V3 V4 vertex= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 如何求顶点如何求顶点 i 的入度？的入度？ 邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。 一、一、图的数组(邻接矩阵)存储表示 有向图的邻接矩阵有向图的邻接矩阵 V1V2 V3V4 V1 V2 V3 V4 vertex= 0 1 1 0 0 0 0

30、 0 0 0 0 1 1 0 0 0 arc= V1 V2 V3 V4 V1 V2 V3 V4 如何判断从顶点如何判断从顶点 i 到顶点到顶点 j 是否存在边？是否存在边？ 测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。 一、一、图的数组(邻接矩阵)存储表示 网图的邻接矩阵网图的邻接矩阵 网图的邻接矩阵可定义为：网图的邻接矩阵可定义为： arcij wij 若若(vi, vj)E（或（或E） 0 若若i=j 其他其他 V1V2 V3V4 2 7 8 5 0 2 5 0 0 8 7 0 arc= 一、一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 邻

31、接表存储的基本思想：对于图的每个顶点邻接表存储的基本思想：对于图的每个顶点vi，将所，将所 有邻接于有邻接于vi的顶点链成一个单链表，称为顶点的顶点链成一个单链表，称为顶点vi的的边边 表表（对于有向图则称为出弧表），所有边表的头指（对于有向图则称为出弧表），所有边表的头指 针和存储顶点信息的一维针和存储顶点信息的一维数组构成了数组构成了顶点表顶点表。 图的邻接矩阵存储结构的空间复杂度？图的邻接矩阵存储结构的空间复杂度？ 如果为稀疏图则会出现什么现象？如果为稀疏图则会出现什么现象？ 假设图假设图G有有n个顶点个顶点e条边，则存储该图需要条边，则存储该图需要O(n2) 。 邻接表有两种结点结构：

32、顶点表结点和边表结点邻接表有两种结点结构：顶点表结点和边表结点。 datafirstearc adjvex nextarc 顶点表顶点表 边边 表表 data：数据域，存放顶点信息。：数据域，存放顶点信息。 firstearc：指针域，指向边表中第一个结点。：指针域，指向边表中第一个结点。 adjvex：邻接点域，与该顶点邻接的点在顶点表中：邻接点域，与该顶点邻接的点在顶点表中 的下标。的下标。 nextarc：指针域，指向边表中的下一个结点。：指针域，指向边表中的下一个结点。 二、图的邻接表存储表示 D B A C FE 二、图的邻接表存储表示 A 1 4 B 0 4 5 C 3 5 D 2

33、 5 E 0 1 F 1 2 3 0 1 2 3 4 5 二、图的邻接表存储表示 1 0 3 23 1 01 V1 V2 V3 V4 0 1 2 3 vertex firstedge V1 V3 V4 V2 无向图的邻接表无向图的邻接表 边表中的结点表示什么？边表中的结点表示什么？ 每个结点对应图中的一条边，每个结点对应图中的一条边， 邻接表的空间复杂度为邻接表的空间复杂度为O(n+2e)。 二、图的邻接表存储表示 1 0 3 23 1 01 V1 V2 V3 V4 0 1 2 3 vertex firstedge V1 V3 V4 V2 无向图的邻接表无向图的邻接表 如何求顶点如何求顶点 i

34、 的度？的度？ 顶点顶点i的边表中结点的个数。的边表中结点的个数。 二、图的邻接表存储表示 如何判断顶点如何判断顶点 i 和顶点和顶点 j 之间是否存在边之间是否存在边? 测试顶点测试顶点 i 的边表中是否存的边表中是否存 在终点为在终点为 j 的结点。的结点。 1 0 3 23 1 01 V1 V2 V3 V4 0 1 2 3 vertex firstedge V1 V3 V4 V2 无向图的邻接表无向图的邻接表 二、图的邻接表存储表示 V1V2 V3V4 12 3 0 V1 V2 V3 V4 0 1 2 3 vertex firstedge 如何求顶点如何求顶点 i 的出度？的出度？ 顶点

35、顶点 i 的出弧表中结点的个数。的出弧表中结点的个数。 有向图的邻接表有向图的邻接表 二、图的邻接表存储表示 有向图的邻接表有向图的邻接表 V1V2 V3V4 12 3 0 V1 V2 V3 V4 0 1 2 3 vertex firstedge 如何求顶点如何求顶点 i 的入度？的入度？ 各顶点的出弧表中以顶点各顶点的出弧表中以顶点 i 为为 终点的结点个数。终点的结点个数。 二、图的邻接表存储表示 网图的邻接表网图的邻接表 V1V2 V3V4 2 7 8 5 2 1 V1 V2 V3 V4 0 1 2 3 vertex firstedge 5 2 8 3 7 0 typedef struc

36、t 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 顶点顶点的结点结构的结点结构 图图的结构的结构定义（邻接表）定义（邻

37、接表） typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph; 三、有向图的十字链表存储表示三、有向图的十字链表存储表示 A B C A B C 0 1 2 0 2 0 1 2 1 2 0 V1 V3 V4 V2 0 1 V1 V2 V3 V4 0 1 2 3 0 3 2 1 3 1 四、无向图的邻接多重表存储表示 作业作业 有一个带权图，其邻接矩阵的数组表有一个带权图，其邻接矩阵的数组表 示如下，请画出该图的带权邻接表。示如下，请画出该图的带权邻接表。 3 图的遍历图的遍历 图的遍历操作

38、图的遍历操作 图的遍历图的遍历是在从图中是在从图中某某一顶点出发，对图中所一顶点出发，对图中所有顶点有顶点 访问一次且仅访问一次且仅访问访问一次。一次。 抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种 处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。 图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题 在图中，如何选取遍历的起始顶点？在图中，如何选取遍历的起始顶点？ n在在线性表线性表中，数据元素在表中的编号就是元素在序列中，数据元素在表中的编号就是元素在序列 中的位置，因而其编号是唯一的；中的位置，因而其编号是唯一的； n在在树树中，将结点按层序编号，

39、由于树具有层次性，因中，将结点按层序编号，由于树具有层次性，因 而其层序编号也是唯一的；而其层序编号也是唯一的； n在在图图中，任何两个顶点之间都可能存在边，顶点是没中，任何两个顶点之间都可能存在边，顶点是没 有确定的先后次序的，所以，顶点的编号不唯一。有确定的先后次序的，所以，顶点的编号不唯一。 为了定义操作的方便，将图中的顶点按任意顺序排列起为了定义操作的方便，将图中的顶点按任意顺序排列起 来，比如，按顶点的存储顺序。来，比如，按顶点的存储顺序。 解决方案：从编号小的顶点开始解决方案：从编号小的顶点开始 。 3 图的遍历图的遍历 3 图的遍历图的遍历 从某个起点始可能到达不了所有其它顶点从

40、某个起点始可能到达不了所有其它顶点，怎么办？怎么办？ 图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题 解决方案：多次调用从某顶点出发遍历图的算法。解决方案：多次调用从某顶点出发遍历图的算法。 因图中可能存在回路，某些顶点可能会被重复访问，因图中可能存在回路，某些顶点可能会被重复访问， 那么如何避免遍历不会因回路而陷入死循环。那么如何避免遍历不会因回路而陷入死循环。 在图中，一个顶点可以和其它多个顶点相连，当这样在图中，一个顶点可以和其它多个顶点相连，当这样 的顶点的顶点访问过后，如何选取下一个要访问的顶点？访问过后，如何选取下一个要访问的顶点？ 图的遍历操作要解决的关键问题图的遍历操

41、作要解决的关键问题 解决方案：附设访问标志数组解决方案：附设访问标志数组visitedn 。 解决方案：解决方案：深度深度优先遍历和优先遍历和广度广度优先遍历。优先遍历。 3 图的遍历图的遍历 一、深度优先遍历一、深度优先遍历 基本思想基本思想 ： 访问顶点访问顶点v； 从从v的未被访问的邻接点中选取一个顶点的未被访问的邻接点中选取一个顶点w， 从从w出发进行深度优先遍历；出发进行深度优先遍历； 重复上述两步，直至图中所有和重复上述两步，直至图中所有和v有路径相通有路径相通 的顶点都被访问到。的顶点都被访问到。 深一层递归深一层递归 递归返回递归返回 深度优先遍历序列深度优先遍历序列?入栈序列

42、入栈序列?出栈序列出栈序列? V1 V3 V2 V4V5V6 V7 V8 V1 遍历序列：遍历序列：V1V2 V2 V4 V4 V5 V5 一、深度优先遍历一、深度优先遍历 一、深度优先遍历一、深度优先遍历 深一层递归深一层递归 递归返回递归返回 深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列? V1 V3 V2 V4V5V6 V7 V8 V1 V1V2 V2 V4 V4 V5V8 V8 遍历序列：遍历序列： 一、深度优先遍历一、深度优先遍历 深一层递归深一层递归 递归返回递归返回 深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列? V1 V3 V2

43、V4V5V6 V7 V8 V1 遍历序列：遍历序列：V1V2 V2 V4 V4 V5V8 一、深度优先遍历一、深度优先遍历 深一层递归深一层递归 递归返回递归返回 深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列? V1 V3 V2 V4V5V6 V7 V8 V1 遍历序列：遍历序列：V1 V7 V2V4V5V8V3 V3 V6 V6 V7 bool visitedMAX_VERTEX_NUM; / 访问标志数组访问标志数组 Status (* VisitFunc)(int v); / 函数变量函数变量 void DFSTraverse(Graph G, Status (*

44、Visit)(int v) VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = false; for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用对尚未访问的顶点调用DFS void DFS(Graph G, int v) visitedv = true; VisitFunc(v); / 访问第访问第v个顶点个顶点 for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) if (!visitedw) / 对对v

45、的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS DFS(G, w); 二、广度优先遍历二、广度优先遍历 基本思想基本思想： 访问顶点访问顶点v； 依次依次访问访问v的各个未被访问的邻接点的各个未被访问的邻接点v1, v2, , vk； 分别从分别从v1，v2，vk出发依次访问它们未被访问出发依次访问它们未被访问 的邻接点，并使的邻接点，并使“先先被访问顶点的邻接点被访问顶点的邻接点”先先于于“ 后被访问顶点的邻接点后被访问顶点的邻接点”被访问。直至图中所有与被访问。直至图中所有与 顶点顶点v有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。 二、广度优先遍历二、广度优先

46、遍历 广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1 V3 V2 V4V5V6 V7 V8 遍历序列：遍历序列：V1 V1 二、广度优先遍历二、广度优先遍历 广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1 V3 V2 V4V5V6 V7 V8 遍历序列：遍历序列：V1 V2 V2V3 V3 二、广度优先遍历二、广度优先遍历 广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1 V3 V2 V4V5V6 V7 V8 遍历序列：遍历序列：V1V2V3 V3 V4 V4 V5 V5 二、广度优先遍历二、广度优先遍历

47、广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1 V3 V2 V4V5V6 V7 V8 遍历序列：遍历序列：V1V2V3V4 V4 V5 V5 V6 V6 V7 V7 二、广度优先遍历二、广度优先遍历 广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1 V3 V2 V4V5V6 V7 V8 遍历序列：遍历序列：V1V2V3V4V5 V5 V6 V6 V7 V7V8 V8 void BFSTraverse(Graph G, Status (*Visit)(int v ) for (v=0; vG.vexnum; +v) visitedv =

48、FALSE; InitQueue(Q); for (v=0; v=0; w=NextAdjVex(G, u, w) if (!visitedw) / u的尚未访问的邻接顶点的尚未访问的邻接顶点w入队列入队列Q visitedw = TRUE; Visit(w); EnQueue(Q, w); /if /while /if / BFSTraverse 已知图已知图G如下，画出它的邻接表，并根据邻接表写出从如下，画出它的邻接表，并根据邻接表写出从 V1出发的深度优先遍历序列和广度优先遍历序列。出发的深度优先遍历序列和广度优先遍历序列。 作业作业 V1 V2V4 V5 V3V6 4 图的连通性问题图

49、的连通性问题 假设要在 n 个城市之间建立通讯 联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前如何在最节省经费的前 提下建立提下建立这个通讯网通讯网？ 问题：问题： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成 回路），使“权值之和权值之和”为最小。 算法二：（普里姆算法）算法二：（普里姆算法） 该问题等价于：该问题等价于： 算法一：（克鲁斯卡尔算法）算法一：（克鲁斯卡尔算法） 4 图的连通性问题图的连通性问题 MST(Minimum Spanning Tree)性质性质 假设假设G=(V, E)是一个无向连通网，是一个无向连通网，U是

50、顶点集是顶点集V的一的一 个非空子集。若个非空子集。若(u, v)是一条具有最小权值的边，其是一条具有最小权值的边，其 中中uU，vVU，则必存在一棵包含边，则必存在一棵包含边(u, v)的最的最 小生成树。小生成树。 顶顶 点点 集集 U VU u v v u 顶顶 点点 集集 T1T2 4 图的连通性问题图的连通性问题 基本思想基本思想：设无向连通网为：设无向连通网为G(V, E)，令，令G的最小生的最小生 成树为成树为T(U, TE)，其，其初态为初态为UV，TE ，然后，然后， 按照按照边的权值由小到大的顺序边的权值由小到大的顺序，考察，考察G的边集的边集E中的各中的各 条边。若被考察

51、的边的两个顶点属于条边。若被考察的边的两个顶点属于T的两个不同的的两个不同的连连 通分量通分量，则将此边作为最小生成树的边加入到，则将此边作为最小生成树的边加入到T中，同中，同 时把两个连通分量连接为一个连通分量；若被考察边时把两个连通分量连接为一个连通分量；若被考察边 的两个顶点属于同一个连通分量，则舍去此边，以免的两个顶点属于同一个连通分量，则舍去此边，以免 造成回路，如此下去，当造成回路，如此下去，当T中的连通分量个数为中的连通分量个数为1时，时， 此连通分量便为此连通分量便为G的一棵最小生成树。的一棵最小生成树。 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 克鲁斯卡尔（克鲁

52、斯卡尔（Kruskal）算法）算法 : 25 1234 1926 46 38 21 25 A B E D C F A B E D C F 连通分量连通分量A, B, C, D, E, F 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 25 1234 1926 46 38 21 25 A B E D C F A B E D C F 连通分量连通分量A, B, C, D, E, F 12 连通分量连通分量A, B, E, C, D, F 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 25 1234 1926 46 38 21 25 A B E D C F A B E D C F

53、 连通分量连通分量A, B, E, C, D, F 12 连通分量连通分量A, F, B, E, C, D 19 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 25 1234 1926 46 38 21 25 A B E D C F A B E D C F 连通分量连通分量A, F, B, E, C, D 12 连通分量连通分量A, F, B, E, C, D 19 21 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 25 1234 1926 46 38 21 25 A B E D C F A B E D C F 12 连通分量连通分量A, F, C, D, B, E 19

54、 21 25 连通分量连通分量A, F, B, E, C, D 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 25 1234 1926 46 38 21 25 A B E D C F A B E D C F 连通分量连通分量A, F, C, D, B, E 12 连通分量连通分量A, F, C, D, B, E 19 21 25 26 克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 : 1. 初始化：初始化：U=V； TE= ； 2. 循环直到循环直到T中的连通分量个数为中的连通分量个数为1 2.1 在在E中寻找最短边中寻找最短边( (u，v) ); 2.2 如果顶点如果顶点u、

55、v位于位于T的两个不同连通分量，则的两个不同连通分量，则 2.2.1 将边将边( (u，v) )并入并入TE； 2.2.2 将这两个连通分量合为一个；将这两个连通分量合为一个； 2.3 在在E中标记边中标记边( (u，v) )，使得，使得( (u，v) )不参加后续不参加后续 最短边的选取；最短边的选取； 普里姆算法普里姆算法: 基本思想基本思想：设：设G=(V, E)是具有是具有n个顶点的连通网，个顶点的连通网， T=(U, TE)是是G的最小生成树，的最小生成树， T的的初始状态初始状态为为 U=u0（u0V），），TE= ，重复执行下述操作：，重复执行下述操作： 在所有在所有uU，vV-

56、U的边中找一条代价最小的边的边中找一条代价最小的边 (u, v)并入集合并入集合TE，同时，同时v并入并入U，直至，直至U=V。 关键关键:是如何找到连接是如何找到连接U和和V-U的最短边的最短边。 U=A V-U=B, C, D, E, F cost=(A, B)34, (A, C)46, (A, D),(A, E),(A, F)19 25 1234 1926 46 38 17 25 A B E D C F 普里姆（普里姆（ Prim ）算法）算法: 25 1234 1926 46 38 17 25 A B E D C F U=A, F V-U=B, C, D, E cost=(A, B)3

57、4,(F, C)25, (F, D)25,(F, E)26 普里姆（普里姆（ Prim ）算法）算法: 25 1234 1926 46 38 17 25 A B E D C F U=A, F, C V-U=B, D, E cost=(A, B)34, (C, D)17, (F, E)26 普里姆（普里姆（ Prim ）算法）算法: 25 1234 1926 46 38 17 25 A B E D C F U=A, F, C, D V-U=B, E cost=(A, B)34, (F, E)26 普里姆（普里姆（ Prim ）算法）算法: 25 1234 1926 46 38 17 25 A B

58、 E D C F U=A, F, C, D, E V-U=B cost=(E, B)12 普里姆（普里姆（ Prim ）算法）算法: 25 1234 1926 46 38 17 25 A B E D C F U=A, F, C, D, E, B V-U= 普里姆（普里姆（ Prim ）算法）算法: 数组数组lowcostn：用来保存集合：用来保存集合V- -U中各顶点与集合中各顶点与集合U 中顶点最短边的权值，中顶点最短边的权值，lowcostv=0表示顶点表示顶点v已加入已加入 最小生成树中；最小生成树中； 数组数组adjvexn：用来保存依附于该边（用来保存依附于该边（集合集合V- -U中

59、各中各 顶点与集合顶点与集合U中顶点的最短边中顶点的最短边）在集合）在集合U中的顶点。中的顶点。 数据结构设计数据结构设计 表示表示顶点顶点vi和顶点和顶点vk之间的权值为之间的权值为w， 其中：其中：vi V- -U 且且vk U lowcosti=w adjvexi=k 如何用数组如何用数组lowcost和和adjvex表示候选最短边集表示候选最短边集？ 普里姆（普里姆（ Prim ）算法）算法: i 数组数组 B( (i=1) ) C( (i=2) ) D( (i=3) ) E( (i=4) )F( (i=5) )UV- -U输出输出 adjvex lowcost A 34 A 46 A

60、 A A 19 AB, C, D, E, F( (A F) )19 adjvex lowcost A 34 F 25 F 25 F 26 A, FB, C, D, E( (F C) )25 adjvex lowcost A 34 C 17 F 26 A, F, CB, D, E( (C D) )17 adjvex lowcost A 34 F 26 A, F, C, DB, E( (F E) )26 adjvex lowcost E 12 A, F, C, D, E B( (E B) )12 adjvex lowcost A,F,C,D,E,B 普里姆（普里姆（ Prim ）算法）算法: 1.