2017-10-10 34 views
-1

私は以下の隣接行列Dを持っています。行列のすべての頂点が接続されている場合にTrueを返し、そうでない場合にFalseを返すPython関数を書き込むにはどうすればよいですか?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))

+1

これはよく理解されているトピックです。クイック検索で効率的なアルゴリズムを簡単に見つけることができます。 –

答えて

0

あなたはDFSまたは深さ優先探索を使用することができます。 1つの頂点がすべてのノードに接続されていれば、グラフ内に完全な接続性があるので、1つの頂点だけを実行する必要があります。

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)とのランタイムを持つことになります(n)はOのスペースの複雑さを持つ(vis用:ここ

は、再帰的に実装DFSのための擬似コード(コール・スタックを使用して)でありますアレイ)。

関連する問題