在邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。
很明显,这种邻接表的存储方式,占用的空间比邻接矩阵要小得多。
要想查出从顶点0能否到达顶点1,该怎么做呢?很简单,我们从顶点0开始,顺着链表的头节点向后遍历,看看后继的节点中是否存在顶点1。
要想查出顶点0能够到达的所有相邻节点,也很简单,从顶点0向后的所有链表节点,就是顶点0能到达的相邻节点。
那么,要想查出有哪些节点能一步到达顶点1,又该怎么做呢?这样就麻烦一些了,我们要遍历每一个顶点所在的链表,看看链表节点中是否包含节点1,最后发现顶点0和顶点3可以到达顶点1。
像这种逆向查找的麻烦,该如何解决呢?我们可以是用逆邻接表来解决。