《假设图G采用邻接表存储》由会员分享，可在线阅读，更多相关《假设图G采用邻接表存储（106页珍藏版）》请在金锄头文库上搜索。
1、第七章 图 第7章 图 一、教学内容： 1、图的基本概念 2、图的存储结构（邻接矩阵、邻接表）； 3、图的遍历（深度优先搜索、广度优先搜索）； 4、最小生成树（kruskul算法、prim算法）； 5、最短路径（dijkstra算法、floyd算法）; 6、AOV网络与拓扑排序； 7、AOE网络与关键路径。 第7章 图 二、教学要求： 1、理解图的基本概念，熟悉图的各种存储结构及其构 造算法； 2、熟练掌握图的两种搜索路径的遍历； 3、掌握构造最小生成树的方法，并理解算法； 4、掌握用Dijkstra方法求解单源最短路径问题，理解 Floyd（弗洛伊德）算法思想； 5、掌握求活动网络的拓扑排序
2、的方法，并理解算法； 6、掌握求解关键路径的方法。 第7章 图 教学重点： 图的定义、术语及其含义，各种图的邻接矩阵 表示法及其类型说明，图的按深度优先搜索遍 历方法和按广度优先搜索遍历方法，生成树和 最小生成树的概念， Prim 算法，拓扑序列和 拓扑排序的概念和算法思想，关键路径的算法 思想，最短路径的算法思想。 教学难点： 图的存储表示、关键路径，最短路径算法 。 引言 图（Graph）是一种较线性表和树更为复杂 的数据结构。 图形结构中，结点之间 的关系可以是任意的 ，任意两个数据元素之间都可能相关。 应用广泛: 如电路网络分析、交通运输、管理与线路的铺 设、印刷电路板与集成电路的布线
3、等众多直接与 图有关的问题，它们必须用图的有关方法进行处 理； 另外像工作的分配、工程进度的安排、课程表 的制订、关系数据库的设计等许多实际问题，如 果间接地用图来表示，处理起来比较方便。 问题的提出 假设有”平顶山”、”郑州”、”洛阳”、”许昌”、”漯河”五 城市的交通图如下,完成如下要求： 1：对任意输入的两个城市，输出它们之间的直接距 离，有则输出实际距离，无则输出道路不直接相通。 2：对任意一个城市，输出都能够直接通达哪些城市 ，距离多少？ 5 1 3 24 平顶山 郑州 洛阳 许昌 漯河 100 150 120 150 200 180 第7章 图 7.1 图的定义和术语 7.2 图的
4、存储结构 7.3 图的遍历操作 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.1 图的定义和术语 1、图的结构定义、图形结构特点 2、顶点、弧、边、弧头、弧尾 3、无向图和有向图 4、完全图和有向完全图 5、网、子图 6、顶点的度、入度和出度、 边、弧与各顶点度的关系 7.1 图的定义和术语 7、路径、路径长度、回路（环）、简单路 径 8、连通、连通图、连通分量 9、强连通图、强连通分量 10、生成树、有向树、生成森林 7.2 图的存储表示 n图的数组(邻接矩阵)存储表示（重点） n图的邻接表存储表示（重点） n有向图的十字链表存储表示 n无向图的邻接多重表存储表示
5、 回答问题 1、什么是图形结构？它和线性结构、树形 结构有何区别？ 2、以下图为例，理解图的相关术语，并回 答有关问题。 G1 AB CD AB CD E G2 回答问题 （1）G1中，A到D的路径是什么？路径长 度多少？ （2）G2中，A到E的路径是什么？路径长 度多少？ （3）G1是强连通图吗？若不是找出其强 连通分量？ （4）写出G2的生成树； （5）写出G1的生成森林； 回答问题 （6）写出G1的邻接矩阵、邻接表和十字链表； （7）写出G2的邻接矩阵、邻接表和邻接多重表 。 3、如下所示为一带权有向图，写出其邻接矩阵 、邻接表。 V1V2 V3V4 40 10 50 20 邻接矩阵的结
6、构定义： #define MAX_VERTEX_NUM 20 Typedef enumDG,DN,UDG,UDN Graphkind; typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct / 图的定义 VertexType / 顶点信息 vexsMAX_VERTEX_NUM; AdjM
7、atrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph; （1） 矩阵不一定是对称的; （2） 第i 行中1的个数为顶点i 的出度; （3） 第i列中1的个数为顶点 i的入度; （4） 矩阵中1的个数为图中弧的数目; （5） 很容易判断顶点i 和顶点j 是否有弧相连. 从有向图的邻接矩阵可以得出如下结论 从无向图的邻接矩阵可以得出如下结论 （1）矩阵是对称的，可压缩存储（上（下）三角; （2）第i行或第i 列中1的个数为顶点i 的度; （3）矩阵中1的个数的一半为图中边的数目; （4）很容易
8、判断顶点i 和顶点j之间是否有边相连 (看矩阵中i行j列值是否为1)。 容易实现图的操作，如：求某顶点的度、判断顶点 之间是否有边（弧）、找顶点的邻接点等等。仅耗 费 O(1) 时间。 n个顶点需要n*n个单元存储边(弧);空间效率为 O(n2)。对稀疏图而言尤其浪费空间。 邻接矩阵法优点： 邻接矩阵法缺点： 邻接矩阵存储表示特点 邻接表表示 图的邻接表存储方法是一种顺序分配与链式分配相结合 的存储方法，它包括两部分： 一部分是单链表，用来存 放边的信息；另一部分是数组，主要用来存放顶点本身 的数据信息。 表结点 头结点 adjvex nextarc info data firstarc 指示
9、与顶点Vi邻接的 点在图中的位置 指示下一条边 或弧的结点 信息可无 存储顶点Vi的 名或其他信息 指示链表中 第一个结点 从无向图的邻接表可以得到如下结论： （1）第i 个链表中结点数目为顶点i的度； （2）所有链表中结点数目的一半为图中边数； （3）占用的存储单元数目为n+2e 。 从有向图的邻接表可以得到如下结论： （1）第i 个链表中结点数目为顶点i的出度； （2）所有链表中结点数目为图中弧数； （3）占用的存储单元数目为n+e 。 邻接表表示 邻接表表示 邻接表的缺点： 邻接表的优点： 空间效率高；容易寻找顶点的邻接点； 判断任意两顶点间是否有边或弧，需搜索两结 点对应的单链表，没有
10、邻接矩阵方便。 图的邻接表数据类型描述 #define MAXN 50 /*MAXN表示图中最大顶点数*/ typedef struct arcnode /定义边结点的结构 int adjvex; /该弧所指向的顶点的位置 struct arcnode *nextarc ; / 指向下一条弧的指针 InfoType *info; arcnode; typedef struct vnode /定义邻接表的表头类型 VertexType data; /顶点信息 arcnode *firstarc; / 指向第一条依附该顶点的弧 vnode;AdjlistMAXN; 讨论：邻接表与邻接矩阵有什么异同
11、之处？ 1. 联系：邻接表中每个链表对应于邻接矩阵中的一行 ，链表中结点个数等于一行中非零元素的个数。 2. 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列 号与顶点编号一致），但邻接表不唯一（链接次序 与顶点编号无关）。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复 杂度为O(n+e)。 3. 用途：邻接矩阵多用于稠密图的存储（e接近n(n- 1)/2)；而邻接表多用于稀疏图的存储（eadjvex; else return -1; 非连通图的深度优先搜索 若图是非连通的或非强连通图，则从图中某 一个顶点出发。不能用深度优先搜索访问到图中 所有顶点，而只能访问到一个连通子图（既连通
12、 分量）或只能访问到一个强连通子图（既强连通 分量）。这时，可以在每个连通分量或每个强连 通分量中都选一个顶点，进行深度优先搜索遍历 ，最后将每个连通分量或每个强连通分量的遍历 结果合起来，则得到整个非连通图的遍历结果。 遍历算法实现与连通图的只有一点不同，即 对所有顶点进行循环，反复调用连通图的深度优 先搜索遍历算法即可。 2图的广度优先搜索 从图中的某个顶点V0出发，并在访问此顶 点之后依次访问V0的所有未被访问过的邻接点 ，之后按这些顶点被访问的先后次序依次访问 它们的邻接点，直至图中所有和V0有路径相通 的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中 一个未曾被访问的顶点作
13、起始点，重复上述过 程，直至图中所有顶点都被访问到为止。 广度优先搜索遍历类似于树的按层次遍历。 设图G的初态是所有顶点均未访问，在G 中任选 一顶点i作为初始点，则广度优先搜索的基本思 想是： (1)首先访问顶点i，并将其访问标志置为 已被访问，即visitedi=1； (2)接着依次访问与顶点i有边相连的所有 顶点W1，W2，Wt； (3)然后再按顺序访问与W1，W2，Wt有 边相连又未曾访问过的顶点； 依此类推，直到图中所有顶点都被访问完 为止 。 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vadjvex;/*m
14、为u的邻接顶点*/ if (visitedm=0)/*若顶点未标记访问,则递归访问之*/ PathAll(G,m,v,l,path,d); p=p-nextarc/*找u的下一个邻接顶点*/ visitedu=0; /*恢复环境*/ 7.4 图的连通性问题 一、 无向图的连通分量和生成树 若图是连通的或强连通的，则从图中某一个 顶点出发可以访问到图中所有顶点； 若图是非连通的或非强连通图，则需从图中 多个顶点出发搜索访问而每一次从一个新的起始 点出发进行搜索，搜索过程中得到的顶点访问序 列恰为每个连通分量中的顶点集。 DE AB C F J L M GH I K D E GH I K AB C
15、 F J L M 对于连通图， 深度优先搜索遍历算法及广 度优先搜索遍历算法中遍历图过程中历经边的 集合和顶点集合一起构成连通图的极小连通子 图。它是连通图的一棵生成树。 生成树：是一个极小连通子图，它含有图中 全部顶点，但只有n-1条边。 由深度优先搜索遍历得到的生成树，称为 深度优先生成树，由广度优先搜索遍历得到的 生成树，称为广度优先生成树。 1、连通图的生成树 例1 ：画出下图的生成树 DFS 生 成 树 v0 v1 v2 v4 v4v3 邻 接 表 0 1 2 3 4 13 341 420 v4 v3 v2 v1 v0 231 420 v0 v2 v1 v4 v3 BFS 生 成 树
16、 v0 v1v3 v2v4 无向连通图 2生成森林 若一个图是非连通图或非强连通图，但有若干 个连通分量或若干个强连通分量，则通过深度优 先搜索遍历或广度优先搜索遍历，不可以得到生 成树，但可以得到生成森林，且若非连通图有 n 个顶点，m 个连通分量或强连通分量，则可以遍 历得到m棵生成树，合起来为生成森林，森林中 包含n-m条树边。 生成森林可以利用非连通图的深度优先搜索 遍历或非连通图的广度优先搜索遍历算法得到。 3 最小生成树 在一般情况下，图中的每条边若给定了权，这 时，我们所关心的不是生成树，而是生成树中边 上权值之和。若生成树中每条边上权值之和达到 最小，称为最小生成树。 构造最小生成树的准则 v必须只使用该网络中的边来构造最小生成树 ； v必须使用且仅使用n-1条边来联结网络中的n 个顶点； v不能使用产生回路的边。 欲在
