数据结构 第7 章 图的定义和术语.pptVIP

数据结构 第七章 图 制作：计算机科学与技术系 徐振中 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 个顶点的有向图需存储空 间为n2，空间复杂度为O(n2)，用于稀疏图时空间浪费严重。 无向图中顶点 vi 的度 TD(vi) 是邻接矩阵中第 i 行 1 的个数。 有向图中 顶点 vi 的出度是邻接矩阵中第 i 行 1 的个数。 顶点 vi 的入度是邻接矩阵中第 i 列 1 的个数。 7.2.2 邻接表（类似于树的孩子链表表示法） 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 特点： 若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头结点 和 2e 个表结点。适宜存储稀疏图。 无向图中顶点 vi 的度为第 i 个单链表中的结点数。 v2 v1 v3 v4 G1 0 1 2 3 2 ^ 1 3 ^ ^ 0 v1 v3 v4 v2 ^ 0 1 2 3 ^ 3 0 ^ ^ 2 v1 v3 v4 v2 ^ 0 邻接表 逆邻接表 顶点 vi 的出度为第 i 个单链 表中的结点个数。 特点： 顶点 vi 的入度为整个单链表 中邻接点域值是 i -1 的结点 个数。 找出度易，找入度难。 找入度易，找出度难。 顶点 vi 的入度为第 i 个单链 表中的结点个数。 顶点 vi 的出度为整个单链表 中邻接点域值是 i -1 的结点 个数。 弧结点 a b c d 0 1 2 3 7.2.3 十字链表 0 1 2 0 0 2 ^ 3 0 ^ 3 1 ^ 3 2 ^ 2 3 ^ ^ b d a c tailvex headvex hlink tlink data firstin firstout 顶点结点 ^ ^ 指向依附于 ivex 的下一条边 7.2.3 邻接多重表（无向图的另一种链式存储结构） 邻接表优点：容易求得顶点和边的信息。 缺点：某些操作不方便（如：删除一条边需找表示此 边的两个结点）。 邻接多重表：每条边用一个结点表示。其结点结构如下： 指向依附于 jvex 的下一条边 mark ivex ilink jvex jlink info 边结点 data firstedge 顶点结点 存与顶点有关的信息 指向第一条依附于该顶点的边 标志域 标记此边是 否被有哪些信誉好的足球投注网站过 该边依附的两个顶点在表头数组中位置 0 3 0 1 2 3 4 v2 v1 v3 v4 v5 G2 v5 v4 v3 v2 v1 0 1