Chapter 22 – Advanced Graph Algorithms

Chapter 22: Advanced Graph Algorithms

In this chapter, we delve deeper into Advanced Graph Algorithms that are essential for solving complex problems related to graph traversal, connectivity, and more. These algorithms are foundational in many computer science applications, from navigating networks to solving puzzles and finding connected components.

We will explore the following topics:

1. Depth-First Search (DFS)
2. Breadth-First Search (BFS)
3. Topological Sorting
4. Strongly Connected Components (Kosaraju’s Algorithm)

---

22.1 Depth-First Search (DFS)

Depth-First Search (DFS) is a fundamental algorithm used to explore all the vertices and edges of a graph. DFS explores as far as possible along each branch before backtracking, which makes it useful for tasks like detecting cycles or solving maze-like problems.

Problem Definition:

Given a graph, perform DFS traversal from a starting vertex, visiting each vertex once.

DFS Algorithm Steps:

1. Start at a given vertex and mark it as visited.
2. For each unvisited neighbor, recursively perform DFS.
3. If all neighbors are visited, backtrack to the previous vertex.

DFS Algorithm (in C):

#include <stdio.h>
#include <stdbool.h>

#define V 5

void DFSUtil(int graph[V][V], int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", v);

    for (int i = 0; i < V; i++) {
        if (graph[v][i] == 1 && !visited[i]) {
            DFSUtil(graph, i, visited);
        }
    }
}

void DFS(int graph[V][V], int startVertex) {
    bool visited[V] = {false};

    DFSUtil(graph, startVertex, visited);
}

int main() {
    int graph[V][V] = {
        {0, 1, 0, 0, 1},
        {1, 0, 1, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0}
    };

    printf("DFS starting from vertex 0:\n");
    DFS(graph, 0);

    return 0;
}

Explanation:

• The graph is represented as an adjacency matrix.
• The DFSUtil() function recursively visits each vertex and its adjacent vertices.
• visited[] keeps track of the vertices that have already been explored to avoid revisiting.

Time Complexity:

The time complexity of DFS is O(V²) for an adjacency matrix representation and O(V + E) for an adjacency list, where V is the number of vertices and E is the number of edges.

---

22.2 Breadth-First Search (BFS)

Breadth-First Search (BFS) is another fundamental graph traversal algorithm that explores the vertices level by level. BFS is often used to find the shortest path in unweighted graphs and in applications such as solving puzzles or network broadcasting.

BFS Algorithm Steps:

1. Start from a given vertex and mark it as visited.
2. Visit all the adjacent vertices of the current vertex.
3. Repeat for each vertex, visiting the vertices in a breadth-first manner.

BFS Algorithm (in C):

#include <stdio.h>
#include <stdbool.h>

#define V 5

void BFS(int graph[V][V], int startVertex) {
    bool visited[V] = {false};
    int queue[V], front = 0, rear = 0;

    visited[startVertex] = true;
    queue[rear++] = startVertex;

    while (front != rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        for (int i = 0; i < V; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 0, 0, 1},
        {1, 0, 1, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0}
    };

    printf("BFS starting from vertex 0:\n");
    BFS(graph, 0);

    return 0;
}

Explanation:

• The graph is represented as an adjacency matrix.
• The queue[] is used to maintain the vertices that need to be explored.
• The visited[] array keeps track of the visited vertices.

Time Complexity:

The time complexity of BFS is O(V²) for an adjacency matrix representation and O(V + E) for an adjacency list.

---

22.3 Topological Sorting

Topological Sorting is an ordering of vertices in a Directed Acyclic Graph (DAG) where, for every directed edge (u, v), vertex u comes before vertex v. It is widely used in scheduling problems where some tasks must precede others.

Topological Sort Algorithm (DFS-based):

1. Perform DFS on the graph.
2. Push the vertices onto a stack when DFS finishes visiting all vertices from that vertex.
3. Pop all vertices from the stack to get the topological order.

Topological Sort Algorithm (in C):

#include <stdio.h>
#include <stdbool.h>

#define V 6

void topologicalSortUtil(int graph[V][V], int v, bool visited[], int stack[], int *index) {
    visited[v] = true;

    for (int i = 0; i < V; i++) {
        if (graph[v][i] == 1 && !visited[i]) {
            topologicalSortUtil(graph, i, visited, stack, index);
        }
    }
    stack[(*index)--] = v;
}

void topologicalSort(int graph[V][V]) {
    bool visited[V] = {false};
    int stack[V], index = V - 1;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSortUtil(graph, i, visited, stack, &index);
        }
    }

    printf("Topological Sort:\n");
    for (int i = 0; i < V; i++) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    topologicalSort(graph);
    return 0;
}

Explanation:

• The graph is represented as an adjacency matrix.
• The vertices are stored in the stack in a topologically sorted order.
• The algorithm makes use of DFS to ensure that all dependencies are visited before the vertex itself.

Time Complexity:

The time complexity of Topological Sort is O(V²) for an adjacency matrix and O(V + E) for an adjacency list.

---

22.4 Strongly Connected Components (Kosaraju’s Algorithm)

In directed graphs, a Strongly Connected Component (SCC) is a maximal subgraph where every vertex is reachable from every other vertex in the subgraph. Kosaraju’s Algorithm is an efficient method to find SCCs in a directed graph.

Kosaraju’s Algorithm Steps:

1. Perform DFS on the original graph and push the vertices onto a stack based on their finish times.
2. Reverse the graph.
3. Perform DFS again, using the vertices in the order defined by the stack.

Kosaraju’s Algorithm (in C):

#include <stdio.h>
#include <stdbool.h>

#define V 5

void DFSUtil(int graph[V][V], int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", v);
    for (int i = 0; i < V; i++) {
        if (graph[v][i] == 1 && !visited[i]) {
            DFSUtil(graph, i, visited);
        }
    }
}

void fillOrder(int graph[V][V], int v, bool visited[], int stack[], int *index) {
    visited[v] = true;

    for (int i = 0; i < V; i++) {
        if (graph[v][i] == 1 && !visited[i]) {
            fillOrder(graph, i, visited, stack, index);
        }
    }
    stack[(*index)--] = v;
}

void transposeGraph(int graph[V][V], int transpose[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            transpose[i][j]

 = graph[j][i];
        }
    }
}

void KosarajuSCC(int graph[V][V]) {
    bool visited[V] = {false};
    int stack[V], index = V - 1;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            fillOrder(graph, i, visited, stack, &index);
        }
    }

    int transpose[V][V];
    transposeGraph(graph, transpose);

    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    printf("Strongly Connected Components:\n");
    for (int i = 0; i < V; i++) {
        int v = stack[i];
        if (!visited[v]) {
            DFSUtil(transpose, v, visited);
            printf("\n");
        }
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {1, 0, 0, 1, 0},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0}
    };

    KosarajuSCC(graph);
    return 0;
}

Explanation:

• The graph is first traversed using DFS, and vertices are pushed onto a stack based on their finishing times.
• The graph is then transposed, and another DFS is performed to discover the strongly connected components.

Time Complexity:

The time complexity of Kosaraju’s Algorithm is O(V²) for an adjacency matrix and O(V + E) for an adjacency list.

---

Wrapping Up Advanced Graph Algorithms

In this chapter, we covered:

• DFS and BFS, two essential algorithms for graph traversal.
• Topological Sorting, a method for ordering tasks or events with dependencies.
• Kosaraju’s Algorithm, a method for finding strongly connected components in a graph.

These advanced graph algorithms are fundamental for solving complex problems related to networks, dependencies, and connectedness.

---

Next Up: Chapter 23: Advanced Dynamic Programming