决定我们采用邻接矩阵还是采用邻接表来表示图,需要判断一个图是稀疏图还是稠密图。邻接矩阵和邻接表表示图所需的存贮空间和算法时间度相差非常大,所以判断一个图是稀疏的还是稠密的非常重要。
判断标准如下: 假设一个图G=(V,E)有n个节点,图G的每个节点的出度是一个固定的常数:k。由于E=kV=O(V) ,所以我们把符合E=O(V) 条件的图称为稀疏图。 同理 : 如果一个图G=(V,E)有n个节点,假设图G的每个节点的出度是关于n的一个小数,并且0<f<=1,我们把符合E=fV2(平方)=V2(平方)条件的图称为稠密图。 比如:一个图节点为16,节点的出度为4,那么f = 0.25。
据说:邻接表是表示图的标准方法,原因是稠密图在实际应用中并不多见。