Topological Sorting

Definition

Definition

Topological sorting is a linear ordering of vertices in a directed graph such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering

Explanation

Repeatedly select a vertex with no incoming edges (in-degree of 0), adding it to the topological order, and removing it along with its outgoing edges. This process continues until all vertices are included in the topological order or until no vertex with zero in-degree is found

Guidance

• Initialize an empty list to store the topological order
• Compute the in-degree of each vertex in the graph
• Enqueue all vertices with an in-degree of 0 into a queue
• While the queue is not empty
  • Dequeue a vertex u from the queue
  • Add u to the topological order list
  • For each neighbor v of u, decrement the in-degree of v
  • If the in-degree of v becomes 0, enqueue v into the queue
• If the topological order list's length is equal to the number of vertices, return the list as the topological order. Otherwise, the graph has a cycle

Tips

• ensure the graph is directed before applying the algorithm
• handle cases where the graph may contain cycles
• use data structures like queues to efficiently track vertices with zero in-degree

Practice

Practice

topologicalSort(graph):
  inDegree[] // array to store in-degree of vertices
  queue // queue to store vertices with in-degree 0
  topologicalOrder[] // list to store topological order

  // Initialize in-degree array and queue
  for each vertex v in graph:
    inDegree[v] = 0
  for each edge (u, v) in graph:
    inDegree[v]++
    if inDegree[v] == 0:
      queue.enqueue(v)

  // Perform topological sort
  while queue is not empty:
    u = queue.dequeue()
    topologicalOrder.append(u)
    for each neighbor v of u in graph:
      inDegree[v]--
      if inDegree[v] == 0:
        queue.enqueue(v)

  // Check for cycles
  if size of topologicalOrder != number of vertices:
    return "Graph has a cycle"

  return topologicalOrder

Solution

package main

type Graph struct {
	vertices  int
	adjacency map[int][]int
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices:  vertices,
		adjacency: make(map[int][]int),
	}
}

func (g *Graph) AddEdge(u, v int) {
	g.adjacency[u] = append(g.adjacency[u], v)
}

func (g *Graph) topologicalSortUtil(vertex int, visited map[int]bool, stack *[]int) {
	visited[vertex] = true
	for _, v := range g.adjacency[vertex] {
		if !visited[v] {
			g.topologicalSortUtil(v, visited, stack)
		}
	}
	*stack = append(*stack, vertex)
}

func (g *Graph) TopologicalSort() []int {
	stack := make([]int, 0)
	visited := make(map[int]bool)

	for i := 0; i < g.vertices; i++ {
		if !visited[i] {
			g.topologicalSortUtil(i, visited, &stack)
		}
	}

	result := make([]int, g.vertices)
	for i := 0; i < g.vertices; i++ {
		result[i] = stack[g.vertices-i-1]
	}
	return result
}

import java.util.*;

class Graph {

  private int vertices;
  private Map<Integer, List<Integer>> adjacency;

  public Graph(int vertices) {
    this.vertices = vertices;
    adjacency = new HashMap<>();
    for (int i = 0; i < vertices; i++) {
      adjacency.put(i, new ArrayList<>());
    }
  }

  public void addEdge(int u, int v) {
    adjacency.get(u).add(v);
  }

  private void topologicalSortUtil(int vertex, boolean[] visited, Stack<Integer> stack) {
    visited[vertex] = true;
    for (int v : adjacency.get(vertex)) {
      if (!visited[v]) {
        topologicalSortUtil(v, visited, stack);
      }
    }
    stack.push(vertex);
  }

