在adj矩阵图中查找最大的连通分量？

Question

我试图发现有一种方法可以在adj矩阵图中找到最大的连通分量.比如这样:

0000000110
0001100000
0000000000
0100000010
0100000100
0000000100
0000000000
1000110000
1001000000
0000000000

我已经谷歌问了这个问题并且正在努力寻找任何东西,我也读过关于图论的维基文章并且没有快乐.我认为他们必须是一个算法来解决这个问题.任何人都可以指出我正确的方向,并给我一些指示,我自己应该做些什么来解决这个问题？

Answer 1

1. 应用连接组件算法.

   对于无向图,只需选择一个节点并进行广度优先搜索.如果在第一个BFS之后剩下任何节点,请选择其中一个剩余部分并执行另一个BFS.(每个BFS可以获得一个连接组件.)

   请注意,有向图需要稍微强一些的算法才能找到强连通分量.Kosaraju的算法让人想起.

2. 从(1)计算每个连接组件中的节点数.选择最大的一个.

Answer 2

选择一个起点并开始“步行”到其他节点，直到您筋疲力尽。这样做直到找到所有组件。这将在运行O(n)，其中n是图的大小。

Python 解决方案的框架：

class Node(object):
    def __init__(self, index, neighbors):
        self.index = index
        # A set of indices (integers, not Nodes)
        self.neighbors = set(neighbors)

    def add_neighbor(self, neighbor):
        self.neighbors.add(neighbor)


class Component(object):
    def __init__(self, nodes):
        self.nodes = nodes
        self.adjacent_nodes = set()
        for node in nodes:
            self.adjacent_nodes.add(node.index)
            self.adjacent_nodes.update(node.neighbors)

    @property
    def size(self):
        return len(self.nodes)

    @property
    def node_indices(self):
        return set(node.index for node in self.nodes)

    @property
    def is_saturated(self):
        return self.node_indices == self.adjacent_nodes

    def add_node(self, node):
        self.nodes.append(node)
        self.adjacent_nodes.update(node.neighbors)


adj_matrix = [[0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
              [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
              [0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
              [1, 0, 0, 0, 1, 1, 0, 0, 0, 0],
              [1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
matrix_size = len(adj_matrix)

nodes = {}
for index in range(matrix_size):
    neighbors = [neighbor for neighbor, value in enumerate(adj_matrix[index])
                 if value == 1]
    nodes[index] = Node(index, neighbors)

components = []
index, node = nodes.popitem()
component = Component([node])
while nodes:
    if not component.is_saturated:
        missing_node_index = component.adjacent_nodes.difference(component.node_indices).pop()
        missing_node = nodes.pop(missing_node_index)
        component.add_node(missing_node)
    else:
        components.append(component)

        index, node = nodes.popitem()
        component = Component([node])

# Final component needs to be appended as well
components.append(component)

print max([component.size for component in components])