【数据结构和算法笔记】：图的储存方式（邻接矩阵，邻接表）
·
邻接矩阵：
顶点i，j之间有边，则A【i】【j】=1或者边的权值，
否则等于0（不带权图）或者无穷（带权图）
例： 无向图的邻接矩阵：
例：有向图的邻接矩阵：
特点：
邻接表：
邻接表占用空间：
无向图：adj【i】=degree【i】
有向图: adj【i】=in degree【i】
占用空间 ：顶点数+度数之和
由握手定理：度数之和为边数2倍
在有向图中出度等于入度，所以出度之和为边数
所以需要的储存空间的规模O(V+E)
注意:邻接表的储存方式一般比邻接表要好
例：邻接表储存带权有向图
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献5条内容
所有评论(0)