邻接表与邻接矩阵的用法？

Question

都是二维的..，大小一样..但是矩阵是布尔，表是数，明显空间大，查起来明显矩阵是O[1]，表最坏O（n）但是.....我这句话哪里不对

Answer 1

邻接表有多种实现方式，比如最简单的动态链表，对于一个无向图，为每个节点建一个动态链表，储存的只是这个节点每个相邻的点，而在邻接矩阵中，对于每个节点需要把它与其他所有点的关系都表示出来（相邻为1，不相邻为0），空间复杂度明显是邻接矩阵大，至于查询两者各有千秋，如果只是查询两个点之间是否相邻，邻接矩阵当然更快，但如果是做dfs的话，找当前节点相邻的点，如果用邻接矩阵的话每次都要从1扫到n，如果用邻接表的话每次只需把当前节点邻接表后的点都取出来即可。