|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 树和图 > 图 >
|
被考次数：1次
被考频率：低频率
总体答错率：62%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：掌握
相关知识点：2个
|
|
|
|
|
|
|
|
|
邻接矩阵表示法利用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G=（V，E）来说，其邻接矩阵是一个n阶方阵，且满足：
|
|
|
|
|
|
有向图和无向图的邻接矩阵如下图中的矩阵A和B所示。
|
|
|
|
|
|
|
|
由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，而有向图的邻接矩阵则不一定具有该性质。
|
|
|
|
借助于邻接矩阵，可判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。对于无向图，顶点νi的度是邻接矩阵中第i行（或列）的值不为0的元素数目（或元素的和）；对于有向图，第i行的元素之和为顶点νi的出度OD（νi），第j列的元素之和为顶点νj的入度ID（νj）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点νi的边（对于有向图是以νi为尾的弧）。邻接链表中的结点有表结点和表头结点两种类型，如下所示：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点及其邻接表。若图用邻接链表来表示，则对应的数据类型可定义如下：
|
|
|
|
|
|
显然，对于有n个顶点、e条边的无向图来说，其邻接链表需要n个头结点和2e个表结点，如下图所示。对于无向图的邻接链表，顶点νi的度恰为第i个邻接链表中表结点的数目。
|
|
|
|
|
|
|
|
下图（b）是下图（a）所示有向图的邻接表。从中可以看出，由于第i个邻接链表中表结点的数目只是顶点νi的出度，因此必须逐个扫描每个顶点的邻接表，才能求出一个顶点的入度。为此，可以建立一个有向图的逆邻接链表，如下图（c）所示。
|
|
|
|
|
|
|
