A D B C 上图所示的无向图的邻接矩阵为: A B C D ABCD 011 0 0 很显然,这是一个对称阵。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 上图所示的无向图的邻接矩阵为： A B C D A 0 1 1 1 B 1 0 1 1 C 1 1 0 1 D 1 1 1 0 很显然，这是一个对称阵。 A D B C
二、特点:从上例中可以看出:无向图的邻 接矩阵是一个对称阵。有向图的邻接矩阵中 各行的和代表了该行表示的顶点的出度,各 列的和代表了该列表示的顶点的入度。 带权的邻接矩阵(耗费矩阵)对于网络 图来说,其邻接矩阵定义为对于有N个顶点 的图的邻接矩阵是一个NxN的方阵C,其中 C[J的值是这样确定的:当顶点对顶点有 边相连时C[J等于该边上的权值Wi;,当顶 点对顶点无边相连时,若尊等于,则C[,J 的值为0;若着不等于J,则C[叮的值为无穷 大 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 二、特点：从上例中可以看出：无向图的邻 接矩阵是一个对称阵。有向图的邻接矩阵中， 各行的和代表了该行表示的顶点的出度，各 列的和代表了该列表示的顶点的入度。 三、带权的邻接矩阵（耗费矩阵）对于网络 图来说，其邻接矩阵定义为:对于有N个顶点 的图的邻接矩阵是一个N×N的方阵C ，其中 C[I,J]的值是这样确定的：当顶点I对顶点J有 边相连时C[I,J]等于该边上的权值ｗｉｊ，当顶 点I对顶点J无边相连时，若I等于J，则C[I,J] 的值为０；若I不等于J，则C[I,J]的值为无穷 大
B 上图所示的网络图的耗费矩阵为 A D 0 ABCD B80 C9702 0 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 上图所示的网络图的耗费矩阵为： A B C D A 0 8 9 4 B ～ 0 7 ～ C ～ ～ 0 ～ D ～ ～ 2 0 A D B C 2 7 4 8 9
6.2.2邻接表 邻接表是表示顶项点之间的相邻关系的n个 单向链表。(n为图中顶点的个数)邻接表由 两部分组成: 其一为表头部分,用来存放各顶点的数据值, 又称为顶点表 其二为链表部分,用来存放相邻页点的地址 又称边表 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 6.２.２ 邻接表 邻接表是表示顶点之间的相邻关系的ｎ个 单向链表。（ｎ为图中顶点的个数）邻接表由 两部分组成： 其一为表头部分，用来存放各顶点的数据值， 又称为顶点表； 其二为链表部分，用来存放相邻顶点的地址。 又称边表
在邻接表中,采用顶点的编号表示顶点 表头部分包括两部分内容:用来存放顶点的名 称和相关数据(data)和指向表结点的指针 c firstarc) 链表部分包括三部分内容:邻接顶点编号 ( adjvex);指向下一个边的指针( nextarc); 数据域或权( weight) 表结点 头结点 adjvex nextarc weight data firstarc 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 在邻接表中，采用顶点的编号表示顶点 表头部分包括两部分内容：用来存放顶点的名 称和相关数据（data）和指向表结点的指针 (* firstarc) 链表部分包括三部分内容：邻接顶点编号 (adjvex)；指向下一个边的指针(*nextarc)； 数据域或权(weight)； 表结点 头结点 adjvex nextarc weight data firstarc