Python函数：检查邻接矩阵中的连通性

Question

下面有一个邻接矩阵D。如何编写一个python函数，如果矩阵中的所有顶点都是连通的，则返回True，否则返回False？在

D = [['a', 'c', 'g', 'w', 'Q', 'f', 'Z', 't', 'R'], [0, 1, 2, 1, 9, 0, 0, 0, 0], [1, 0, 3, 4, 0, 0, 0, 0, 0], [2, 3, 0, 15, 2, 0, 0, 0, 0], [1, 4, 15, 0, 7, 0, 0, 0, 0], [9, 0, 2, 7, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 2, 9, 0], [0, 0, 0, 0, 0, 2, 0, 0, 20], [0, 0, 0, 0, 0, 9, 0, 0, 0], [0, 0, 0, 0, 0, 0, 20, 0, 0]] def connectivity(adjMatrix): connected = True while connected == True: # some algorithm that checks that each vertex can be connected to any other vertex # if connected -> remains True # if not connected -> False return connected print(connectivity(D))

Answer 1

您可以使用DFS或深度优先搜索。你只需要在一个顶点上运行，因为如果一个顶点连接到所有节点，那就意味着图中有完全的连通性。在

以下是递归实现的DFS的伪代码（使用调用堆栈）：

def DFS(vertex, adj, vis):
    # adj is the adjacency matrix and vis is the visited nodes so far
    set vertex as visited # example if vis is list: vis[vertex] = True
    for vert in adj[vertex]:
        if vert is not visited:
            DFS(vertex, adj, vis)
    return whether or not all vertices are visited # this only needs to happen 
                                                    # for the first call

此算法的运行时为O（n），空间复杂度为O（n）（对于vis数组）。在