数据结构

位置:IT落伍者 >> 数据结构 >> 浏览文章

数据结构之邻接矩阵表示法


发布日期:2020年02月23日
 
数据结构之邻接矩阵表示法

定义

邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵设G=(VE)是一个图其中V={vvvn}G的邻接矩阵是一个具有下列性质的n阶方阵

特点

无向图的邻接矩阵一定是对称的而有向图的邻接矩阵不一定对称因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n个单元来存储邻接矩阵对有n个顶点的无向图则只存入上(下)三角阵故只需n(n+)/个单元

无向图邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度

有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度第i列非零元素的个数为第i个顶点的入度第i个顶点的度为第i行与第i列非零元素个数之和

用邻接矩阵表示图很容易确定图中任意两个顶点是否有边相连

邻接矩阵的C语言描述

用一个顺序表来存储顶点信息

上一篇:09计算机专业研究生入学考试:数据结构备考[1]

下一篇:数据结构 4.12 作业排队问题