页数：38页文件大小：559.2 KB来源： 数据结构-C#语言描述ppt课件
本课件讲解图形结构这一多对多的非线性结构：先给出顶点集、边集及无向图有向图、度与邻接、路径与连通、权与网等术语，再讲邻接矩阵与邻接表两类存储方式，图解深度优先与广度优先遍历及生成树，最后展开普里姆、克鲁斯卡尔两种最小生成树算法与迪杰斯特拉、弗洛伊德最短路径算法。
本页为第六章图封面。本章讲解图的基本概念与术语、邻接矩阵与邻接表存储结构、图的遍历、生成树与最小生成树，以及最短路径算法。
线性表中的元素是“一对一”的关系，树中的元素是“一对多”的关系，本章所讲述的图形结构中的元素则是“多对多”的关系。
图（Graph）是一种复杂的非线性数据结构，在图形结构中，每个元素可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。
一个图（Graph）是由顶点（Vertex）集 V 和边（Edge，又称为弧）集 E 组成的。图中顶点用 Vi 来表示，在括号中使用逗号分隔的两个顶点来表示一条边，如 (V1，V2)。
示例：顶点集 V(G) = {V1，V2，V3，V4}，边集 E(G) = { (V1，V2)，(V1，V3)，(V1，V4)，(V2，V4) }。
设有两个图 G = (V，E) 和 G' = (V'，E')，若 V' 是 V 的子集，且 E' 是 E 的子集，则称 G' 是 G 的子图。
图中 (b)、(c) 都是由 (a) 中去掉部分顶点与边后得到的子图。
路径（Path）：在无向图中，若从顶点 Vi 出发有一组边可到达顶点 Vj，则称顶点 Vi 到顶点 Vj 的顶点序列为从顶点 Vi 到顶点 Vj 的路径。
图中给出了从起点沿若干条边到达终点的两种不同走法，说明两点之间的路径可能有多条。
强连通图（Strongly Connected Graph）：在有向图中，若任意一对不同的顶点 Vi 和 Vj 都存在从 Vi 到 Vj 及 Vj 到 Vi 的路径，则称为强连通图。
有向图中极大的强连通子图称为它的强连通分量。
权（Weight）：图的边有时会包含具有某种特定含义的数据信息，这些附带的数据信息称为权。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费代价、所需时间等。
带权的图也称作网络或网。图中给出了北京、上海、南宁、广州、武汉等城市之间带有距离数值的带权图。
邻接矩阵表示法用一个二维数组存放图中各顶点之间的邻接关系：矩阵第 i 行第 j 列为 1 表示顶点 i 与顶点 j 之间有边，为 0 表示无边。
无向图的邻接矩阵一定关于主对角线对称，且主对角线元素为 0。
有向图的邻接矩阵一般不再对称：第 i 行第 j 列为 1 表示存在由顶点 i 指向顶点 j 的弧。
因此同一行之和为该顶点的出度，同一列之和为该顶点的入度。
邻接表由表头结点与表结点两部分组成：
图中给出了无向图 ABCD 及其对应的邻接表，每个顶点的所有邻接点串成一条单链表。
图中 (a) 为有向图，(b) 为按出边建立的邻接表，(c) 为按入边建立的逆邻接表。
邻接表便于找出某个顶点的所有后继，逆邻接表便于找出其所有前驱，二者结构相同、建表方向相反。
带权图的邻接表在各个表结点中额外增加一个权值域，用于存放该边上的权。
图中给出了带权图 ABCD 及其邻接表，每条边除邻接点下标外还记录了对应的权值。
和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。
图的遍历方法有两种：一种是深度优先搜索遍历（Depth-First Search，简称 DFS）；另一种是广度优先搜索遍历（Breadth_First Search，简称 BFS）。
深度优先搜索遍历从图中某个顶点出发，访问该顶点后依次从它的未被访问的邻接点出发深度优先遍历，直到所有与起点有路径相通的顶点都被访问。
图中给出了 V1 到 V8 八个顶点按深度优先得到的访问序号。
广度优先搜索遍历从某个顶点出发，依次访问它的所有未被访问的邻接点，再按同样次序访问这些邻接点的邻接点，表现为一层一层向外扩展。
图中给出了 V1 到 V8 八个顶点按广度优先得到的访问序号，与深度优先的结果明显不同。
若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。
为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点，否则不能访问到所有顶点。为此同样需要再选初始点，继续进行遍历，直到图中的所有顶点都被访问过为止。
对于无向图，含有连通图全部顶点的一个极小连通子图，称为生成树（Spanning Tree）。
其本质就是从连通图任一顶点出发进行遍历操作所经过的边，再加上所有顶点构成的子图。
采用深度优先搜索遍历方式获得的生成树称为深度优先生成树（DFS 生成树）。
图中左侧为带权连通图，右侧为按深度优先遍历经过的边所构成的树形子图。
采用广度优先搜索遍历获得的生成树称为广度优先生成树（BFS 树）。
图中右侧为按广度优先遍历经过的边所构成的树形子图，与深度优先生成树的形态不同。
如果连通图是一个网络（带权的图），称该网络中所有生成树中权值总和最小的生成树为最小生成树（Minimum Spanning Tree），简称 MST。
构造有 n 个顶点的无向连通带权图的最小生成树必须满足以下 3 个条件：
典型的构造最小生成树的方法有两种，一种称为普里姆（Prim）算法，另一种称为克鲁斯卡尔（Kruskal）算法。
普里姆（Prim）算法是一种构造性算法。设图 G = (V，E) 是具有 n 个顶点的网，T = (U，E(T)) 为 G 的最小生成树，U 是 T 的顶点集合，E(T) 是 T 的边集合。
算法每次从连接 U 与 V-U 的边中选一条权值最小的边，把对应顶点并入 U，直到 U 包含全部顶点。
本页演示普里姆算法的第一步：从集合 U 中的初始顶点 0 出发，在连接 U 与 V-U 的候选边中选取权值最小的一条，将其端点并入集合 U，并在最小生成树中画出这条边。
本页演示普里姆算法的第二步：集合 U 已含两个顶点，重新考察所有一端在 U 中、另一端在 V-U 中的边，再取其中权值最小者，把新顶点并入 U。
本页演示普里姆算法的第三步：集合 U 继续扩大，最小生成树中已确定的边随之增加，候选边集合同步更新，始终保留跨集合的最小权边。
本页演示普里姆算法的第四步：继续选取跨集合的最小权边并入 U，最小生成树中已确定的边逐渐增多，剩余未确定顶点越来越少。
本页演示普里姆算法的最后一步：当集合 U 包含全部顶点、最小生成树中选入的边达到顶点数减一条时，算法结束，得到权值总和最小的生成树。
克鲁斯卡尔（Kruskal）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设 G = (V，E) 是一个具有 n 个顶点的带权连通无向图，T = (U，TE) 是 G 的最小生成树，则构造最小生成树的步骤为：
将图中所有边按权值递增顺序排序，依次选取权值较小的边，但要求后面选择的边不能与前面选择的边构成回路，否则就放弃该边，重复这个过程，直到 n 个顶点的图选出 n-1 条边即可。
本页演示克鲁斯卡尔算法的执行过程：按权值由小到大依次考察各条边，把不会与已选边构成回路的边加入生成树，遇到会形成回路的边则直接放弃，直到选够顶点数减一条边为止。
单源点最短路径是指给定一个出发点（源点）和一个有向网，求出源点到其他各顶点之间的最短路径。
从源点 0 到终点 4 共有 4 条路径，下表列出各条路径及其长度：
| 候选序号 | 路径 | 路径长度 |
|---|---|---|
| 1 | 0 → 4 | 90 |
| 2 | 0 → 3 → 4 | 90 |
| 3 | 0 → 1 → 2 → 4 | 70 |
| 4 | 0 → 3 → 2 → 4 | 60 |
源点 0 到终点 4 的最短路径为第 4 条路径，长度为 60。
原课件该页另有一张含源点、中间顶点、终点、路径长度四列的结果表，因文本提取时数字粘连，此处仅还原正文中明确给出的四条路径对比，其余数据请以原课件图示为准。
迪杰斯特拉（Dijkstra）算法用于求单源点最短路径：把顶点分成已确定最短路径的集合 S 与尚未确定的集合 U，每轮从 U 中取出距离最小的顶点并入 S，并用它松弛其余顶点的距离值 dist，直到所有顶点都进入 S。
图中给出了有向网的邻接矩阵以及各轮 dist 结果集的变化。
对于给定的有向网而言，可以利用 Dijkstra 算法，把每个顶点作为源点重复执行 n 次，即可求出有 n 个顶点的有向网中每对顶点间的最短路径，它的时间复杂度为 O(n 的 3 次方)。
弗洛伊德（Floyed）提出了另一种算法用于计算有向网中所有顶点间的最短路径，这种算法称为弗洛伊德算法，它的时间复杂度依然为 O(n 的 3 次方)，但形式上更为简单些。
本页演示弗洛伊德算法的迭代过程：以邻接矩阵为初始状态，依次把每个顶点作为允许中转的顶点，逐轮更新距离矩阵与路径矩阵，最终得到任意两顶点之间的最短路径长度。
图是一种网状的多对多的非线性数据结构，图中的每个顶点可以有多个前驱和后继。图的存储包括结构有邻接矩阵、邻接表等。但在实际应用中，图也有可能以多种形式存在。
本章还介绍了求最小生成树的普里姆算法、克鲁斯卡尔算法，求最短路径的迪杰斯特拉算法、弗洛伊德算法，这些算法的掌握对于将来学习图论算法有着重要的意义。
本页为实训指导，要求在如图所示的迷宫中求从起点到终点的最短路径。图中用行列坐标标出可通行的格子，例如 0,2、0,3、0,4、0,5、1,0、1,2 等，并标出了起点与终点所在位置。
可把每个可通行格子看作图的顶点、相邻格子之间的连通关系看作边，用广度优先遍历求最少步数的走法。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}