我有一个列表列表,每个列表都是一个节点,并且包含到其他节点的边。例如
[[1, 1, 0], [1, 1, 0], [0, 0, 1]]
该节点有 1
当它引用自己的位置时,以及当它有到另一个节点的边缘时,以及 0
当不存在边时。
这意味着 node 0
( [1, 1, 0]
) 连接到 node 1
,和node 2
( [0,0,1]
) 未连接到任何其他节点。因此,这个列表列表可以被认为是一个邻接矩阵:
1 1 0 <- node 0
1 1 0 <- node 1
0 0 1 <- node 2
除此之外,一个节点是否与另一个节点连接是可传递的,这意味着如果 node 1
连接到node 2
和node 2
连接到node 3
,节点1
和3
也相互连接(通过传递性)。
考虑到所有这些,我希望能够知道给定一个矩阵有多少个连接的组。我应该使用什么算法,递归 DFS?有人可以提供有关如何解决此问题的任何提示或伪代码吗?
最佳答案
如果输入矩阵保证描述传递连通性,则它具有一种特殊的形式,允许算法仅探测矩阵元素的子集。以下是 Python 中的示例实现:
def count_connected_groups(adj):
n = len(adj)
nodes_to_check = set([i for i in range(n)]) # [] not needed in python 3
count = 0
while nodes_to_check:
count += 1
node = nodes_to_check.pop()
adjacent = adj[node]
other_group_members = set()
for i in nodes_to_check:
if adjacent[i]:
other_group_members.add(i)
nodes_to_check -= other_group_members
return count
# your example:
adj_0 = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
# same with tuples and booleans:
adj_1 = ((True, True, False), (True, True, False), (False, False, True))
# another connectivity matrix:
adj_2 = ((1, 1, 1, 0, 0),
(1, 1, 1, 0, 0),
(1, 1, 1, 0, 0),
(0, 0, 0, 1, 1),
(0, 0, 0, 1, 1))
# and yet another:
adj_3 = ((1, 0, 1, 0, 0),
(0, 1, 0, 1, 0),
(1, 0, 1, 0, 0),
(0, 1, 0, 1, 0),
(0, 0, 0, 0, 1))
for a in adj_0, adj_1, adj_2, adj_3:
print(a)
print(count_connected_groups(a))
# [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
# 2
# ((True, True, False), (True, True, False), (False, False, True))
# 2
# ((1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (0, 0, 0, 1, 1), (0, 0, 0, 1, 1))
# 2
# ((1, 0, 1, 0, 0), (0, 1, 0, 1, 0), (1, 0, 1, 0, 0), (0, 1, 0, 1, 0), (0, 0, 0, 0, 1))
# 3
同一算法的优化版本(可读性较差,但速度更快且更容易翻译成其他语言)如下:
def count_connected_groups(adj):
n = len(adj)
nodes_to_check = [i for i in range(n)] # [0, 1, ..., n-1]
count = 0
while n:
count += 1
n -= 1; node = nodes_to_check[n]
adjacent = adj[node]
i = 0
while i < n:
other_node = nodes_to_check[i]
if adjacent[other_node]:
n -= 1; nodes_to_check[i] = nodes_to_check[n]
else:
i += 1
return count
关于java - 查找给定邻接矩阵中有多少个相连的节点组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57825109/