当用 Java 等语言表示内存中的图时,要么使用邻接矩阵(对于密集图),要么使用邻接列表(对于稀疏图)。
所以说我们代表后者,就像
Map<Integer, LinkedList<Integer>> graph;
整数键代表顶点,LinkedList包含它指向的所有其他顶点。
为什么使用 LinkedList 来表示边? int[] 或 ArrayList 不能同样正常工作,或者是否有理由希望以保持顺序的方式表示边缘,例如
2 -> 4 -> 1 -> 5
最佳答案
int[]
或 ArrayList
也可以工作。
不过,我不会立即推荐 int[]
,因为如果您从一开始就不知道所有尺寸,则需要调整大小,本质上是模拟ArrayList
功能,但如果内存有问题,它可能有意义。
LinkedList
可能稍微好一些,因为您需要使数组/ArrayList
足够大以处理最大数量的可能边,或者将其大小调整为你去吧,因为 LinkedList
不会出现这个问题,但话又说回来,对于大多数应用程序来说,创建图表可能不是最消耗资源的任务。
底线 - 对于大多数应用程序来说,它的影响很可能可以忽略不计 - 只需选择您觉得最舒服的一个即可(当然,除非您需要经常按索引访问,或者需要执行以下其中一项操作)两个的表现比另一个好得多)。
关于java - 当用邻接矩阵表示稀疏图时,为什么使用链表作为包含边的结构?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22387979/