Bij het breedte-eerst doorlopen van een graaf (breadth-first search, afgekort BFS) worden de toppen van een graaf \(G\) op een systematische manier doorlopen. Hierbij wordt er gestart vanuit een bepaalde top \(r\) van \(G\), ook de wortel genoemd. De wortel is de eerste actieve top. Tijdens elke stap van de doorloop worden alle toppen adjacent aan de huidige actieve top bezocht, als ze nog niet eerder bezocht werden. Er wordt m.a.w. een breed zoekproces uitgevoerd voor niet-bezochte toppen. De nieuwe actieve top wordt de minst recent bezochte top die nog niet de rol van huidige top gespeeld heeft. Dit proces eindigt wanneer alle bezochte toppen actief geweest zijn.

Opmerking: bij een niet-samenhangende graaf moet deze procedure herhaald worden tot alle toppen actief geweest zijn.

Voorbeeld

In onderstaande afbeelding wordt een BFS geïllustreerd. Er wordt hier gestart van top 0. Vervolgens worden de toppen adjacent met top 0 bezocht. Deze zijn top 1, top 2 en top 3. Omdat top 1 nog niet eerder onderzocht werd, wordt top 1 de volgende actieve top en worden top 4 en 5 bezocht (top 2 bezochten we eerder al vanuit top 0). Vervolgens wordt top 2 de volgende actieve top en worden top 6 en 7 bezocht. Vervolgens wordt top 3 de volgende actieve top. Aangezien top 7 reeds bezocht werd, zal deze niet nogmaals bezocht worden. Ten slotte worden achtereenvolgens top 4, 5, 6 en 7 actief. Deze hebben echter geen adjacente toppen die nog niet eerder werden bezocht. Bij BFS worden bijgevolg achtereenvolgens top 1, top 2, top 3, top 4, top 5, top 6 en top 7 doorlopen.

In deze oefening is het de bedoeling om de volgende pseudocode te implementeren.

# De onbezochte toppen worden bijgehouden
nodes = {alle toppen}
# De nog te onderzoeken toppen worden in een wachtlijn, queue, opgeslaan
queue = []
# De oplossing wordt stap voor stap opgebouwd.
bfs = {}
while(nog niet alle toppen bezocht){
    # Selecteer een onbezochte top
    node = een onbezochte top
    queue.add(node)
    nodes.remove(node)
    while(!queue.isEmpty()){
        Node next = queue.poll()
        bfs.add(next)
        # Onderzoek deze top om adjacente onbezochte toppen te vinden
        for(alle adjacente toppen n met de top next){
            if(nodes.contains(n)){
                queue.add(n)
                nodes.remove(n)
            }
        }
    }
}
return bfs

Ontwerp en implementeer een algoritme dat een ongerichte graaf op een breedte-eerst manier doorloopt. Implementeer hiervoor een functie doorloop die als argument een ongerichte (mogelijks niet-samenhangede) graaf meekrijgt. De functie moet een lijst van toppen teruggeven in de volgorde waarin ze bij BFS doorlopen worden, startend bij een arbitraire top.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier¹. Neem eerst en vooral eens de API en de bibliotheek zelf door en stel eventueel vragen hierover voor je begint te programmeren.

Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in PyCharm moet je het bestand graph_library.py² toevoegen aan dezelfde directory als waarin je ze gebruikt. Dan kun je ze gebruiken door ze te importeren met

from graph_library import *

Dit import statement mag wel niet mee ingediend worden op dodona.

Opmerking

Het is niet toegestaan om de input van de methode doorloop aan te passen. Indien je dit wel doet, zal de test falen.

Voorbeeld:

>>> graph = undirected_graph_from_dict({1: [2], 2: [1, 3], 3: [2, 4], 4: [3]})
>>> doorloop(graph, src, dest)
[Node(1), Node(2), Node(3), Node(4)]