在邻接表中查找所有连接的节点 [英] Find all connected nodes in adjacency list

问题描述

我有一个 DAG 的邻接列表，我需要从所有节点中找到所有连接的节点，例如:对于下面的 DAG

1 ->3 ->42 ->43 ->24 ->55 ->空值

我需要这个:

1 ->{2, 3, 4, 5}2 ->{4, 5}3 ->{2, 4, 5}4 ->{5}5 ->空值

有什么有效的算法吗?

解决方案

正如您提到的 DAG，您可以使用以下算法将所有连接的组件获取到给定的顶点:-

<块引用>

1. 对图中的所有节点进行拓扑排序
2. 按已排序节点的降序开始.
3. 为每个节点维护一组所有连接的节点.
4. 按拓扑排序对顶点 u 的邻接表进行排序
5. 对于顶点 u 和每条边 (u,v) 和 !Set(u).contains(v) 做 Set(u) = Set(u) union Set(v) union v
6. 按拓扑排序的降序对所有节点执行此操作.

时间复杂度:-

拓扑排序: O(E)

计算集合: O(V^2*logV)

总计: O(V^2*logV)

示例:-

1 ->3 ->42 ->43 ->24 ->55 ->空值拓扑排序:1,3,2,4,5按降序访问:-1. Set(5) = {null}2. Set(4) = Set(5) + 5 = {5}3. Set(2) = Set(4) + 4 = {4,5}4. Set(3) = Set(2) + 2 = {2,4,5}5. Set(1) = Set(3) + 1 = {1,2,4,5}

I have an adjacency list for a DAG, and I need to find all connected nodes from all nodes, for example : for a DAG below

1 -> 3 -> 4  
2 -> 4  
3 -> 2    
4 -> 5  
5 -> NULL  

I need this :

1 -> {2, 3, 4, 5}
2 -> {4, 5}
3 -> {2, 4, 5}
4 -> {5}
5 -> NULL  

Is there any efficient algorithm for this ?

解决方案

As you mentioned a DAG you can use following algorithm to get all connected components to given vertex :-

1. Do a Topological Sort of the all nodes in graph
2. Start in decreasing order of the sorted nodes.
3. Maintain a Set of all connected nodes for each node.
4. Sort adjacency list of vertex u in toposort order
5. For vertex u and each edge(u,v) and !Set(u).contains(v) do Set(u) = Set(u) union Set(v) union v
6. Do this for all node in decreasing order of toposort.

Time Complexity :-

Toposort : O(E)

Caculating Set : O(V^2*logV)

Total: O(V^2*logV)

Example:-

1 -> 3 -> 4  
2 -> 4  
3 -> 2    
4 -> 5  
5 -> NULL  

TopoSort: 1,3,2,4,5

Visiting in descending order :-
1. Set(5) = {null}
2. Set(4) = Set(5) + 5 = {5}
3. Set(2) = Set(4) + 4 = {4,5}
4. Set(3) = Set(2) + 2 = {2,4,5}
5. Set(1) = Set(3) + 1 = {1,2,4,5} 

这篇关于在邻接表中查找所有连接的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！