Ga naar hoofdinhoud

Bouwsteen 1 — de graph in Python

Hier bouw je op verder

Leerdoel: je kunt een gewogen graph opslaan in een Python-dict, en voor één node zijn buren ophalen.

Wat we willen​

We hebben dit plaatje:

       4
   A ─────── B
   │         │
   2         1
   │         │
   C ─────── D
       8

Dit moet in Python, zó dat we straks kunnen vragen wie de buren van A zijn, en als antwoord krijgen: B met gewicht 4, en C met gewicht 2.

Eén node, één lijstje​

Voor elke node hebben we een lijstje van buren nodig, met hun gewicht. Dat wordt een lijst van tuples:

buren_van_A = [('B', 4), ('C', 2)]

Lees: "de buren van A zijn: B met gewicht 4, en C met gewicht 2."

Een tuple houdt de naam van de buur en het gewicht bij elkaar. Het is een lijst van tuples, want een node kan meer dan één buur hebben.

Alle nodes in één dict​

Voor alle vier de nodes samen maken we één dict:

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 1)],
    'C': [('A', 2), ('D', 8)],
    'D': [('B', 1), ('C', 8)],
}

De sleutel is de naam van de node, de waarde zijn buren.

Elke edge staat twee keer in deze dict. De edge A─B met gewicht 4 zie je bij 'A': [..., ('B', 4), ...] én bij 'B': [('A', 4), ...]. Een weg die je beide kanten op mag, sla je aan beide kanten op.

Voorspel​

Wat denk je dat dit print?

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 1)],
    'C': [('A', 2), ('D', 8)],
    'D': [('B', 1), ('C', 8)],
}

print(graph['A'])
Antwoord
[('B', 4), ('C', 2)]

Een lijst met twee tuples. Vanuit A zijn er twee buren.

Run​

Python
Code-omgeving wordt voorbereid…

Door de buren lopen​

Met for buur, gewicht in graph['A']: pak je elke tuple uit in twee losse variabelen:

Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
A → B (gewicht 4)
A → C (gewicht 2)

Wat nu nog mist​

De graph staat erin en de buren komen eruit. Er is nog geen plek voor de afstanden en voor wie al bekend is; dat is bouwsteen 2.

Door naar bouwsteen 2: de tabel →.