Directed Acyclic Graph (DAG)¶

Theorem 3.3.2¶

Statement: If \(G\) is a directed acyclic graph (DAG), then the vertices of \(G\) can be ordered as \(v_{1}, v_{2}, ..., v_{n}\) such that if the edge \((v_{i}, v_{j})\) exists in the graph, then \(i < j\). (See Figure 1 and Figure 2. Figure 2 shows a vertex ordering for the graph in Figure 1.)

Proof: We prove this theorem using induction. The base case is \(n = 1\), where the graph has a single vertex. The statement trivially holds here.

By Theorem 3.1.2 (proven in our earlier definitions of graphs), \(G\) contains a vertex with in-degree \(0\) (since if all vertices had an in-degree of at least 1, the graph would contain a cycle, contradicting the assumption).

Let \(d^{-}(x) = 0\). Place vertex \(x\) at position \(v_{1}\) and remove it from the graph (along with all its connected edges).

Since the original graph had no cycles, removing \(x\) will not create any cycles, preserving the induction hypothesis. By induction, the remaining graph can be ordered as \(v_{2}, v_{3}, ..., v_{n}\) to satisfy the condition. We append this ordering after \(v_{1} = x\).

We now verify that this ordering satisfies the theorem’s condition. For vertices \(v_{2}, v_{3}, ..., v_{n}\), the condition holds by the induction hypothesis. For \(v_{1}\), the condition is also satisfied because \(v_{1}\) has no incoming edges. Thus, the theorem is proven.

Note: An intuitive interpretation of this theorem is that the vertices of a DAG can be arranged in a linear order such that all edges point in the same direction (e.g., left to right or right to left). This ordering is called a topological sort or topological order!

Algorithm¶

A common algorithm for topological sorting is based on depth-first search (DFS). The steps are as follows:

1. Perform DFS traversal of the graph

2. After visiting all neighbors of a vertex, add it to a stack

3. The final topological order is the reverse of the stack

Example implementation in Python:

def topological_sort(graph):
    # Function for topological sort using DFS
    visited = set()
    stack = []

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph[node]:  # barresi hame hamsayaha
            dfs(neighbor)
        stack.append(node)  # ezafe kardan be stack bad az bazgasht

    for node in graph:
        dfs(node)

    return stack[::-1]  # baraks kardane stack baraye daryafte tartib

Topological Sorting Algorithm¶

This algorithm is the same as the \(DFS\) algorithm. Simply, when finishing the traversal of a vertex, we push it onto a stack (here, to improve the program's speed, we did not use a stack. It is recommended to minimize stack usage).

Suppose the order provided by the algorithm is as follows: \(v_{1}, v_{2}, ..., v_{n}\). Consider the following lemma:

Lemma 1: When we place a vertex \(x\) in the array, all vertices reachable from \(x\) (i.e., all vertices \(v\) such that there is a path from \(x\) to \(v\)) must have already been traversed and placed in the array! (Why?)

To prove the above algorithm, we use proof by contradiction and Lemma 1. Assume the order we obtained is not valid. That is, there exist \(i < j\) such that the edge \((v_{i}, v_{j})\) belongs to the graph (i.e., an edge from left to right).

But this is impossible! Because when \(v_{i}\) is placed in the array, according to Lemma 1, all vertices reachable from \(v_{i}\) must have already been placed in the array. However, there is an edge (and trivially a path) from \(v_{i}\) to \(v_{j}\), yet \(v_{j}\) has not been placed in the array! This contradicts Lemma 1. Therefore, the assumption is false, and such \(i, j\) cannot exist!

Algorithm Complexity¶

The complexity of the above algorithm is the same as the complexity of the \(DFS\) algorithm, i.e., \(O(n + m)\), where \(m, n\) are the number of vertices and edges, respectively.

The following code reads a graph as input and stores it using an adjacency matrix:

 1n = int(input())  # Get number of vertices
 2m = int(input())  # Get number of edges
 3
 4# Create (n+1)*(n+1) adjacency matrix initialized with 0
 5adjacency_matrix = [[0]*(n+1) for _ in range(n+1)]
 6
 7for _ in range(m):
 8    u = int(input())  # Enter edge from vertex
 9    v = int(input())  # Enter edge to vertex
10    adjacency_matrix[u][v] = 1
11    adjacency_matrix[v][u] = 1  # Undirected graph

The adjacency matrix representation is visualized below:

#include<bits/stdc++.h>

using namespace std;

const int MX = 5e5 + 5;

int n, m; /// Tedad ra's ha va yal ha
vector<int> gr[MX]; /// vector mojaverat
vector<int> topologic; /// topological sort
bool mark[MX];

void dfs(int v){
    mark[v] = 1;
    for(int u: gr[v]){
        if(!mark[u])
            dfs(u);
    }
    topologic.push_back(v); // in array yek topological sort baraie DAG ast!
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
                int v, u;
                cin >> v >> u; // Ra's ha 0-based hastand!
                gr[v].push_back(u);
    }
    // Graph vorodi bayad DAG bashad!
    for(int i = 0; i < n; i++)
                if(!mark[i])
                   dfs(i);
    // topological sort ro khoroji midahim!
    for(int i = 0; i < topologic.size(); i++)
          cout << topologic[i] << ' ';
    cout << endl;
    return 0;
}