图的表示方法

描述

邻接矩阵

用一个二维矩阵来存储两个节点之间的状态

缺点: 面对稀疏图时，有很多空间没有储存有效信息

• 确定邻接至或邻接于一个给定节点的集合需要用时 \(\Theta{(n)}\), 增加或删除一条 边仅需要 \(\Theta{(1)}\)

邻接链表

只考虑那些有连边的点对

对一个有 n 个点的图, 可以用 n 个链表, 第 i 个链表中存着从 i 直接连接的点

链式前向星表示的图

链式前向星（也称为邻接表的一种变种）是一种用于存储图的数据结构，它结合了数组和链表的优点，既节省空间又方便使用。在链式前向星中，每个节点的边不是直接存储在一个链表中，而是通过一个数组来存储所有边的信息，同时使用两个辅助数组来记录每条边的起点以及下一条边的位置。