파이썬 함수 : 인접 행렬에있는 연결성을 확인하십시오.

Question

다음과 같은 인접 행렬 D가 있습니다. 행렬의 모든 정점이 연결되어 있으면 True를 반환하는 파이썬 함수를 작성하려면 어떻게 작성합니까?

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 또는 깊이 우선 탐색을 사용할 수 있습니다. 하나의 버텍스가 모든 노드에 연결되어 있으면 그래프 내에서 전체 연결이 이루어지기 때문에 하나의 버텍스에서만 실행하면됩니다.

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를위한 의사 코드 (호출 스택을 사용)이며 정렬).