Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Graaf doorzoeken

Engels: Graph traversal · Ook wel: graph traversal

In het kort

Graph traversal is het bezoeken van elk punt in een graaf, om dat punt te controleren of bij te werken. Een graaf is een netwerk van punten en lijnen, en de volgorde van bezoek verschilt: diepte-eerst volgt één tak tot het einde, breedte-eerst bekijkt eerst alle buren. Het doorlopen van een boom is een bijzonder geval, en een programma ziet zo welke punten via lijnen bij elkaar horen.

Waarom is dit belangrijk?

Een computer kan de kortste verbinding tussen twee punten in een netwerk vinden zonder alle mogelijkheden met de hand te vergelijken. In de wetenschap gebruiken onderzoekers dit om netwerken en relaties tussen onderdelen stap voor stap te analyseren. Op school en op het werk versnelt dit het zoeken van een bruikbare route, maar bij veel onderlinge verbindingen stijgt de rekentijd.

Zo werkt het in de praktijk

Google Search gebruikt PageRank om webpagina's te ordenen. Een denkbeeldige bezoeker klikt van pagina naar pagina via hyperlinks. De pagina die zo het vaakst wordt bereikt, komt hoger in de resultaten.

PageRank ontstond in 1996 aan Stanford University. Larry Page en Sergey Brin onderzochten een nieuwe zoekmachine. Onderzoekers bekijken ook hoe neplinks de scores vervalsen, zodat die links buiten de telling blijven.

Met SPARQL, een aanbeveling van het W3C, stelt een programma vragen aan gegevens in RDF. RDF legt die gegevens vast als een gerichte graaf met labels. Zogeheten property paths laten een vraag punten volgen via een pad van onbekende lengte.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026