能否快速判断两个点之间的连通性 #749
lld1995
started this conversation in
Feature Request
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
理论上来说,创建第一个A、B点时,生成个随机组ID,并记录组ID对应的节点数,如果B点可以与A点连通,那么就用节点数大的组ID去同化节点数小的整个组ID上的全部节点。只要形成连通就进行同化小图,这样虽然在插入时会造成额外开销,但可以O(1)判断多个点之间是否存在连通性。能否考虑做成配置项供用户开启该功能
并且在搜索两点的最短路径时,限定在组ID内搜索,可以极大加快搜索速度,特别点很多的时候
Beta Was this translation helpful? Give feedback.
All reactions