matrizen.py

import copy
#Matrix!
mat_original = [
    [0,1,0,0,1,0],
    [1,0,0,0,0,0],
    [0,0,0,1,1,0],
    [0,0,1,0,1,1],
    [1,0,1,1,0,0],
    [0,0,0,1,0,0],
]

def printmat(mat):
    print('---------')
    for i in range(0,len(mat)):
        print(mat[i])

print('Die Matrix ist:')
printmat(mat_original)

#Anzahl der Knoten (=Anzahl der Zeilen)
nodes = len(mat_original)
print('Die Anzahl der Knoten ist', str(nodes) + '.')

#Anzahl Kanten
edges = 0
for i in range(0,len(mat_original)):
    edges += mat_original[i].count(1) # Zählt die Anzahl der einsen in Spalte i
edges = int(edges/2)
print ('Die Anzahl der Kanten ist', str(edges) + '.')

#Breitensuche
def breadth_first_search (mat, start):
    consistent = True

    #Besuchte Werte initialisieren
    visited = []
    for i in range(0, len(mat)):
        visited.append(False)

    visited[start] = True

    #Warteschlange initialisieren
    queue = []
    queue.append(start)

    while (len(queue) != 0):

        current = queue.pop(0) # Holt das erste Element aus der Warteschlange raus und löscht diese

        #Knoten, die in Matrix mit start verbunden sind herrausfinden
        for i in range(0, len(mat[current])): #Jedes Element durchgehen
            if (mat[current][i] == 1 and visited[i] == False):
                    queue.append(i) #Gefundenen Knoten hinzufügen
                    visited[i] = True #Gefundenen Knoten als besucht markieren

    #Prüfen, ob Netz zusammenhängend ist
    for i in range(0, len(visited)):
        if (visited[i] == False):
            consistent = False

    return consistent

def del_edge(mat, x, y):
    mat_copy = copy.deepcopy(mat)
    mat_copy[x][y] = 0
    mat_copy[y][x] = 0
    return mat_copy

#Test auf kritische Leitungen
def critical_connection (mat):
    print('Test auf kritische Leitungen:')
    for r in range(0, len(mat)): #Geht durch die Zeilen
        for c in range(0,len(mat[r])): #Geht durch Spalten
            if (mat[c][r] == 1): #Wenn Kante gefunden
                del_mat = del_edge(mat, c, r)
                if (breadth_first_search(del_mat, 0) == False):
                    print("Kritische Leitung bei", c , "->" , r)


result = breadth_first_search(mat_original, 5)
if result:
    print('Die Matrix ist zusammenhängend.')
    critical_connection(mat_original)
else:
    print('Die Matrix ist nicht zusammenhängend.')