Past exam question: 2066 Jestha (Back), Q9
Open in the Padhaiko appQuestion
Define in-degree and out-degree in directed graph. Discuss the Depth First Traversal (DFT) and Breadth-First Traversal (BFT) with suitable examples.
Solution
In-Degree and Out-Degree in a Directed Graph:
- In-degree (): Number of directed edges entering vertex (edges of form ).
- Out-degree (): Number of directed edges leaving vertex (edges of form ).
(Always .)
DFT vs. BFT with Example: Consider directed edges A->B, A->C, B->D, C->E, starting from A:
- Depth-First Traversal (DFT): Uses a Stack (or recursion) to explore as deep as possible along each branch before backtracking.
- Trace: Visit
Apush/visitBvisitD(dead end, backtrack) visitCvisitEA, B, D, C, E.
- Trace: Visit
- Breadth-First Traversal (BFT): Uses a Queue (FIFO) to visit all neighbors level by level.
- Trace: Enqueue
AvisitA, enqueueB, CvisitB, enqueueDvisitC, enqueueEvisitD, EA, B, C, D, E.
- Trace: Enqueue
Answer:
In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges. On A->B, A->C, B->D, C->E from A, DFT (stack) visits A, B, D, C, E while BFT (queue) visits A, B, C, D, E.