Wie konvertiert man eine Adjazenzmatrix in eine Adjazenzliste mit Python?

Question

Ich habe eine Adjazenzmatrix wie hier unten

[[ 0., 15., 0., 7., 10., 0.], 
    [ 15., 0., 9., 11., 0., 9.], 
    [ 0., 9., 0., 0., 12., 7.], 
    [ 7., 11., 0., 0., 8., 14.], 
    [ 10., 0., 12., 8., 0., 8.], 
    [ 0., 9., 7., 14., 8., 0.]] 

Wie kann ich es auf eine Adjazenzliste wie diese konvertieren?

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}], 
'2': [{'3':'9'}, {'4':'11'}, {'6':'9'}], 
'3': [{'5':'12'}, {'6':'7'}], 
'4': [{'5':'8'}, {'6':'14'}], 
'5': [{'6':'8'}]} 

?

Answer 1

Behalten Sie eine Liste der bereits hinzugefügten Kanten in einem Satz edges. Diese Kanten werden in einer frozenset gespeichert, so dass bereits hinzugefügte Paare nicht repliziert werden.

---

bauen dann Ihr Diagramm von die äußeren Liste mit einem Startindex einer aufzählt, dann der innere Liste auch mit einem Startindex von einem. Nullwertige Einträge werden mit dem if Zustand auf Werte eliminiert:

from collections import defaultdict 
from pprint import pprint 

l =[[ 0., 15., 0., 7., 10., 0.], 
    [ 15., 0., 9., 11., 0., 9.], 
    [ 0., 9., 0., 0., 12., 7.], 
    [ 7., 11., 0., 0., 8., 14.], 
    [ 10., 0., 12., 8., 0., 8.], 
    [ 0., 9., 7., 14., 8., 0.]]  

graph = defaultdict(list) 
edges = set() 

for i, v in enumerate(l, 1): 
    for j, u in enumerate(v, 1): 
     if u != 0 and frozenset([i, j]) not in edges: 
      edges.add(frozenset([i, j])) 
      graph[i].append({j: u}) 

pprint(graph) 
# {1: [{2: 15.0}, {4: 7.0}, {5: 10.0}], 
# 2: [{3: 9.0}, {4: 11.0}, {6: 9.0}], 
# 3: [{5: 12.0}, {6: 7.0}], 
# 4: [{5: 8.0}, {6: 14.0}], 
# 5: [{6: 8.0}]} 

eine defaultdict Verwendung, die einen list als Standardwert nimmt die Liste bewertet Wörterbuch on the fly helfen zu bauen.