graph w pythonie

dzien dobry, mi trzeba realizowac graph ktory przyjmowal macierz sąsiedztwa czyli
graph = [
[0, 1, 1, 1, 1],
[1, 0, 1, 0, 1],
[1, 1, 0, 0, 1],
[1, 0, 0, 0, 0],
[1, 1, 1, 0, 0]]

zamiast listy sasiedztwa

graph0 = {'1': ['2', '3','4','5'], 
          '2': ['1', '3', '5'], 
          '3': ['1','2', '5'],
          '4':['1'],
          '5':['1','2','3']} 

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited
visited = dfs(graph0,'1', [])
print(visited)

po prostu wymienic nie wyjdzie, bo tak nie dziala

Nie jestem pewien, czy o to Ci chodzi, ale jakbyś chciał przekonwertować graph do postaci graph0, to możesz zrobić to tak:

from numpy import asarray
{str(i+1):item for i, item in enumerate(asarray(graph, dtype=str).tolist())}

{'1': ['0', '1', '1', '1', '1'],
 '2': ['1', '0', '1', '0', '1'],
 '3': ['1', '1', '0', '0', '1'],
 '4': ['1', '0', '0', '0', '0'],
 '5': ['1', '1', '1', '0', '0']}

A tu: https://stackoverflow.com/questions/11803800/depth-first-search-using-adjacency-matrix o dfs - ie.

Z tego co się orientuję lepiej użyć listy albo innej struktury niż tablicy. W przypadku dużej ilości danych tablica może być nieskalowalna.

damiansk napisał(a):

Z tego co się orientuję lepiej użyć listy albo innej struktury niż tablicy. W przypadku dużej ilości danych tablica może być nieskalowalna.

W Pythonie obiekt list to pod spodem zwykła tablica wskaźników na elementy, co zapewnia stały O(1) dostęp do elementów. W związku z tym rzeczywiście Pythonowa lista ma typowe dla tablic problemy. Jednak użycie struktury typu linked-list to zwykły trade-off gdzie zyskujesz elastyczność, kosztem czasu dostępu do elementów który spada do liniowego O(n). W związku z tym właściwe dobranie struktury zależy już od konkretnego przypadku. W tym konkretnym przypadku do przechowywania macierzy sąsiedztw, użycie obiektu list (czyli zwykłej tablicy) jest najlepszym wyborem właśnie przez stały czas dostępu do elementów O(1).