数据结构图总结.ppt

7.1 图的定义和术语,定义：,图(Graph)是一种复杂的非线性数据结构，由顶 点集合及顶点间的关系（也称弧或边）集合组成。可 以表示为：G(V,VR)其中 V 是顶点的有穷非空集合；VR 是顶点之间关系 的有穷集合，也叫做弧或边集合。弧是顶点的有序对，边是顶点的无序对。,生成树：所有顶点均由边连接在一起，但不存在回路的图。,一个图可以有许多棵不同的生成树。,注,所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同；生成树是图的极小连通子图；一个有 n 个顶点的连通图的生成树有 n-1 条边；生成树中任意两个顶点间的路径是唯一的；在生成树中再加一条边必然形成回路。,含 n 个顶点 n-1 条边的图不一定是生成树。,7.2 图的存储结构,7.2.1 数组表示法（邻接矩阵表示法）,特点：,无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无向图 需存储空间为 n(n-1)/2。,有向图邻接矩阵不一定对称；有 n 个顶点的有向图需存储空 间为n，空间复杂度为O(n2)，用于稀疏图时空间浪费严重。,无向图中顶点 vi 的度 TD(vi)是邻接矩阵中第 i 行 1 的个数。,有向图中,顶点 vi 的出度是邻接矩阵中第 i 行 1 的个数。,顶点 vi 的入度是邻接矩阵中第 i 列 1 的个数。,7.2.2 邻接表（类似于树的孩子链表表示法）,3,1,4,2,0,4,3,1,2,0,2,1,特点：,若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头结点 和 2e 个表结点。适宜存储稀疏图。,无向图中顶点 vi 的度为第 i 个单链表中的结点数。,0,1,2,3,2,1,3,0,v1,v3,v4,v2,邻接表,逆邻接表,顶点 vi 的出度为第 i 个单链 表中的结点个数。,特点：,顶点 vi 的入度为整个单链表 中邻接点域值是 i-1 的结点 个数。,找出度易，找入度难。,找入度易，找出度难。,顶点 vi 的入度为第 i 个单链 表中的结点个数。,顶点 vi 的出度为整个单链表 中邻接点域值是 i-1 的结点 个数。,弧结点,7.2.3 十字链表,顶点结点,7.2.3 邻接多重表（无向图的另一种链式存储结构）,邻接表优点：容易求得顶点和边的信息。缺点：某些操作不方便（如：删除一条边需找表示此 边的两个结点）。,邻接多重表：每条边用一个结点表示。其结点结构如下：,标志域 标记此边是 否被搜索过,7.2.3 邻接多重表（无向图的另一种链式存储结构）,7.3 图的遍历,深度优先遍历（Depth_First SearchDFS）广度优先遍历（Breadth_Frist SearchBFS）,7.4.3 最小生成树,构造最小生成树方法：,方法一：普里姆(Prim)算法。,方法二：克鲁斯卡尔(Kruskal)算法。,最小生成树 可能不惟一,拓扑排序的方法：,在有向图中选一个没有前驱的顶点且输出之。,从图中删除该顶点和所有以它为尾的弧。,重复上述两步，直至全部顶点均已输出；或者当图中 不存在无前驱的顶点为止,一个AOV网的拓扑序列不是唯一的,7.5.2 关键路径,把工程计划表示为有向图，用顶点表示事件，弧表示活 动，弧的权表示活动持续时间。每个事件表示在它之前的活 动已经完成，在它之后的活动可以开始。称这种有向图为边 表示活动的网络，简称为AOE（Activity On Edge）网。,对于AOE网，我们关心两个问题：(1)完成整项工程至少需要 多少时间？(2)哪些活动是影响工程进 度的关键？,求关键路径步骤：求 ve(i)、vl(j)求 e(i)、l(i)计算 l(i)-e(i),7.6 最短路径,7.6.1 单源点最短路径（从某个源点到其余各顶点的最短路径）,迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。,7.6.2 每一对顶点之间的最短路径,方法一：每次以一个顶点为源点，重复执行 Dijkstra 算法 n 次。,方法二：弗洛伊德(Floyd)算法 算法思想：逐个顶点试探，从 vi 到 vj 的所有可能存在 的路径中，选出一条长度最短的路径。,