邻接表与邻接矩阵的用法?都是二维的..,大小一样..但是矩阵是布尔,表是数,明显空间大,查起来明显矩阵是O[1],表最坏

邻接表与邻接矩阵的用法?
都是二维的..,大小一样..但是矩阵是布尔,表是数,明显空间大,查起来明显矩阵是O[1],表最坏O(n)但是.我这句话哪里不对
六侠镇淄衣捕头 1年前 已收到1个回答 举报

我狂我可以000 幼苗

共回答了25个问题采纳率:92% 举报

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

1年前

1
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.024 s. - webmaster@yulucn.com