Core Concepts

Topological Sorting Overview

Topological sorting generates a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u \rightarrow v), vertex (u) appears before (v) in the sequence. This is critical for resolving dependency-based ordering problems, such as scheduling tasks where some operations must complete before others can start. For example, if a cloud deployment requires provisioning a server (S) before installing a database (D) and application (A), and the application depends on the database, topological sorting can produce valid sequences like (S \rightarrow D \rightarrow A) or (S \rightarrow A \rightarrow D). In C++, adjacency lists are the preferred structure for representing such graphs due to their space efficiency for sparse datasets.

Directed Acyclic Graphs (DAGs) and AOV Networks

A Activity-On-Vertex (AOV) network is a specialized DAG where each vertex represents a task or activity, and directed edges define prerequisite relationships: an edge from (u) to (v) means activity (u) must finish before (v) can begin. Thece networks model real-world scenarios like project workflows, where cycles are impossible (as they would imply circular dependencies that can never be resolved).

Adjacency List Representation

Adjacency lists are a linked graph storage structure consisting of a vertex list and associated edge lists for each vertex.

Undirected Graph Adjacency List

Each vertex points to a list of its adjacent vertices. For an undirected graph with (n) vertices and (e) edges, the structure contains (n) vertex entries and (2e) edge entries (since each edge connects two vertices). The degree of a vertex equals the length of its edge list.

Directed Graph Adjacency List (Out-Edge Focus)

For directed graphs, each vertex’s edge list only includes vertices it points to (out-edges). This structure uses (n) vertex entries and (e) edge entries. The out-degree of a vertex is the count of entries in its edge list.

Reverse Adjacency List (In-Edge Focus)

A reverse adjacency list tracks in-edges for each vertex, listing all vertices that point to it. This is essential for calculating in-degrees, a key component of Kahn’s topological sorting algorithm. The in-degree of a vertex is the length of its reverse edge list.

Adjacency List Code Implementation

#include <iostream>
using namespace std;

const int MAX_VERTICES = 100;
typedef char VertexData;

struct EdgeNode {
    int targetIndex;
    EdgeNode* nextEdge;
};

struct VertexNode {
    VertexData data;
    EdgeNode* firstEdge;
};

struct AdjacencyListGraph {
    VertexNode vertices[MAX_VERTICES];
    int vertexCount, edgeCount;
};

int findVertexIndex(const AdjacencyListGraph& graph, VertexData val) {
    for (int i = 0; i < graph.vertexCount; ++i) {
        if (graph.vertices[i].data == val) return i;
    }
    return -1;
}

void addDirectedEdge(AdjacencyListGraph& graph, int fromIdx, int toIdx) {
    EdgeNode* newEdge = new EdgeNode();
    newEdge->targetIndex = toIdx;
    newEdge->nextEdge = graph.vertices[fromIdx].firstEdge;
    graph.vertices[fromIdx].firstEdge = newEdge;
}

void printAdjacencyList(const AdjacencyListGraph& graph) {
    cout << "---------- Adjacency List ----------\n";
    for (int i = 0; i < graph.vertexCount; ++i) {
        cout << graph.vertices[i].data << ": ";
        EdgeNode* current = graph.vertices[i].firstEdge;
        while (current != nullptr) {
            cout << "[" << current->targetIndex << "] ";
            current = current->nextEdge;
        }
        cout << endl;
    }
}

void buildDirectedGraph(AdjacencyListGraph& graph) {
    cout << "Enter number of vertices and edges:\n";
    cin >> graph.vertexCount >> graph.edgeCount;
    
    cout << "Enter vertex data:\n";
    for (int i = 0; i < graph.vertexCount; ++i) {
        cin >> graph.vertices[i].data;
        graph.vertices[i].firstEdge = nullptr;
    }
    
    for (int i = 0; i < graph.edgeCount; ) {
        VertexData u, v;
        cout << "Enter edge (u -> v):\n";
        cin >> u >> v;
        
        int fromIdx = findVertexIndex(graph, u);
        int toIdx = findVertexIndex(graph, v);
        
        if (fromIdx != -1 && toIdx != -1) {
            addDirectedEdge(graph, fromIdx, toIdx);
            ++i;
        } else {
            cout << "Invalid vertices entered. Try again.\n";
        }
    }
}

