Een grafe is niet ingebouwd als datastructuur in Python. We modelleren de grafe aan de hand van een zelfgedefinieerde klasse.

👀 Voorbeeld - Een klasse voor grafen

We modelleren een grafe aan de hand van zijn knopen en bogen.

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

De knopen gaan we voorstellen door een verzameling, en de bogen door een verzameling van tupels.

👀 Voorbeeld - Vlaamse steden modelleren

Kijk eens naar deze grafe, die enkele Vlaamse steden modelleert waartussen een snelweg loopt.

We kunnen deze grafe modelleren zoals hieronder:

knopen = { 'Kortrijk', 'Antwerpen', 'Gent' , 'Brussel', 'Hasselt' }
bogen = {
('Gent','Kortrijk'),
('Antwerpen', 'Gent'),
('Brussel', 'Gent'),
('Antwerpen','Brussel'),
('Antwerpen','Hasselt'),
('Brussel','Hasselt')
}

snelwegen = Grafe(knopen, bogen)
print(snelwegen.knopen)
print(snelwegen.bogen)

🧠 Denkoefening - Verzamelingen?

Probeer eens te verklaren waarom verzamelingen een geschikte datastructuur zijn om knopen en bogen voor te stellen?

💻 Programmeeroefening - Amerikaanse steden

Kijk eens naar de gewogen grafe met Amerikaanse steden. In deze opdracht ga je deze grafe modelleren, de gewichten laten we voorlopig achterwege.

---

Opdracht

• Kopieer de klasse Grafe in de editor hieronder.
• Maak een verzameling knopen aan met de knopen van de grafe van Amerikaanse steden.
• Maak een verzameling bogen aan, met de bogen van de grafe van Amerikaanse steden. Belangrijk: sorteer de knopen in elke boog alfabetisch!
• Gebruik deze verzamelingen om de grafe aan te maken, plaats deze in een variabele steden.
• print vervolgens alle knopen van de grafe als een gesorteerde lijst, met sorted(steden.knopen).
• print tenslotte alle bogen van de grafe als een gesorteerde lijst, met sorted(steden.bogen).