EMZETT.Glossar
1620 Begriffe aus IT, Netzwerk, Sicherheit und Programmierung: erst kurz erklärt, dann ausführlicher. Suche nach einem Wort oder wähle einen Buchstaben.
1 Treffer
Breitensuche und Tiefensuche (BFS und DFS) Breitensuche und Tiefensuche sind zwei Wege, einen Graphen oder Baum vollständig zu durchlaufen. BFS geht Ebene für Ebene, DFS so tief wie möglich, bevor es zurückgeht.
BFS nutzt eine Warteschlange (Queue-Datenstruktur) und findet in einem Graphen ohne Gewichte den kürzesten Weg (gemessen in Kanten). DFS nutzt einen Stapel (Stack-Datenstruktur) oder Rekursion (Rekursion) und eignet sich für Labyrinthe, Zyklensuche und topologische Sortierung. Beide brauchen O(V + E) Zeit.
Verwandt: Dijkstra-Algorithmus · Big-O-Notation · Graph (Datenstruktur) · Queue (Warteschlange) · Recursion (Rekursion) · Stack (Stapel)
Ganzer Artikel im Wiki →