【7.3】图的存储结构

图的 相邻矩阵( adjacency matrix,或邻接矩 阵)表示顶点之间的邻接关系,即有没有边

设 G = $<V,E> $是一个有 n 个顶点的图,则图 的相邻矩阵是一个二维数组 A[n,n],定义如下:

对于 n 个顶点的图,相邻矩阵的空间代价都为 O(n2),与边数无关

有向图的相邻矩阵:

无向图的相邻矩阵

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学