Graphs: Representations, Traversals, Shortest Paths & Applications

What is a Graph?

A graph is a non-linear data structure consisting of:

• Vertices (Nodes): Represent entities (e.g., cities, computers, people).
• Edges: Represent relationships (e.g., roads, connections, friendships).

Types of Graphs

Real-World Graphs

• Social Networks (Facebook): Vertices = users, edges = friendships.
• Transportation (NTC Bus Routes): Vertices = bus stops, edges = routes.
• Computer Networks (Ncell): Vertices = routers, edges = connections.

Graph Representations

1. Adjacency Matrix

A 2D array where matrix[i][j] = 1 if there’s an edge from vertex i to j. Example: 4-vertex undirected graph.

Adjacency Matrix:

      1  2  3  4
1 [0, 1, 1, 0]
2 [1, 0, 1, 1]
3 [1, 1, 0, 0]
4 [0, 1, 0, 0]

2. Adjacency List

A list of lists where each index represents a vertex and contains its adjacent vertices. Same graph as adjacency list:

1: [2, 3]
2: [1, 3, 4]
3: [1, 2]
4: [2]

Comparison Table:

Graph Traversals

1. Breadth-First Search (BFS)

Explores all neighbors at the present depth before moving deeper. Algorithm Steps:

Example: Traverse the graph starting from vertex 1.

from collections import deque

def bfs(graph, start):
    visited = [False] * (len(graph))
    queue = deque([start])
    visited[start] = True
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

graph = {0: [1, 2], 1: [2], 2: [3], 3: [1]}
bfs(graph, 0)  # Output: 0 1 2 3

Trace Table:

2. Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking. Algorithm Steps:

Example: Traverse the same graph using DFS.

def dfs(graph, start):
    visited = [False] * (len(graph))
    stack = [start]
    while stack:
        vertex = stack.pop()
        if not visited[vertex]:
            print(vertex, end=" ")
            visited[vertex] = True
            stack.extend(reversed(graph[vertex]))

dfs(graph, 0)  # Output: 0 2 3 1

Trace Table:

Minimum Spanning Tree (MST)

A subset of edges connecting all vertices with the minimum total weight.

1. Prim’s Algorithm

Greedily adds the cheapest edge from the growing tree. Example: Find MST for the weighted graph below.

graph TD
    A["1"] -- 2 --> B["2"]
    A -- 3 --> C["3"]
    B -- 1 --> C
    B -- 4 --> D["4"]
    C -- 5 --> D

Steps:

1. Start with vertex 1.
2. Add edge (1-2) with weight 2.
3. Add edge (2-3) with weight 1.
4. Add edge (3-4) with weight 5.

Final MST:

Edges: (1-2), (2-3), (3-4)
Total Weight: 8

Python Implementation:

import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    while edges and len(mst) < len(graph) - 1:
        weight, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            for neighbor, w in graph[v]:
                if neighbor not in visited:
                    heapq.heappush(edges, (w, v, neighbor))
    return mst

graph = {
    1: [(2, 2), (3, 3)],
    2: [(1, 2), (3, 1), (4, 4)],
    3: [(1, 3), (2, 1), (4, 5)],
    4: [(2, 4), (3, 5)]
}
print(prim(graph, 1))  # Output: [(1, 2, 2), (2, 3, 1), (3, 4, 5)]

2. Kruskal’s Algorithm

Sorts all edges and adds the smallest edge that doesn’t form a cycle. Steps for the same graph:

1. Sort edges: (2-3, 1), (1-2, 2), (1-3, 3), (2-4, 4), (3-4, 5).
2. Add (2-3), (1-2), (1-3) → forms a cycle, skip (1-3).
3. Add (2-4).

Final MST:

Edges: (2-3), (1-2), (2-4)
Total Weight: 7

Shortest Path Algorithms

Dijkstra’s Algorithm

Finds the shortest path from a source to all other vertices in a weighted graph. Example: Find shortest paths from vertex 1 in the graph below.

Steps:

1. Initialize distances: [0, ∞, ∞, ∞].
2. Visit 1 → update distances: [0, 4, 2, ∞].
3. Visit 3 (smallest distance) → update distances: [0, 3, 2, 5].
4. Visit 2 → update distances: [0, 3, 2, 4].
5. Visit 4.

Final Distances:

1: 0, 2: 3, 3: 2, 4: 4

Python Implementation:

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

graph = {
    1: [(2, 4), (3, 2)],
    2: [(1, 4), (3, 1), (4, 5)],
    3: [(1, 2), (2, 1), (4, 3)],
    4: [(2, 5), (3, 3)]
}
print(dijkstra(graph, 1))  # Output: {1: 0, 2: 3, 3: 2, 4: 4}

In the Real World

1. Pathao (Ride-Hailing App):

   • Uses Dijkstra’s algorithm to find the shortest path from the user’s location to the destination, considering traffic and road weights.

2. NTC Bus Routes:

   • Graph representation models bus stops as vertices and routes as edges. BFS/DFS helps optimize schedules and find the shortest path between stops.

3. Facebook Friend Suggestions:

   • Graph traversal (BFS/DFS) identifies common friends or mutual connections to suggest new friends.

4. Nepal Electricity Authority (NEA) Power Grid:

   • Minimum Spanning Tree (Kruskal’s/Prim’s) ensures efficient power distribution with minimal wiring cost.

Exam Tip

• Graph Representations: Know when to use adjacency matrix vs. list (dense vs. sparse graphs).
• Traversals: Practice BFS and DFS on paper; understand their time complexities (O(V + E)).
• MST: Memorize Prim’s (greedy, single-source) vs. Kruskal’s (sort all edges).
• Shortest Path: Dijkstra’s works for non-negative weights; Bellman-Ford handles negative weights (though not in syllabus).
• Applications: Relate graphs to real-world problems (e.g., NTC routes, Pathao paths).

TAKEAWAYS:

• Graphs model relationships in networks, routes, and hierarchies.
• Adjacency matrices are efficient for dense graphs; adjacency lists save space for sparse graphs.
• BFS explores level by level; DFS goes deep first.
• Prim’s and Kruskal’s build MSTs differently but yield the same result.
• Dijkstra’s finds shortest paths in weighted graphs with non-negative edges.