Bij het diepte-eerst doorlopen van een graaf (depth-first search, afgekort DFS) worden de toppen van een graaf \(G\) op een systematische manier doorlopen. Bij deze doorloop wordt de top die momenteel bezocht wordt, de actieve top genoemd. DFS start vanuit een bepaalde top \(r\) van \(G\), ook de wortel genoemd. De wortel is dan de eerste actieve top. Elke stap van de doorloop kan als volgt beschreven worden. Zij \(k\) de huidige actieve top in de doorloop en veronderstel dat niet alle toppen in de component van \(G\) die \(k\) bevat, reeds bezocht zijn, dan vindt één van onderstaande acties plaats.

• Als er onbezochte toppen adjacent met \(k\) zijn, dan wordt een top adjacent met \(k\) geselecteerd die nog niet bezocht is. Dit is de volgende top van de doorloop. Deze top wordt de nieuwe actieve top.

• Wanneer alle toppen adjacent met \(k\) reeds bezocht zijn, dan wordt \(k\) als een doodlopende top beschouwd en keren we terug naar de top die de actieve top was vooraleer we \(k\) voor het eerst bezochten. Deze top wordt de huidige actieve top.

Deze algemene stap wordt herhaald totdat elke top in deze component van \(G\) bezocht is. Wanneer niet alle toppen van \(G\) bezocht werden, dan wordt een niet-bezochte top gekozen als de volgende actieve top, waarna de doorloop verdergaat. Dit proces eindigt wanneer alle bezochte toppen actief geweest zijn.

Voorbeeld

In onderstaande afbeelding wordt een DFS geïllustreerd. Er wordt hier gestart van top 0 (huidige actieve top). Vervolgens wordt een top adjacent met top 0 geselecteerd indien deze nog niet bezocht is. Hier zijn zowel top 1, top 4 en top 7 nog niet bezocht. We kiezen hier echter maar één top, bv. top 1. Deze wordt de volgende actieve top. Vervolgens wordt een top adjacent met top 1 bezocht. Ook hier zijn er meerdere mogelijkheden, maar we kiezen er één, bv. top 2. Top 2 is nu de nieuwe actieve top. Aangezien top 2 geen adjacente toppen heeft die nog niet bezocht zijn, wordt top 1 terug actief. Top 1 heeft nog één adjacente top die nog niet bezocht is, nl. top 3. Bijgevolg wordt top 3 actief. Deze heeft echter geen adjacente toppen die nog niet bezocht zijn. Bijgevolg wordt top 1 terug actief. Top 1 heeft ook geen adjacente toppen meer die nog niet bezocht zijn. Bijgevolg wordt top 0 terug actief. Analoog wordt vervolgens top 4 actief. Daarna kan top 5 actief worden, waarna terug top 4 actief wordt en vervolgens top 6 en top 7 actief kunnen worden. Bij deze DFS worden bijgevolg achtereenvolgens top 0, 1, 2, 3, 4, 5, 6 en 7 doorlopen.

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

// De onbezochte toppen worden bijgehouden
nodes = {alle toppen}
// De oplossing wordt stap voor stap opgebouwd.
dfs = {}
while(nog niet alle toppen bezocht){
    // Selecteer een onbezochte top
    node = een onbezochte top
    recursieDFS(node, dfs)
}
return dfs

De pseudocode voor de methode recursieDFS ziet er als volgt uit.

function recursieDFS(node, dfs)
  dfs.add(node);
  nodes.remove(node);
  for(alle adjacente toppen van node){
    if(nodes.contains(adjacente top)){
      recursieDFS(adjacente top, dfs);
    }
}

Ontwerp en implementeer een algoritme dat een ongerichte graaf op een diepte-eerst manier doorloopt. Implementeer hiervoor de interface GraafDoorloper¹ in een klasse genaamd DiepteEerstDoorloper. 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 DFS voor het eerst bezocht 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.