int main() {
    AdjacencyListGraph graph;
    buildDirectedGraph(graph);
    printAdjacencyList(graph);
    return 0;
}

Topological Sorting Implementations

Kahn’s Algorithm (BFS-Based)

Kahn’s algorithm uses a queue to process vertices with zero in-degree, ensuring valid dependency resolution:

1. Initialize a queue with all vertices having no incoming edges (in-degree = 0).
2. While the queue is not empty: a. Dequeue a vertex (u) and add it to the topological order list. b. For each neighbor (v) of (u), decrement (v)’s in-degree by 1. c. If (v)’s in-degree becomes 0, anqueue (v).
3. If the resulting list has fewer vertices than the graph, a cycle exists (topological sort is impossible).

Recursive DFS-Based Approach

This approach uses a stack to collect vertices after completing their DFS traversal:

1. Mark vertices as visited during DFS.
2. After visiting all neighbors of a vertex, push it onto a stack.
3. Pop the stack to retrieve the topological order.

Code Implementations

DFS-Based Topological Sort

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class DAGTopoSorter {
private:
    int vertexCount;
    vector<vector<int>> adjacencyList;
    vector<bool> visited;
    stack<int> topoStack;

    void dfsHelper(int vertex) {
        visited[vertex] = true;
        for (int neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                dfsHelper(neighbor);
            }
        }
        topoStack.push(vertex);
    }

public:
    DAGTopoSorter(int count) : vertexCount(count), adjacencyList(count), visited(count, false) {}

    void addDirectedEdge(int from, int to) {
        adjacencyList[from].push_back(to);
    }

    void performTopologicalSort() {
        for (int i = 0; i < vertexCount; ++i) {
            if (!visited[i]) {
                dfsHelper(i);
            }
        }

        cout << "Topological Order (DFS-based):\n";
        while (!topoStack.empty()) {
            cout << topoStack.top() << " ";
            topoStack.pop();
        }
        cout << endl;
    }
};

int main() {
    DAGTopoSorter sorter(6);
    sorter.addDirectedEdge(5, 2);
    sorter.addDirectedEdge(5, 0);
    sorter.addDirectedEdge(4, 0);
    sorter.addDirectedEdge(4, 1);
    sorter.addDirectedEdge(2, 3);
    sorter.addDirectedEdge(3, 1);
    
    sorter.performTopologicalSort();
    return 0;
}

Kahn’s Algorithm with Lexicographical Order Priority Queue

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;

const int MAX_NODES = 2005;

inline int readInt() {
    int x = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * sign;
}

int main() {
    int testCases = readInt();
    while (testCases--) {
        int nodeCount = readInt();
        int edgeCount = readInt();
        
        vector<int> adj[MAX_NODES];
        int inDegree[MAX_NODES] = {0};
        vector<int> topoOrder;
        
        for (int i = 0; i < edgeCount; ++i) {
            int u = readInt();
            int v = readInt();
            adj[u].push_back(v);
            inDegree[v]++;
        }
        
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (int i = 1; i <= nodeCount; ++i) {
            if (inDegree[i] == 0) {
                minHeap.push(i);
            }
        }
        
        while (!minHeap.empty()) {
            int current = minHeap.top();
            minHeap.pop();
            topoOrder.push_back(current);
            
            for (int neighbor : adj[current]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    minHeap.push(neighbor);
                }
            }
        }
        
        for (size_t i = 0; i < topoOrder.size(); ++i) {
            if (i > 0) printf(" ");
            printf("%d", topoOrder[i]);
        }
        printf("\n");
    }
    return 0;
}