首页 > 笔记 > 图的储存

图的储存

最基本的图论。。。但是也不能松懈啊

有邻接矩阵,邻接链表。。。

1.1        无向图的数组表示
(1)   无权图的邻接矩阵
无向无权图G=(V,E)有n(n≧1)个顶点,其邻接矩阵是n阶对称方阵。其元素的定义如下:

clip_image002

clip_image004

(2)   带权图的邻接矩阵
无向带权图G=(V,E)的邻接矩阵元素的定义如下:

clip_image006

clip_image008

(3)   无向图邻接矩阵的特性
a)        邻接矩阵是对称方阵;
b)        对于顶点vi,其度数是第i行(或第i列)的非0元素的个数;
c)        无向图的边数是上(或下)三角形矩阵中非0元素个数。
1.2        有向图的数组表示

(1)   无权图的邻接矩阵

若有向无权图G=(V,E)有n(n≧1)个顶点,其邻接矩阵元素定义如下:

clip_image010

clip_image012

(2)   带权图的邻接矩阵

有向带权图G=(V,E)的邻接矩阵元素的定义如下:

clip_image014

clip_image016

(3)   有向图邻接矩阵的特性

  1. a) 对于顶点vi,第i行的非0元素的个数是其出度OD(vi);第i列的非0元素的个数是其入度ID(vi)。
  2. b) 邻接矩阵中非0元素的个数就是图的弧的数目。

2  邻接表
基本思想:对图的每个顶点建立一个单链表,存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。

2.1链表中的结点称为表结点,每个结点由三个域组成,如图所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号),链域(nextarc)指向下一个与顶点Vi邻接的表结点,数据域(info)存储和边或弧相关的信息,如权值等。对于无权图,如果没有与边相关的其他信息,可省略此域。
每个链表设一个表头结点(称为顶点结点),由两个域组成,如图所示。链域(firstarc)指向链表中的第一个结点,数据域(data)存储顶点名或其他信息。

images

在图的邻接表中,所有顶点结点用一个向量以顺序结构形式存储,可以随机访问任意顶点的链表,该向量称为表头向量,向量的下标指示顶点的序号。

2.2 示例
用邻接表存储图时,对无向图,其邻接表是唯一的,对有向图,其邻接表有两种形式,如图所示。

clip_image018

clip_image020

3数组模拟链表

 


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×