1

我尝试编写一个脚本来计算图形的连接组件，但我无法获得正确的解决方案。我有一个包含 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)

谁能帮我找出错误？

4

3 回答 3

6

不相交集数据结构将真正帮助您在这里编写清晰的代码，请参阅Wikipedia。

基本思想是您将一个集合与图中的每个节点相关联，并且对于每条边，您合并其两个端点的集合。两组x，y如果相同x.find() == y.find()

这是最幼稚的实现（最坏情况下的复杂性很差），但在上面的维基百科页面上有一些 DisjointSet 类的优化，在几行额外的代码中可以提高效率。为了清楚起见，我省略了它们。

nodes = [[1, [2]], [2, [1]], [3, [4]], [4, [3]], [5, []], [6, []]]

def count_components(nodes):
    sets = {}
    for node in nodes:
      sets[node[0]] = DisjointSet()
    for node in nodes:
        for vtx in node[1]:
            sets[node[0]].union(sets[vtx])
    return len(set(x.find() for x in sets.itervalues()))

class DisjointSet(object):
    def __init__(self):
        self.parent = None

    def find(self):
        if self.parent is None: return self
        return self.parent.find()

    def union(self, other):
        them = other.find()
        us = self.find()
        if them != us:
            us.parent = them

print count_components(nodes)
于 2010-10-24T12:20:30.883 回答
4

有时编写代码比阅读代码更容易。

对此进行一些测试，我很确定只要每个连接都是双向的（例如在您的示例中），它就会始终有效。

def recursivelyMark(nodeID, nodes):
    (connections, visited) = nodes[nodeID]
    if visited:
        return
    nodes[nodeID][1] = True
    for connectedNodeID in connections:
        recursivelyMark(connectedNodeID, nodes)

def main():
    nodes = [[[1], False], [[0], False], [[3], False], [[2], False], [[], False], [[], False]]
    componentsCount = 0
    for (nodeID, (connections, visited)) in enumerate(nodes):
        if visited == False:
            componentsCount += 1
            recursivelyMark(nodeID, nodes)
    print(componentsCount)

if __name__ == '__main__':
    main()

请注意，我从节点信息中删除了 ID，因为它在数组中的位置是它的 ID。如果这个程序不能满足你的需要，请告诉我。

于 2010-10-23T17:57:35.147 回答
0

我把我的答案放在这里来缓存我的学习。我用深度优先搜索来解决。

给定一个邻接列表，它的图形如下所示：

在此处输入图像描述

深度优先搜索，递归地触及图中的所有节点。这部分很简单：

    count=0
    # I touch all the nodes and if dfs returns True, count+=1
    for node in graph:
        if dfs(node):
            count+=1

现在我们应该在 dfs 中编写逻辑。如果我们从节点 0 开始，我们将其标记为已访问，然后我们访问它的邻居。当我们访问邻居时，最终我们访问节点 2，如果我们到达节点 2，这意味着图是连接的，所以我们返回 True。

    def dfs(node):
        if node in visited:
            return False
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)
        # If I get here that means i explored all
        return True

我们从节点 0 开始，我们访问到节点 2，我们返回 True。由于我写了for node in graph:，现在它将从节点 1 开始，但由于节点 1 已经访问过，它将返回 False。

这是完整的代码：

class Solution:
    def count_connected(self,graph):
        visited=set()
        count=0
        def dfs(node):
            if node in visited:
                return False
            visited.add(node)
            for neighbor in graph[node]:
                dfs(neighbor)
            # If I get here that means i explored all
            return True
        # explore all the neightbors of nodes
        for node in graph:
            if dfs(node):
                count+=1
        return count
于 2021-10-27T21:09:55.813 回答