1、数据结构讲义- 图的定义和存储信息工程学院信息工程学院魏洪涛魏洪涛Email:图的定义：图的定义： 图G是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。例如，对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：G1=(V1,E1), 其中 V1=a,b,c,d, E1=(a,b),(a,c),(a,d),(b,d),(c,d),而G2=(V2,E2)，其中V2=1,2,3, E2=,。 d A cA b a 2 1 3 (a) 无向图 G1 (b) 有向图 G2 图 7-1 无向图和有向图 图无法以数据元素在存储区中的物理位置
2、来表示元图无法以数据元素在存储区中的物理位置来表示元素之间关系，即素之间关系，即图没有顺序映象的存储结构图没有顺序映象的存储结构。 用多重链表表示图，即以一个数据域和多个指针域用多重链表表示图，即以一个数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针。顶点的信息，指针域存储指向其邻接点的指针。常用的有邻接矩阵、邻接表和十字链表等。不管哪常用的有邻接矩阵、邻接表和十字链表等。不管哪一种方式，它除了要存储图中各个顶点本身的信息一种方式，它除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的
3、所有关系（边外，同时还要存储顶点与顶点之间的所有关系（边的信息）。的信息）。多重链表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V31 图的邻接矩阵表示图的邻接矩阵表示在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）E(G)或i,jE(G),则矩阵中第i行 第j列元素值为1，否则为0 。图的邻接矩阵定义为： 1 若（i,j）E(G)或i,jE(G) Aij= 0 其它情形 例如, 对图7-8所示的无向图和有向图的邻接矩阵。 3 1 2 (a) 无向图 G3 (b)有向图 G4 图 7-8 无向图 G3 及有向图 G4 1
4、 2 4 3 0111101011011010 001100110 (a) G3 的邻接矩阵 (b) G4 的邻接矩阵 邻接矩阵表示 2 2 从从无向图无向图的邻接矩阵可以得出如下结论的邻接矩阵可以得出如下结论 （1）矩阵是对称的，可压缩存储（上（下）三角）;（2）第第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。3 从从有向图有向图的邻接矩阵可以得出如下结论的邻接矩阵可以得出如下结论（1） 矩阵不一定是对称的;（2） 第
5、i 行中1的个数为顶点i 的出度;（3） 第i列中1的个数为顶点 i的入度;（4） 矩阵中1的个数为图中弧的数目;（5） 很容易判断顶点i 和顶点j 是否有弧相连.4 4网网的邻接矩阵表示的邻接矩阵表示 类似地可以定义网的邻接矩阵为： wij 若（i,j）E(G)或i,jE(G)Aij= 其它情形网及网的邻接矩阵见下图。 7493728421986316 (a) 网 G5 (b) 网 G5 的邻接矩阵示意图 网及邻接矩阵示意图 5 3 1 2 4 3 6 1 2 4 8 9 7 邻接矩阵法邻接矩阵法优点：优点：u容易实现图的操作，如：容易实现图的操作，如：求某顶点的度求某顶点的度、判断顶判断顶
6、点之间是否有边（弧）点之间是否有边（弧）、找顶点的邻接点等等找顶点的邻接点等等。邻接矩阵法邻接矩阵法缺点：缺点：un n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间效率为空间效率为O(nO(n2 2) )。 u对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。1图的邻接表表示图的邻接表表示 图的图的邻接表邻接表存储方法是一种存储方法是一种顺序分配顺序分配与与链式分配链式分配相相结合的存储方法，它包括两部分：结合的存储方法，它包括两部分：一部分一部分是单链表，是单链表，用来存放边的信息；用来存放边的信息；另一部分另一部分是数组，主要用来存是数组，主要用来
7、存放顶点本身的数据信息。放顶点本身的数据信息。 vertex link next adjvex weight next 边结点边结点顶点结点顶点结点 1 2 3 4 2 4 1 3 4 2 4 1 2 3 (a)无向图 G3 的邻接表 1 2 3 2 3 3 1 1 2 3 3 1 1 3 (b) 有向图 G4 的邻接表 (c) 有向图 G4 的逆邻接表 邻接表示例 左图所示的无向图G3和有向图G4的邻接表见右图所示 : 3 1 2 (a) 无向图 G3 (b)有向图 G4 无向图 G3 及有向图 G4 1 2 4 3 2 2 从从无向图无向图的邻接表可以得到如下结论的邻接表可以得到如下结论
8、（1）第i 个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为占用的存储单元数目为n+2e 。3 从从有向图有向图的邻接表可以得到如下结论的邻接表可以得到如下结论（1）第i 个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；所有链表中结点数目为图中弧数；（3）占用的存储单元数目为占用的存储单元数目为n+e 。从有向图的邻接表可知，不能求出顶点的从有向图的邻接表可知，不能求出顶点的入度入度。为此，我们必须另外建立有向图的为此，我们必须另外建立有向图的逆邻接表逆邻接表，以，以便求出每一个顶点的入度
9、。便求出每一个顶点的入度。8064125当邻接表当邻接表的存储结的存储结构形成后，构形成后，图便唯一图便唯一确定！确定！如果是无向图，只要如果是无向图，只要搜索任意一个结点的搜索任意一个结点的边表。有向图要搜索边表。有向图要搜索两个结点的边表。两个结点的边表。l邻接表的优点邻接表的优点：空间效率高；容易寻找顶点的邻接点；l邻接表的缺点：邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。4 图的邻接表数据类型描述图的邻接表数据类型描述图的邻接表数据类型描述如下：图的邻接表数据类型描述如下：#define MAXN 50 /*MAXN表示图中最大顶点数表示图中最大
10、顶点数*/typedef struct e_node /定义边结点的结构定义边结点的结构 int adjvex; int weight; /边的信息边的信息 struct e_node *next ;E_NODE; /指向邻接点的指针指向邻接点的指针typedef struct v_node /定义邻接表的表头类型定义邻接表的表头类型 int vertex; /顶点信息顶点信息 E_NODE *link; /指向指向“边表边表”的指针的指针V_NODE;V_NODE headMAXN;1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中
11、结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(O(n n2 2),),而邻接表的空间复杂而邻接表的空间复杂度为度为O(O(n+en+e) )。3.3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用
12、于稀疏图的存储（；而邻接表多用于稀疏图的存储（enen2 2) )l有向图的十字链表表示法弧结点：typedef struct arcnode int tailvex, headvex; /弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧 struct arcnode *tlink; /指向弧尾相同的下一条弧AD;tailvex headvex hlink tlink顶点结点：typedef struct dnode int data; /存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点 str
13、uct arcnode *firstout; /指向以该顶点为弧尾的第一个弧结点DD;DD gM; /g0不用data firstin firstout例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1l无向图的邻接多重表表示法顶点结点：typedef struct dnode int data; /存与顶点有关的信息 struct node *firstedge; /指向第一条依附于该顶点的边DD;DD gaM; /ga0不用data firstedge边结点：typedef struct node int mark; /标志域 int ivex, jvex; /该边依附的两个顶点在表头数组中位置 struct node *ilink, *jlink; /分别指向依附于ivex和jvex的下一条边JD;mark ivex ilink jvex jlink例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2l已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表；（5） 十字链表.
