Python-Funktion: Auf Konnektivität in Adjazenzmatrix prüfen

Question

Ich habe eine Adjazenzmatrix D unten. Wie schreibe ich eine Python-Funktion, die True zurückgibt, wenn alle Scheitelpunkte in der Matrix verbunden sind, oder False, wenn nicht?

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

können Sie verwenden DFS oder Tiefensuche. Sie müssen nur auf einem Scheitelpunkt laufen, denn wenn ein Scheitelpunkt mit allen Knoten verbunden ist, bedeutet dies, dass eine vollständige Konnektivität innerhalb des Graphen besteht.

Hier ist Pseudo-Code für eine rekursiv implementiert DFS (mit dem Call-Stack):

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 

Dieser Algorithmus wird eine Laufzeit von O (n) hat mit einer Speicherkomplexität von O (n) (für die vis Array).