我试图编写一个脚本,计算一个图的连接组件,但我无法得到正确的解决方案。 我有一个有6个节点(顶点)的简单图,节点1和2是连接的,节点3和4是连接的(6个顶点;1-2,3-4,5,6)。所以这个图包含4个连接的组件。我使用下面的脚本计算连接的组件,但得到的结果是错误的(2)。
nodes = [[1, [2], False], [2, [1], False], [3, [4], False], [4, [3], False], [5, [], False], [6, [], False]]
# 6 nodes, every node has an id, list of connected nodes and boolean whether the node has already been visited
componentsCount = 0
def mark_nodes( list_of_nodes):
global componentsCount
componentsCount = 0
for node in list_of_nodes:
node[2] = False
mark_node_auxiliary( node)
def mark_node_auxiliary( node):
global componentsCount
if not node[2] == True:
node[2] = True
for neighbor in node[1]:
nodes[neighbor - 1][2] = True
mark_node_auxiliary( nodes[neighbor - 1])
else:
unmarkedNodes = []
for neighbor in node[1]:
if not nodes[neighbor - 1][2] == True: # This condition is never met. WHY???
unmarkedNodes.append( neighbor)
componentsCount += 1
for unmarkedNode in unmarkedNodes:
mark_node_auxiliary( nodes[unmarkedNode - 1])
def get_connected_components_number( graph):
result = componentsCount
mark_nodes( graph)
for node in nodes:
if len( node[1]) == 0: # For every vertex without neighbor...
result += 1 # ... increment number of connected components by 1.
return result
print get_connected_components_number( nodes)
有人能帮我找出错误吗?
不相交集数据结构将真正帮助您在这里编写清晰的代码,请参见Wikipedia。
基本思想是将一个集合与图中的每个节点相关联,并对每个边合并其两个端点的集合。如果
x.find() == y.find()
,两个集合x
和y
是相同的这里是最简单的实现(它有糟糕的最坏情况的复杂性),但是在维基百科页面上有两个DisjointSet类的优化,在上面的几行额外的代码中,这些优化使得这一点非常有效。为了清楚起见,我省略了它们。
有时候写代码比读代码容易。
通过一些测试,我很确定只要每个连接都是双向的(比如在您的示例中),它就会一直工作。
注意,我从节点信息中删除了ID,因为它在数组中的位置是它的ID。如果这个程序不执行您需要的操作,请告诉我。
相关问题 更多 >
编程相关推荐