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

发布时间：2020-12-14 05:51:13 所属栏目：Java 来源：网络整理

导读：我试图发现有一种方法可以在adj矩阵图中找到最大的连通分量.比如这样： 0000000110000110000000000000000100000010010000010000000001000000000000100011000010010000000000000000 我已经谷歌问了这个问题并且正在努力寻找任何东西,我也读过关于图论的维基文

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

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

解决方法

选择一个起点并开始“行走”到其他节点,直到你筋疲力尽.在找到所有组件之前执行此操作.这将在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,1,0],[0,[1,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])

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!