DFS-fa | mateking
 

DFS-fa

A DFS algoritmus eredményeként kapjuk a DFS-fát.

Hogyha a DFS-fába berajzoljuk az eredeti gráf többi élét is, akkor ezek az élek három típusba sorolhatóak. Vannak olyan élek, amelyek képesek lerövidíteni egy utat a DFS fában. Ezeket az éleket úgy hívjuk, hogy "előre-él". Ha az eredeti gráfban van fordított irányú él, akkor ezt az élt "vissza-él"-nek nevezzük. Hogyha az eredeti gráfban van $u$-ból $v$-be vezető él, akkor ezt az élt "kereszt-él"-nek nevezzük.