Python函數：檢查鄰接矩陣中的連通性

-1

我有一個下面的鄰接矩陣D.如何編寫一個python函數，如果矩陣中的所有頂點都連接，則返回True;否則返回False？Python函數：檢查鄰接矩陣中的連通性

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))

來源

2017-10-10 V. Loh

這是一個很好理解的話題。您應該能夠通過快速搜索輕鬆找到一個有效的算法。 –

您可以使用DFS或深度優先搜索。你只需要在一個頂點上運行，因爲如果一個頂點連接到所有的節點，這意味着圖中有完整的連接。

這裏爲遞歸地執行DFS的僞代碼（使用調用堆棧）：用O（n）的空間複雜度

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）的運行時（對於vis數組）。

來源

2017-10-10 05:56:34 Albert

Python函數：檢查鄰接矩陣中的連通性

回答

相關問題