邻接矩阵的特点如下: (1)图的邻接矩阵表示是惟一的 (2)无向图的邻接矩阵一定是一个对称矩阵。因此,按照 压缩存储的思想,在具体存放邻接矩阵时只需存放上(或下) 三角形阵的元素即可。 (3)不带权的有向图的邻接矩阵一般来说是一个稀疏矩 阵,因此,当图的顶点较多时,可以采用三元组表的方法存储 邻接矩阵。 (4)对于无向图邻接矩阵的第行(或第列)零元素(或非 元素)的个数正好是第个顶点v的度
邻接矩阵的特点如下： (1)图的邻接矩阵表示是惟一的。 (2)无向图的邻接矩阵一定是一个对称矩阵。因此,按照 压缩存储的思想,在具体存放邻接矩阵时只需存放上(或下) 三角形阵的元素即可。 (3)不带权的有向图的邻接矩阵一般来说是一个稀疏矩 阵,因此,当图的顶点较多时,可以采用三元组表的方法存储 邻接矩阵。 (4)对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非 ∞元素)的个数正好是第i个顶点vi的度
(5)对于有向图,邻接矩阵的第i(或第列)非零元素(或 非∞元素)的个数正好是第个顶点v的出度(或入度。 (6)用邻接矩阵方法存储图很容易确定图中任意两个顶 点之间是否有边相连。但是,要确定图中有多少条边,则必须 按行、按列对每个元素进行检测所花费的时间代价很大 这是用邻接矩阵存储图的局限性
(5)对于有向图,邻接矩阵的第i行(或第i列)非零元素(或 非∞元素)的个数正好是第i个顶点vi的出度(或入度)。 (6)用邻接矩阵方法存储图,很容易确定图中任意两个顶 点之间是否有边相连。但是,要确定图中有多少条边,则必须 按行、按列对每个元素进行检测,所花费的时间代价很大。 这是用邻接矩阵存储图的局限性
邻接矩阵的数据类型定义如下: # define MAXv<最大顶点个数> typedef struct int no; 顶点编号 InfoType info 顶点其他信息* s Vertex Type; 顶页点类型* typedef struct /图的定义 { int edges MAXVIMAXV;/邻接矩阵* int vexnumarcum: 顶点数,弧数 VertexType vex MAXV;/存放顶点信息* MGraph
邻接矩阵的数据类型定义如下： #define MAXV <最大顶点个数> typedef struct { int no; /*顶点编号*/ InfoType info; /*顶点其他信息*/ } VertexType; /*顶点类型*/ typedef struct /*图的定义*/ { int edges[MAXV][MAXV]; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数,弧数*/ VertexType vexs[MAXV]; /*存放顶点信息*/ } MGraph;
9.2.2邻接表存储方法一 图的邻接表存储方法是一种顺序分配与链式分配相结 合的存储方法。在邻接表中对图中每个顶点建立一个单链 表第个单链表中的结点表示依附于顶点v的边对有向图是 以顶点v为尾的弧)。每个单链表上附设一个表头结点。表 结点和表头结点的结构如下: 表结点 表头结点 adve nextarc info data firstarc 其中,表结点由三个域组成, adjvex指示与顶点v邻接 的点在图中的位置, nextarc指示下一条边或弧的结点,info 存储与边或弧相关的信息,如权值等。表头结点由两个域 组成,data存储顶点v的名或其他信息, firstarc指向链表中 第一个结点
9.2.2 邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结 合的存储方法。在邻接表中,对图中每个顶点建立一个单链 表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是 以顶点vi为尾的弧)。每个单链表上附设一个表头结点。表 结点和表头结点的结构如下： 表结点 表头结点 advex nextarc info data firstarc 其中,表结点由三个域组成,adjvex指示与顶点vi邻接 的点在图中的位置,nextarc指示下一条边或弧的结点,info 存储与边或弧相关的信息,如权值等。表头结点由两个域 组成,data存储顶点vi的名或其他信息,firstarc指向链表中 第一个结点
①、吧 2 (a) 」→[o人
1 2 3 0 4 1 2 3 0 4 (a) (b) 0 1 2 3 4 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 ∧ 3 ∧ 4 ∧ 2 3 ∧ 4 ∧ v0 v1 v2 v3 v4 1 2 3 0 3 ∧ 3 ∧ 4 ∧ 3 ∧ v0 v1 v2 v3 ∧ v4 (a) (b)