Arborele muchiilor de avansare

Ca și la BFS, dacă atunci când avansăm din nodul curent într-un vecin nevizitat al său, considerăm o muchie cu cele două noduri ca extremități, vom obține un arbore de acoperire pentru componenta conexă a nodului de start. Acesta nu mai este un arbore al drumurilor minime de la nodul de pornire la toate celelalte (cum este cazul la BFS) dar are alte proprietăți (un prim exemplu: este o structură aciclică pe care se pot face calcule bazate pe programare dinamică; un alt exemplu: dacă facem parcurgerea pe un arbore oarecare îl transformăm pe acesta într-un arbore cu rădăcina în nodul de pornire etc).