|
|||||
| Breadth-First Search (BFS) | |||||
| De vorige les zagen
we hoe je met Depth-First-Search (DFS) een graaf kunt doorzoeken. Deze
les zullen we een andere zoekmanier bekijken. Eigenlijk nog een veel
simpelere manier. Laat ik direct maar met het stroomdiagram beginnen: |
|||||
|
|
|||||
| Die blauwe route is
alleen nodig als een graaf uit meerdere losse componenten bestaat. Dat
geeft meteen een mogelijkheid om bij te houden uit hoeveel losse delen
de graaf bestaat. Merk nog even op dat knooppunten het zelfde nummer kunnen krijgen (als ze tegelijkertijd worden genummerd in het blauwe vakje). Hoe hoger het nummer, des te verder ligt een knooppunt van het allereerste beginknooppunt af. Dit stroomschema levert een BFS-boom op als je, op het moment dat je een punt nummert, ook de route die erheen leidde markeert (als er meerderen waren kies je er gewoon eentje). Overigens is dat wel voor elk beginknooppunt een verschillende boom. Voor gerichte grafen gebruik je gewoon het zelfde algoritme! Voorbeeld. |
|||||
| Hier zie je een klein voorbeeldje. Het "actuele" deel is steeds groen gekleurd, het gedeelte wat is geweest is rood. | |||||
|
|
|||||
|
© h.hofstede (h.hofstede@hogeland.nl) |
|||||
