有向图及无向图的比较研究.ppt

有向图及无向图的比较研究 知识结构 图的定义无向图与有向图无向图与有向图异同点 图 图 Graph 是一种较线性表和树更为复杂的非线性结构 是对结点的前趋和后继个数不加限制的数据结构 用来描述元素之间 多对多 的关系 一图的定义图G由两个集合构成 记作G V E 其中V是顶点的非空有限集合 E是边的有限集合 其中边是顶点的无序对或有序对集合 G1 V1 E1 V1 v0 v1 v2 v3 v4 E1 v0 v1 v0 v3 v1 v2 v1 v4 v2 v3 v2 v4 无序对 vi vj 用连接顶点vi vj的线段表示 称为无向边 例 G1图示 G2图示 有序对 用以为vi起点 以vj为终点的有向线段表示 称为有向边或弧 G2 V2 v0v1 v2 v3 E2 有向图和无向图 在图中 若用箭头标明了边是有方向性的 则称这样的图为有向图 否则称为无向图 在无向图中 一条边 x y 与 y x 表示的结果相同 用圆括号表示 在有向图中 一条边与表示的结果不相同 故用尖括号表示 表示从顶点x发向顶点y的边 x为始点 y为终点 有向图 无向图 完全图 图G中的每条边都是有方向的 图G中的每条边都是无方向的 图G任意两个顶点都有一条边相连接 若n个顶点的无向图有n n 1 2条边 称为无向完全图若n个顶点的有向图有n n 1 条边 称为有向完全图 图的应用举例 例1交通图 公路 铁路 顶点 地点边 连接地点的公路交通图中的有单行道双行道 分别用有向边 无向边表示 例2电路图顶点 元件边 连接元件之间的线路例3通讯线路图顶点 地点边 地点间的连线例4各种流程图如产品的生产流程图顶点 工序边 各道工序之间的顺序关系 异同点 证明 若是完全有向图 则n个顶点中的每个顶点都有一条弧指向其它n 1个顶点 因此总边数 n n 1 证明 从 可以直接推论出无向完全图的边数 因为无方向 两弧合并为一边 所以边数减半 总边数为n n 1 2 完全无向图有n n 1 2条边 完全有向图有n n 1 条边 图的邻接表表示 图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法 它包括两部分 边表和顶点表 边表是单链表 用来存放边的信息 顶点表是数组 主要用来存放顶点本身的数据信息和该顶点邻接点的位置 边结点 顶点结点 1无向图的邻接表顶点 通常按编号顺序将顶点数据存储在一维数组中 关联同一顶点的边 用线性链表存储 该结点表示边 ViVj 其中的1是Vj在一维数组中的位置 例 下标编号link 2有向图的邻接表和逆邻接表1 有向图的邻接表顶点 用一维数组存储 按编号顺序 以同一顶点为起点的弧 用线性链表存储 类似于无向图的邻接表 所不同的是 以同一顶点为起点的弧 用线性链表存储 例 2 有向图的逆邻接表顶点 用一维数组存储 按编号顺序 以同一顶点为终点的弧 用线性链表存储 类似于有向图的邻接表 所不同的是 以同一顶点为终点弧 用线性链表存储 例 2 从无向图的邻接表可以得到如下结论 1 在G邻接表中 同一条边对应两个结点 所有链表中结点数目的一半为图中边数 2 顶点v的度 等于v对应线性链表的长度 3 判定两顶点v u是否邻接 要看v对应线性链表中有无对应的结点4 在G中增减边 要在两个单链表插入 删除结点 5 设存储顶点的一维数组大小为m m 图的顶点数n 图的边数为e G占用存储空间为 m 2 e G占用存储空间与G的顶点数 边数均有关 3 从有向图的邻接表可以得到如下结论 1 第i个链表中结点数目为顶点i的出度 2 所有链表中结点数目为图中弧数 3 占用的存储单元数目为n e 从有向图的邻接表可知 不能求出顶点的入度 为此 我们必须另外建立有向图的逆邻接表 以便求出每一个顶点的入度 适用于边稀疏的图 邻接矩阵 A Edge v1v2v3v4v5 v1v2v3v4v5 0101010101010111010101110 分析1 无向图的邻接矩阵是对称的 分析2 顶点Vi的度 第i行 列 中1的个数 特别 完全图的邻接矩阵中 对角元素为0 其余全1 顶点表 无向图的邻接矩阵如何表示 0000000000000000000000000 0101010101010111010101110 有向图的邻接矩阵如何表示 分析1 有向图的邻接矩阵可能是不对称的 分析2 顶点vi的出度 第i行元素之和 OD vi A Edge i j 顶点vi的入度 第i列元素之和 ID vi A Edge j i 顶点的度 第i行元素之和 第i列元素之和 即 TD vi OD vi ID vi 邻接矩阵 A Edge v1v2v3v4 v1v2v3v4 0000000000000000 注 在有向图的邻接矩阵中 第i行含义 以结点vi为尾的弧 即vi出度边 第i列