无向图，获取所有可访问节点的列表

Question

我刚接触图论，遇到一个问题。我有一个图，每次都可能不同。我想知道有没有什么算法可以从一个随机的节点出发，找出我可以访问到哪些节点。这个问题是在我读了一篇文章后产生的。

举个例子：

	A	B	C	D	E
A	0	0	0	1	0
B	0	0	1	0	0
C	0	1	0	0	0
D	1	0	0	0	1
E	0	0	0	1	0

我想知道怎么能得到这些节点之间的连接关系，比如A、D和E是连在一起的，而B和C是连在一起的。

我对这个领域还很陌生，希望你能用数学的方式来解释，或者用Python、C#、C++或JavaScript来写出解决方案。

Answer 1

你想要找出图的连通分量。

你可以使用深度优先遍历的方法，同时记录哪些节点已经被标记为属于某个分量。

如果你用邻接表来表示图，这个算法会更高效，不过你也可以用你在问题中提到的邻接矩阵来实现。

下面是一些Python代码，它会给每个顶点分配一个分量编号。拥有相同编号的顶点属于同一个分量：

def components(adjacency):
    components = [0] * len(adjacency)
    component = 1

    def findcomponent(vertex):
        if components[vertex] == 0:
            components[vertex] = component
            for neighbor, connected in enumerate(adjacency[vertex]):
                if connected:
                    findcomponent(neighbor)
        
    for vertex, row in enumerate(adjacency):
        for neighbor, connected in enumerate(row):
            if connected and components[neighbor] == 0:
                findcomponent(vertex)
                component += 1

    return components

接下来是如何在你的示例图中使用这个函数：

adjacency = [
    [0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 0, 1, 0]
]
result = components(adjacency)
print(result)

# If we want to use the names "A", "B",... for the nodes, then:
vertices = [*"ABCDE"]
print(dict(zip(vertices, result)))

上面代码的输出结果将是：

[1, 2, 2, 1, 1]
{'A': 1, 'B': 2, 'C': 2, 'D': 1, 'E': 1}

这两个输出都将顶点映射到它们的分量编号：第一个输出只是使用每个顶点的索引，第二个输出则使用每个顶点的名称。