Unit 6: Graphs

1. Graph Traversal

Graph traversal refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited.

A. Breadth-First Search (BFS)

BFS is an algorithm for traversing or searching tree or graph data structures. It starts at a selected node (source) and explores all of its neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Key Characteristics:

• Strategy: Level-order traversal.
• Data Structure Used: Queue (FIFO - First In, First Out).
• Application: Finding the shortest path in unweighted graphs, peer-to-peer networks, garbage collection (Cheney's algorithm).

Algorithm Steps:

1. Initialize a boolean array visited[] to keep track of visited vertices.
2. Create a Queue and enqueue the starting vertex. Mark it as visited.
3. While the queue is not empty:
   • Dequeue a vertex u from the queue.
   • Process u (e.g., print it).
   • For every adjacent vertex v of u:
     • If v has not been visited, mark it as visited and enqueue it.

Pseudocode:

BFS(Graph, start_node):
    create a queue Q
    mark start_node as visited
    Q.enqueue(start_node)

    while Q is not empty:
        u = Q.dequeue()
        print(u)

        for each neighbor v of u:
            if v is not visited:
                mark v as visited
                Q.enqueue(v)

Complexity Analysis:

• Time Complexity: , where is the number of vertices and is the number of edges.
• Space Complexity: (for the queue and visited array).

B. Depth-First Search (DFS)

DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Key Characteristics:

• Strategy: Deep exploration (depth-ward motion).
• Data Structure Used: Stack (LIFO - Last In, First Out) or Recursion (Call Stack).
• Application: Cycle detection, Topological sorting, Solving mazes, Finding connected components.

Algorithm Steps:

1. Initialize a boolean array visited[].
2. Push the starting vertex onto the stack (or call the recursive function).
3. Mark the current node as visited.
4. For every adjacent vertex v of the current node:
   • If v is not visited, recursively call DFS on v.

Pseudocode (Recursive):

DFS(Graph, u, visited):
    mark u as visited
    print(u)

    for each neighbor v of u:
        if v is not visited:
            DFS(Graph, v, visited)

# Wrapper function
DFS_Start(Graph):
    create visited array initialized to False
    for each vertex i in Graph:
        if not visited[i]:
            DFS(Graph, i, visited)

Complexity Analysis:

• Time Complexity: .
• Space Complexity: (for the recursion stack in the worst case, e.g., a skewed graph).

2. Shortest Path Algorithms

These algorithms are designed to find a path between two vertices (or from a source to all other vertices) such that the sum of the weights of its constituent edges is minimized.

A. Dijkstra’s Algorithm

Dijkstra's algorithm solves the Single-Source Shortest Path (SSSP) problem for graphs with non-negative edge weights.

Key Concepts:

• Approach: Greedy Algorithm.
• Relaxation: The process of updating the cost to reach a vertex v via vertex u. If distance[u] + weight(u, v) < distance[v], then distance[v] is updated.
• Data Structure: Min-Priority Queue (Min-Heap).

Algorithm Steps:

1. Initialize distances of all vertices as infinite (), except the source vertex, which is 0.
2. Insert the source vertex into a Min-Priority Queue.
3. While the Priority Queue is not empty:
   • Extract the vertex u with the minimum distance value.
   • For every adjacent vertex v of u:
     • Perform Relaxation: If dist[u] + weight(u,v) < dist[v]:
       • Update dist[v] = dist[u] + weight(u,v)
       • Update priority of v in the Priority Queue (or insert if not present).

Pseudocode:

Dijkstra(Graph, source):
    dist[] = {infinity, infinity, ...}
    dist[source] = 0
    PriorityQueue PQ
    PQ.add(source, 0)

    while PQ is not empty:
        u = PQ.extract_min()

        for each neighbor v of u with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                PQ.update(v, dist[v])

Complexity Analysis:

• Time Complexity: using a Binary Heap (Adjacency List). using an Array (Adjacency Matrix).
• Space Complexity: .

B. Bellman-Ford Algorithm

The Bellman-Ford algorithm solves the Single-Source Shortest Path (SSSP) problem. Unlike Dijkstra's, it can handle graphs with negative edge weights.

Key Concepts:

• Approach: Dynamic Programming.
• Negative Cycles: It can detect negative weight cycles. If a negative cycle exists, the shortest path is undefined (can be infinitely small).
• Principle: If a graph contains vertices, the shortest path between any two vertices can contain at most edges.

Algorithm Steps:

1. Initialize distances of all vertices as infinite (), except the source vertex (0).
2. Relaxation Loop: Repeat times:
   • For every edge with weight in the graph:
     • If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
3. Negative Cycle Check: Iterate over all edges one more time.
   • If dist[u] + w < dist[v] is still true for any edge, a negative weight cycle exists.

Pseudocode:

BellmanFord(Graph, source, V, E):
    dist[] = {infinity, ...}
    dist[source] = 0

    # Step 1: Relax all edges V-1 times
    for i from 1 to V-1:
        for each edge (u, v) with weight w:
            if dist[u] != infinity and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Step 2: Check for negative cycles
    for each edge (u, v) with weight w:
        if dist[u] != infinity and dist[u] + w < dist[v]:
            return "Negative Cycle Detected"
            
    return dist

Complexity Analysis:

• Time Complexity: .
• Space Complexity: .

C. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm solves the All-Pairs Shortest Path (APSP) problem. It finds the shortest paths between every pair of vertices in a given edge-weighted directed Graph.

Key Concepts:

• Approach: Dynamic Programming.
• Handling Weights: Works with positive and negative weights, but fails if there are negative cycles.
• Matrix Representation: Uses a 2D matrix dist[][] where dist[i][j] represents the shortest distance from vertex i to j.

Algorithm Logic:
The algorithm considers a set of intermediate vertices .
For every pair , we check if traveling through vertex offers a shorter path than the current known path.
The recurrence relation is:

Algorithm Steps:

1. Initialize a solution matrix dist[V][V] same as the input adjacency matrix.
   • If there is no edge between i and j, dist[i][j] = \infty.
   • Diagonal elements dist[i][i] = 0.
2. Create three nested loops:
   • Outer loop k from 0 to (considering each vertex as an intermediate).
   • Middle loop i from 0 to (source).
   • Inner loop j from 0 to (destination).
3. Update dist[i][j] using the recurrence relation.

Pseudocode:

FloydWarshall(Graph, V):
    # Initialize result matrix with input graph weights
    dist = Graph 

    for k from 0 to V-1:           # Intermediate node
        for i from 0 to V-1:       # Source node
            for j from 0 to V-1:   # Destination node
                
                # If vertex k is on the shortest path from i to j
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    
    return dist

Complexity Analysis:

• Time Complexity: .
• Space Complexity: (to store the 2D matrix).

Summary Comparison Table