|
|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 图 >
|
|
考试要求：熟悉
相关知识点：5个
|
|
|
|
|
设G=（V，E）是有n （n31）个顶点的图，在图的邻接矩阵表示法中，可用两个表格分别存储数据元素（顶点）的信息和数据元素之间的关联（边）信息。通常用一维数组（顺序表）存储数据元素的信息，用二维数组（邻接矩阵）存储数据元素之间的关系。
|
|
|
|
|
|
给定图G=（V，E），其中V（G）=｛v0，…，vi, …，vn-1｝，G邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵，G的邻接矩阵是具有如下性质的n阶方阵：
|
|
|
|
|
|
若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对称的，故可采用压缩存储的方法，仅存储下三角阵（不包括对角线上的元素）中的元素即可。显然，邻接矩阵表示法的空间复杂度S（n）=O（n2）。
|
|
|
|
|
|
|
|
| |
|
|
|
