Most őrülten izgalmas dolgokat fogunk csinálni irányított gráfokkal. Megnézzük, hogy az irányított gráfokban hogyan működnek a különböző gráf-algoritmusok. Kezdjük a DFS algoritmussal, vagyis a gráfok mélységi keresésével. A mélységi keresés valójában nagyon egyszerű. A DFS algoritmusnak az a lényege, hogy kiindulunk egy csúcsból… és megyünk ameddig tudunk. Az, hogy merre megyünk, teljesen a véletlen műve. Egyszer aztán elérkezünk egy olyan pontba, ahonnan már nincs tovább. Innen már csak olyan csúcsba tudnánk továbblépni, ahol korábban már jártunk. Ekkor visszaugrunk egészen addig… ahonnan még vezet út bejáratlan csúcsba. Ha már minden csúcshoz eljutottunk, akkor a DFS algoritmus véget ér. 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”. Legyen u és v két olyan csúcs, amelyek a DFS-fában nem szomszédosak és vezet út u-ból v-be. Hogyha az eredeti gráfban van u-ból v-be vezető él, akkor ezt az élt „előre-él”nek nevezzük. ELŐRE-ÉL Itt van aztán ez a másik él is. Ez pont olyan, mint az „előre-él” csak éppen visszafelé mutat. Legyen u és v két olyan csúcs a DFS-fában, hogy vezet út u-ból v-be. Hogyha az eredeti gráfban van fordított irányú, vagyis v-ből u-ba vezető él, akkor ezt az élt „vissza-él”nek nevezzük. Itt most van még néhány „vissza-él”. Vannak aztán olyan élek is, amelyek a DFS-fa két különböző ágát kötik össze. Legyen u és v két olyan csúcs a DFS-fában, hogy sem u-ból v-be, sem v-ből u-ba nem vezet út. Hogyha az eredeti gráfban van u-ból v-be vezető él, akkor ezt az élt „kereszt-él”nek nevezzük. A DFS-fa rengeteg hasznos információt árul el az eredeti gráf szerkezetéről. Ha a DFS-fában van vissza-él, az azt jelenti, hogy a gráf ciklikus. Tehát körbe lehet menni. Éppenséggel most elég sokféleképpen… Hogyha az eredeti gráf aciklikus, vagyis nincsenek benne körök… az DFS-fa alapján is azonnal kiderül: Nincsenek benne vissza-élek. Most, hogy mindezt megtudtuk, lássuk mi a helyzet a BFS algoritmussal.