PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q9

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

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:

(Always .)

DFT vs. BFT with Example: Consider directed edges A->B, A->C, B->D, C->E, starting from A:

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.

All past exam questions for Data Structure and Algorithms