我试图发现有一种方法可以在adj矩阵图中找到最大的连通分量.比如这样：
0000000110 0001100000 0000000000 0100000010 0100000100 0000000100 0000000000 1000110000 1001000000 0000000000
我已经谷歌问了这个问题并且正在努力寻找任何东西,我也读过关于图论的维基文章并且没有快乐.我认为他们必须是一个算法来解决这个问题.任何人都可以指出我正确的方向,并给我一些指示,我自己应该做些什么来解决这个问题？
解决方法
选择一个起点并开始“行走”到其他节点,直到你筋疲力尽.在找到所有组件之前执行此操作.这将在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])
