Graph Algorithms and Solutions
Detailed Solutions for Graph Algorithms and Problems:
1. Breadth-First Search (BFS)
-------------------------------------
Step 1: Understand BFS
BFS explores all neighbors of a vertex before moving deeper into the graph. It uses a queue to keep
track of vertices to explore.
Step 2: Initialize BFS
Start at vertex A. Use a queue to keep track of vertices to visit: Queue = [A]. Maintain a visited list to
track explored vertices: Visited = {}.
Step 3: Traverse the Graph
1. Visit A: Dequeue A -> Queue = []. Add B and C (neighbors of A) to the queue -> Queue = [B, C].
Mark A as visited -> Visited = {A}.
2. Visit B: Dequeue B -> Queue = [C]. Add D (neighbor of B) to the queue -> Queue = [C, D]. Mark B
as visited -> Visited = {A, B}.
3. Visit C: Dequeue C -> Queue = [D]. Add E (neighbor of C) to the queue -> Queue = [D, E]. Mark
C as visited -> Visited = {A, B, C}.
4. Visit D: Dequeue D -> Queue = [E]. Add F (neighbor of D) to the queue -> Queue = [E, F]. Mark D
as visited -> Visited = {A, B, C, D}.
5. Visit E: Dequeue E -> Queue = [F]. No neighbors to add. Mark E as visited -> Visited = {A, B, C,
D, E}.
6. Visit F: Dequeue F -> Queue = []. No neighbors to add. Mark F as visited -> Visited = {A, B, C, D,
E, F}.
BFS Order: A -> B -> C -> D -> E -> F
2. Depth-First Search (DFS)
-------------------------------------
Step 1: Understand DFS
DFS explores as far as possible along each branch before backtracking. It uses a stack (or
recursion) to keep track of vertices to visit.
Step 2: Initialize DFS
Start at vertex A. Use a stack to keep track of vertices to visit: Stack = [A]. Maintain a visited list to
track explored vertices: Visited = {}.
Step 3: Traverse the Graph
1. Visit A: Pop A -> Stack = []. Add B and C (neighbors of A) to the stack -> Stack = [C, B]. Mark A
as visited -> Visited = {A}.
2. Visit B: Pop B -> Stack = [C]. Add D (neighbor of B) to the stack -> Stack = [C, D]. Mark B as
visited -> Visited = {A, B}.
3. Visit D: Pop D -> Stack = [C]. Add F (neighbor of D) to the stack -> Stack = [C, F]. Mark D as
visited -> Visited = {A, B, D}.
4. Visit F: Pop F -> Stack = [C]. No neighbors to add. Mark F as visited -> Visited = {A, B, D, F}.
5. Visit C: Pop C -> Stack = []. Add E (neighbor of C) to the stack -> Stack = [E]. Mark C as visited ->
Visited = {A, B, D, F, C}.
6. Visit E: Pop E -> Stack = []. No neighbors to add. Mark E as visited -> Visited = {A, B, D, F, C, E}.
DFS Order: A -> B -> D -> F -> C -> E
3. Minimum Spanning Tree (MST) using Kruskal's Algorithm
-------------------------------------
Question: Find the MST for the graph with the following edges: {A-B: 1, A-C: 4, B-C: 2, B-D: 5, C-D:
3}.
Step 1: Sort the edges by weight
Sorted edges: {A-B: 1, B-C: 2, C-D: 3, A-C: 4, B-D: 5}.
Step 2: Add edges one by one, avoiding cycles
Initialize MST = {} and MST weight = 0. Add edges in order, checking for cycles.
1. Add edge A-B (1): No cycle is formed. Add A-B to MST. MST = {A-B}, MST weight = 1.
2. Add edge B-C (2): No cycle is formed. Add B-C to MST. MST = {A-B, B-C}, MST weight = 3.
3. Add edge C-D (3): No cycle is formed. Add C-D to MST. MST = {A-B, B-C, C-D}, MST weight = 6.
4. Skip edges A-C (4) and B-D (5): Adding these edges forms cycles.
Final MST: {A-B, B-C, C-D}, Total Weight = 6.
4. Dijkstra's Algorithm
-------------------------------------
Question: Find the shortest path from vertex A to all other vertices in the graph: Edges: {A->B (1),
A->C (4), B->C (2), B->D (6), C->D (3)}.
Step 1: Initialize Variables
Create a distance table: distance[A] = 0, distance[B], distance[C], distance[D] = infinity. Priority
Queue = [(0, A)].
Step 2: Algorithm Steps
1. Process vertex A: Dequeue (0, A). Explore neighbors of A: Update distance[B] = 1, distance[C] =
4. Queue: [(1, B), (4, C)].
2. Process vertex B: Dequeue (1, B). Explore neighbors of B: Update distance[C] = 3, distance[D] =
7. Queue: [(3, C), (7, D)].
3. Process vertex C: Dequeue (3, C). Explore neighbors of C: Update distance[D] = 6. Queue: [(6,
D)].
4. Process vertex D: Dequeue (6, D). No neighbors to explore.
Shortest Distances: A->A = 0, A->B = 1, A->C = 3, A->D = 6.
5. 0/1 Knapsack Problem
-------------------------------------
Question: Solve for weights {1, 2, 4, 2}, values {10, 20, 40, 25}, and capacity = 5.
Step 1: Create a DP Table
Define DP[i][w] as the maximum value we can get using the first i items and weight limit w.
Step 2: Fill the DP Table
Use the recurrence relation: DP[i][w] = max(DP[i-1][w], value[i] + DP[i-1][w-weight[i]]).
1. For item 1 (weight 1, value 10): Fill row based on whether weight w >= 1.
2. For item 2 (weight 2, value 20): Include/exclude based on whether w >= 2.
3. For item 3 (weight 4, value 40): Include/exclude based on whether w >= 4.
4. For item 4 (weight 2, value 25): Include/exclude based on whether w >= 2.
Final DP Table: [0, 10, 25, 35, 45, 55]. The maximum value is 55.
