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 de interface GraafDoorloper¹ in een klasse genaamd BreedteEerstDoorloper. Hiervoor schrijf je een methode public List<Node<String>> doorloop(UndirectedGraph<String> graph), die een ongerichte graaf als argument heeft. De uitvoer is een lijst van toppen in de volgorde waarin ze bij BFS doorlopen worden.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. Deze bevat onder meer de klassen UndirectedGraph en Node. De API van deze bibliotheek vind je hier². Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.

Opmerking

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