数组表示法(邻接矩阵) 用两个数组分别存储数据元素(顶点)的信息和数据元素 之间的关系(边或弧)的信息。 ●在图的邻接矩阵表示中,有一个记录各个顶点信息的顶点 表,还有一个表示各个顶点之间关系的邻接矩阵。 设图A=(V日是一个有n个顶点的图,则图的邻接矩阵 定义: 4.n1,若(v,V)或 <V12V1>∈B(G) 0,其它 ●无向图的邻接矩阵是对称的,有向图的邻接矩阵可能是不 对称的。 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 ⚫ 用两个数组分别存储数据元素（顶点）的信息和数据元素 之间的关系（边或弧）的信息。 一、数组表示法（邻接矩阵） = 0，其它 1,若(v , v )或 v , v E(G) [ , ] i j i j A i j ⚫ 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点 表，还有一个表示各个顶点之间关系的邻接矩阵。 ⚫ 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵 定义： ⚫ 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不 对称的
数组表示法(邻接矩阵)①②③ 例 2 0000 ③0001 3 GI ④L100O 例 ①0 010 3 ②10101 ③o1011 ④10100 G2 ⑤O 00 北京邮电大学自动化学院
北京邮电大学自动化学院 12 例 G1 2 4 1 3 例 1 5 3 2 4 G2 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 一、数组表示法（邻接矩阵）
、数组表示法(邻接矩阵) 借助郤接矩阵容易判定任意两个顶点之间是否有边(或弧)相 连,并容易求得各个顶点的度。 对于无向量,顶点V的度是邻接矩阵中第行(或第i列)的元 素之和,即 TD()=AI[] (n=MAX_VERTEX_ NUM) 对于有向图,第的元素之和为顶点v的出度OG(), 第列的元素之和为顶点V的入度D)8②④ 0110 2 ②0000 4 ③0001 000 北京邮电大学自动化学院 13
北京邮电大学自动化学院 13 ⚫ 借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相 连，并容易求得各个顶点的度。 − = = = 1 0 ( ) [ ][ ] ( _ _ ) n j TD Vi A i j n MAX VERTEX NUM ⚫ 对于无向量，顶点Vi的度是邻接矩阵中第i行（或第i列）的元 素之和，即 ⚫ 对于有向图，第i行的元素之和为顶点Vi的出度OG（ Vi ）， 第j列的元素之和为顶点Vj的入度ID(Vj )。 一、数组表示法（邻接矩阵） 例 G1 2 4 1 3 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0
数组表示法(邻接矩阵) 网的邻接矩阵可定义为: ∫vy,若,y)<v,v>∈EG) ∞,其它 Q52 中∞57∞31 5 ∞48 8 ○O 6 3816 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 ⚫网的邻接矩阵可定义为： = ，其它 ,若(v , v )或 v , v E(G) [ , ] wi j i j i j A i j 例 1 4 5 2 3 7 5 3 1 8 6 4 2 3 8 1 6 4 2 6 7 2 1 5 4 8 5 7 3 一、数组表示法（邻接矩阵）
图的邻接表存储表示 口邻接表是图的一种链式存储结构。在邻接表中,对 图中每个顶点建立一个单链表,第个单链表中的 结点表示依附于顶点v的边(对有向图中指以顶点 V为尾的弧)。 口每个结点有三个域组成:| adjvex nextarc info 口邻接结点域( adjvex):指示与顶点v邻接的点在图 中的位置。 口链域( nextarc):指示下一条边或弧的结点。 口数据域(info):存储和边相关的信息,如权值等 北京邮电大学自动化学院
北京邮电大学自动化学院 15 二、图的邻接表存储表示 ❑ 邻接表是图的一种链式存储结构。在邻接表中，对 图中每个顶点建立一个单链表，第i个单链表中的 结点表示依附于顶点Vi的边（对有向图中指以顶点 Vi为尾的弧）。 ❑ 每个结点有三个域组成： adjvex nextarc info ❑ 邻接结点域(adjvex)：指示与顶点Vi邻接的点在图 中的位置。 ❑ 链域(nextarc)：指示下一条边或弧的结点。 ❑ 数据域(info)：存储和边相关的信息，如权值等