  public List<Integer> topologicalSort() {
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[vertices];

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

    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) {
      result.add(stack.pop());
    }
    return result;
  }
}

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.adjacency = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjacency.set(i, []);
    }
  }

  addEdge(u, v) {
    this.adjacency.get(u).push(v);
  }

  topologicalSortUtil(vertex, visited, stack) {
    visited[vertex] = true;
    for (const v of this.adjacency.get(vertex)) {
      if (!visited[v]) {
        this.topologicalSortUtil(v, visited, stack);
      }
    }
    stack.push(vertex);
  }

  topologicalSort() {
    const stack = [];
    const visited = new Array(this.vertices).fill(false);

    for (let i = 0; i < this.vertices; i++) {
      if (!visited[i]) {
        this.topologicalSortUtil(i, visited, stack);
      }
    }

    return stack.reverse();
  }
}

import java.util.*

class Graph(private val vertices: Int) {
    private val adjacency: MutableMap<Int, MutableList<Int>> = HashMap()

    init {
        for (i in 0 until vertices) {
            adjacency[i] = ArrayList()
        }
    }

    fun addEdge(u: Int, v: Int) {
        adjacency[u]?.add(v)
    }

    private fun topologicalSortUtil(vertex: Int, visited: BooleanArray, stack: Stack<Int>) {
        visited[vertex] = true
        adjacency[vertex]?.forEach { v ->
            if (!visited[v]) {
                topologicalSortUtil(v, visited, stack)
            }
        }
        stack.push(vertex)
    }

    fun topologicalSort(): List<Int> {
        val stack = Stack<Int>()
        val visited = BooleanArray(vertices)

        for (i in 0 until vertices) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack)
            }
        }

        return stack.toList().reversed()
    }
}

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjacency = defaultdict(list)

    def add_edge(self, u, v):
        self.adjacency[u].append(v)

    def topological_sort_util(self, vertex, visited, stack):
        visited[vertex] = True
        for v in self.adjacency[vertex]:
            if not visited[v]:
                self.topological_sort_util(v, visited, stack)
        stack.append(vertex)

    def topological_sort(self):
        visited = [False] * self.vertices
        stack = []

        for i in range(self.vertices):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)

        return stack[::-1]

use std::collections::{HashMap, HashSet};

struct Graph {
    vertices: usize,
    adjacency: HashMap<usize, Vec<usize>>,
}

impl Graph {
    fn new(vertices: usize) -> Self {
        let mut adjacency = HashMap::new();
        for i in 0..vertices {
            adjacency.insert(i, Vec::new());
        }
        Graph {
            vertices,
            adjacency,
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.adjacency.get_mut(&u).unwrap().push(v);
    }

    fn topological_sort_util(&self, vertex: usize, visited: &mut HashSet<usize>, stack: &mut Vec<usize>) {
        visited.insert(vertex);
        for &v in &self.adjacency[&vertex] {
            if !visited.contains(&v) {
                self.topological_sort_util(v, visited, stack);
            }
        }
        stack.push(vertex);
    }

    fn topological_sort(&self) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut stack = Vec::new();

        for i in 0..self.vertices {
            if !visited.contains(&i) {
                self.topological_sort_util(i, &mut visited, &mut stack);
            }
        }

        stack.into_iter().rev().collect()
    }
}

class Graph {
  vertices: number;
  adjacency: Map<number, number[]>;

  constructor(vertices: number) {
    this.vertices = vertices;
    this.adjacency = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjacency.set(i, []);
    }
  }

  addEdge(u: number, v: number): void {
    this.adjacency.get(u)?.push(v);
  }

  topologicalSort(): number[] {
    const stack: number[] = [];
    const visited: boolean[] = new Array(this.vertices).fill(false);

    for (let i = 0; i < this.vertices; i++) {
      if (!visited[i]) {
        this.topologicalSortUtil(i, visited, stack);
      }
    }

    return stack.reverse();
  }

  private topologicalSortUtil(
    vertex: number,
    visited: boolean[],
    stack: number[],
  ): void {
    visited[vertex] = true;
    for (const v of this.adjacency.get(vertex)!) {
      if (!visited[v]) {
        this.topologicalSortUtil(v, visited, stack);
      }
    }
    stack.push(vertex);
  }
}