0图的存储结构 第七章图 图的存储表示方法方法很多。对应于不同的应用问题, 往往选用不同的图的存储结构。具体选择哪一种表示法,主 要取决于具体的应用场合以及欲施加的操作 介绍一般情况下常用的图的有关存储结构。它们是 数组表示法——邻接矩阵一 邻接表表示法图的一种链式存储结构 十字链表表示法—有向图的另一种链式存储结构 邻接多重表表示法—无向图的另一种链式存储结构
第七章 图 第21页 图的存储表示方法方法很多。对应于不同的应用问题， 往往选用不同的图的存储结构。具体选择哪一种表示法，主 要取决于具体的应用场合以及欲施加的操作。 介绍一般情况下常用的图的有关存储结构。它们是 数组表示法——邻接矩阵 邻接表表示法——图的一种链式存储结构 十字链表表示法——有向图的另一种链式存储结构 邻接多重表表示法——无向图的另一种链式存储结构 ⚫ 图的存储结构
图的存情结构一邻接矩阵 第七章图 +数组表示法邻接矩阵 邻接矩阵( Adjacency Matrix)是表示图中顶点之间相邻关系 的矩阵 设G=(VE)是具有n个顶点的图,则G的邻接矩阵是具有如下性 质的示M小10.若(m或W不是E(G)中的边 1,若(v或<vi,v>是E(G)中的边 示例9设有向图G1和无向图 G2为 V V4 有向图G1 无向图G2 则它们的邻接矩阵A1和A2分别为 010 0110 01 0000A A1= 0 011 0001 0101 00 1000 0 100
第七章 图 第22页 数组表示法——邻接矩阵 邻接矩阵（Adjacency Matrix）是表示图中顶点之间相邻关系 的矩阵。 设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下性 质的n阶方阵 = 若 或 不是 中的边 若 或 是 中的边 0, ( , ) , ( ) 1, ( , ) , ( ) , v i v j v i v j E G v i v j v i v j E G A i j 示例9 设有向图G1和无向图 G2为 V1 V2 V3 V4 V1 V2 V4 V5 V3 则它们的邻接矩阵A1和A2分别为 有向图G1 无向图G2 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 A1= A2= ⚫ 图的存储结构 – 邻接矩阵
第七章图 示例10对于下述之无向图G7和有向图G8 V1( 无向图G7 有向图G8 记其相应邻接矩阵分别为A7和A8,则有一 000 00 00 A=01010 100 0000 00010 说明 1)无向图的邻接矩阵是对称的,有向图则不一定; (2)设图G共有n个顶点,则若G是有向图,则存储空间为n2位 而若G是无向图,则存储空间可为n(n+1/2位,即仅存储上(或下 三角元素; (3)无向图顶点Ⅴ的度是邻接矩阵中第行(或第列)的元素之和, 即 TD()=∑4门(or∑4j 而有向图顶点v的出度为邻接矩阵中第行元素之和,入度为第列 元素之和,即 OD)=∑4,,D()=∑4 第23页
第七章 图 第23页 说明 (1) 无向图的邻接矩阵是对称的，有向图则不一定； (2) 设图G共有n个顶点，则若G是有向图，则存储空间为n 2位， 而若G是无向图，则存储空间可为n(n+1)/2位，即仅存储上（或下） 三角元素； (3) 无向图顶点Vi的度是邻接矩阵中第i行（或第i列）的元素之和， 即 而有向图顶点Vi的出度为邻接矩阵中第i行元素之和，入度为第i列 元素之和，即 示例10 对于下述之无向图G7和有向图G8 V1 V4 V2 V3 V1 V2 V5 V4 记其相应邻接矩阵分别为A7和A8，则有 无向图G7 有向图G8 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 A7= A8= V3 ( ) [ , ]; ( [ , ]) 1 1 = = = n j n j i TD V A i j or A j i = = = = n j n j i i OD V A i j ID V A j i 1 1 ( ) [ , ], ( ) [ , ]
第七章图 (4)欲检测在图G中总共有多少条边,必须按行、列逐次检测邻接矩二 阵的各元素,故最坏情况下需时O(n2 若G是网,则邻接矩阵可定义为 vn,若(v,V)或<V,V>∈E(G) ∞或O 否贝 其中W表示边上的权值,∞表示一个计算机允许的、大于所有边上权值 的数。 示例11下面给出一个网及其邻接矩阵 358 6411 A O 10 无向网 示例12有向网及其邻接矩阵(图7.9) ∞4 8 8∞000-∝ A 6 3∞∞01∞ 5 图7.9 第24页
第七章 图 第24页 (4) 欲检测在图G中总共有多少条边，必须按行、列逐次检测邻接矩 阵的各元素，故最坏情况下需时O(n2 )。 若G是网，则邻接矩阵可定义为 = 或 否则 若 或 0 , ( , ) , ( ); [ , ] w V V V V E G A i j i j i j i j 其中wij表示边上的权值，∞表示一个计算机允许的、大于所有边上权值 的数。 示例11 下面给出一个网及其邻接矩阵 V1 V2 V5 V3 V4 3 8 6 5 4 2 11 10 ∞ 3 5 8 ∞ 3 ∞ 6 4 11 5 6 ∞ 2 ∞ 8 4 2 ∞ 10 ∞ 11 ∞ 10 ∞ A= 无向网 示例12 有向网及其邻接矩阵（图7.9） 3 5 4 8 7 9 6 1 5 5 V4 V3 V2 V1 V6 V5 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ A= 图 7.9
图的存储结构一邻接矩阵 第七章图 +数组表示法邻接矩阵 下面给出建立无向网的存储结构即邻接矩阵的算法 数据结构 define MAX VERTEX207最天顶点个数 typedef enumfDG,DN,AG,AN) GraphKind;//有向图,有向网,无向图,无向网 typedef struct Arccell( VRType adji //顶点关系类型,无权图用0,1表示相邻否,带权图为权 neoType*info;//相关信息的指针 JArccell, AdjMatrix [MAX VERTEX+1] [MAX VERTEX+1 typedef structi VertexType vex[ MAX VERTEX+1];//顶点向量 AdjMatrix arcs /邻接矩阵 int vexnum arcum //顶点数,弧数 Graphickind kind; //图的类型 Mgraph 第25页
第七章 图 第25页 下面给出建立无向网的存储结构即邻接矩阵的算法。 数据结构 #define MAX_VERTEX 20 //最大顶点个数 typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网 typedef struct ArcCell{ VRType adj; //顶点关系类型，无权图用0，1表示相邻否，带权图为权 InfoType *info; //相关信息的指针 }ArcCell, AdjMatrix[MAX_VERTEX+1][MAX_VERTEX+1]; typedef struct{ VertexType vexs[MAX_VERTEX+1]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //顶点数，弧数 GraphicKind kind; //图的类型 } Mgraph; ⚫ 图的存储结构 – 邻接矩阵 数组表示法——邻接矩阵