java - 查找给定邻接矩阵中有多少个连接的节点组

Question

我有一个列表列表，每个列表都是一个节点并且包含到其他节点的边。例如 [[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？有人可以提供有关如何解决此问题的任何提示或伪代码吗？

Answer 1

如果输入矩阵保证描述传递连接，它有一个特殊的形式，允许算法只探测矩阵元素的一个子集。这是 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