AntInLoop

Topological Sort Algorithm Code Implementations

Complete Topological Sort Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Topological Sort Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// Topological Sort Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>

class TopologicalSort {
public:
    static std::vector<int> topologicalSort(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::unordered_set<int> recStack;
        std::vector<int> result;
        bool hasCycle = false;
        
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                dfs(graph, node, visited, recStack, result, hasCycle);
            }
        }
        
        return hasCycle ? std::vector<int>{} : result;
    }
    
private:
    static void dfs(const std::unordered_map<int, std::vector<int>>& graph, int node,
                   std::unordered_set<int>& visited, std::unordered_set<int>& recStack,
                   std::vector<int>& result, bool& hasCycle) {
        if (hasCycle) return;
        
        visited.insert(node);
        recStack.insert(node);
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    dfs(graph, neighbor, visited, recStack, result, hasCycle);
                } else if (recStack.find(neighbor) != recStack.end()) {
                    hasCycle = true;
                }
            }
        }
        
        recStack.erase(node);
        result.insert(result.begin(), node);
    }
    
public:
    // Topological Sort using Kahn's Algorithm (BFS approach)
    static std::vector<int> topologicalSortKahn(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_map<int, int> inDegree;
        std::queue<int> queue;
        std::vector<int> result;
        
        // Calculate in-degrees
        for (const auto& [node, neighbors] : graph) {
            inDegree[node] = 0;
        }
        
        for (const auto& [node, neighbors] : graph) {
            for (int neighbor : neighbors) {
                inDegree[neighbor]++;
            }
        }
        
        // Add nodes with in-degree 0 to queue
        for (const auto& [node, degree] : inDegree) {
            if (degree == 0) {
                queue.push(node);
            }
        }
        
        // Process queue
        while (!queue.empty()) {
            int current = queue.front();
            queue.pop();
            result.push_back(current);
            
            auto it = graph.find(current);
            if (it != graph.end()) {
                for (int neighbor : it->second) {
                    inDegree[neighbor]--;
                    if (inDegree[neighbor] == 0) {
                        queue.push(neighbor);
                    }
                }
            }
        }
        
        // Check if all nodes were processed
        return result.size() == graph.size() ? result : std::vector<int>{};
    }
    
    // Topological Sort with cycle detection
    static std::pair<bool, std::vector<int>> topologicalSortWithCycleDetection(const std::unordered_map<int, std::vector<int>>& graph) {
        std::unordered_set<int> visited;
        std::unordered_set<int> recStack;
        std::vector<int> result;
        std::vector<int> cycle;
        
        for (const auto& [node, neighbors] : graph) {
            if (visited.find(node) == visited.end()) {
                if (dfsWithCycle(graph, node, visited, recStack, result, cycle, {})) {
                    return {true, cycle};
                }
            }
        }
        
        return {false, result};
    }
    
private:
    static bool dfsWithCycle(const std::unordered_map<int, std::vector<int>>& graph, int node,
                           std::unordered_set<int>& visited, std::unordered_set<int>& recStack,
                           std::vector<int>& result, std::vector<int>& cycle, std::vector<int> path) {
        if (recStack.find(node) != recStack.end()) {
            // Found a cycle
            auto cycleStart = std::find(path.begin(), path.end(), node);
            cycle.assign(cycleStart, path.end());
            return true;
        }
        
        if (visited.find(node) != visited.end()) return false;
        
        visited.insert(node);
        recStack.insert(node);
        path.push_back(node);
        
        auto it = graph.find(node);
        if (it != graph.end()) {
            for (int neighbor : it->second) {
                if (dfsWithCycle(graph, neighbor, visited, recStack, result, cycle, path)) {
                    return true;
                }
            }
        }
        
        recStack.erase(node);
        path.pop_back();
        result.insert(result.begin(), node);
        return false;
    }
};

JAVA Implementation

// Topological Sort Implementation in Java
import java.util.*;

public class TopologicalSort {
    public static List<Integer> topologicalSort(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        boolean[] hasCycle = {false};
        
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs(graph, node, visited, recStack, result, hasCycle);
            }
        }
        
        return hasCycle[0] ? null : result;
    }
    
    private static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited,
                           Set<Integer> recStack, List<Integer> result, boolean[] hasCycle) {
        if (hasCycle[0]) return;
        
        visited.add(node);
        recStack.add(node);
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, recStack, result, hasCycle);
            } else if (recStack.contains(neighbor)) {
                hasCycle[0] = true;
            }
        }
        
        recStack.remove(node);
        result.add(0, node);
    }
    
    // Topological Sort using Kahn's Algorithm (BFS approach)
    public static List<Integer> topologicalSortKahn(Map<Integer, List<Integer>> graph) {
        Map<Integer, Integer> inDegree = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        
        // Calculate in-degrees
        for (int node : graph.keySet()) {
            inDegree.put(node, 0);
        }
        
        for (int node : graph.keySet()) {
            List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
            for (int neighbor : neighbors) {
                inDegree.put(neighbor, inDegree.getOrDefault(neighbor, 0) + 1);
            }
        }
        
        // Add nodes with in-degree 0 to queue
        for (int node : inDegree.keySet()) {
            if (inDegree.get(node) == 0) {
                queue.offer(node);
            }
        }
        
        // Process queue
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            
            List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
            for (int neighbor : neighbors) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // Check if all nodes were processed
        return result.size() == graph.size() ? result : null;
    }
    
    // Topological Sort with cycle detection
    public static Map<String, Object> topologicalSortWithCycleDetection(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        List<Integer> cycle = new ArrayList<>();
        
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                if (dfsWithCycle(graph, node, visited, recStack, result, cycle, new ArrayList<>())) {
                    Map<String, Object> response = new HashMap<>();
                    response.put("hasCycle", true);
                    response.put("cycle", cycle);
                    return response;
                }
            }
        }
        
        Map<String, Object> response = new HashMap<>();
        response.put("hasCycle", false);
        response.put("result", result);
        return response;
    }
    
    private static boolean dfsWithCycle(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited,
                                      Set<Integer> recStack, List<Integer> result, List<Integer> cycle, List<Integer> path) {
        if (recStack.contains(node)) {
            // Found a cycle
            int cycleStart = path.indexOf(node);
            cycle.addAll(path.subList(cycleStart, path.size()));
            return true;
        }
        
        if (visited.contains(node)) return false;
        
        visited.add(node);
        recStack.add(node);
        path.add(node);
        
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (dfsWithCycle(graph, neighbor, visited, recStack, result, cycle, path)) {
                return true;
            }
        }
        
        recStack.remove(node);
        path.remove(path.size() - 1);
        result.add(0, node);
        return false;
    }
}

JAVASCRIPT Implementation

// Topological Sort Implementation in JavaScript
function topologicalSort(graph) {
  const visited = new Set();
  const recStack = new Set();
  const result = [];
  const hasCycle = { value: false };
  
  function dfs(node) {
    if (hasCycle.value) return;
    
    visited.add(node);
    recStack.add(node);
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      } else if (recStack.has(neighbor)) {
        hasCycle.value = true;
      }
    }
    
    recStack.delete(node);
    result.unshift(node);
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return hasCycle.value ? null : result;
}

// Topological Sort using Kahn's Algorithm (BFS approach)
function topologicalSortKahn(graph) {
  const inDegree = {};
  const queue = [];
  const result = [];
  
  // Calculate in-degrees
  for (const node in graph) {
    inDegree[node] = 0;
  }
  
  for (const node in graph) {
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    }
  }
  
  // Add nodes with in-degree 0 to queue
  for (const node in inDegree) {
    if (inDegree[node] === 0) {
      queue.push(node);
    }
  }
  
  // Process queue
  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);
    
    const neighbors = graph[current] || [];
    for (const neighbor of neighbors) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
  
  // Check if all nodes were processed
  return result.length === Object.keys(graph).length ? result : null;
}

// Topological Sort with cycle detection
function topologicalSortWithCycleDetection(graph) {
  const visited = new Set();
  const recStack = new Set();
  const result = [];
  const cycle = [];
  
  function dfs(node, path) {
    if (recStack.has(node)) {
      // Found a cycle
      const cycleStart = path.indexOf(node);
      cycle.push(...path.slice(cycleStart));
      return true;
    }
    
    if (visited.has(node)) return false;
    
    visited.add(node);
    recStack.add(node);
    path.push(node);
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (dfs(neighbor, path)) return true;
    }
    
    recStack.delete(node);
    path.pop();
    result.unshift(node);
    return false;
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, [])) {
        return { hasCycle: true, cycle };
      }
    }
  }
  
  return { hasCycle: false, result };
}

// Topological Sort for multiple components
function topologicalSortMultiple(graph) {
  const visited = new Set();
  const result = [];
  
  function dfs(node) {
    visited.add(node);
    
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
    
    result.unshift(node);
  }
  
  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return result;
}

PYTHON Implementation

# Topological Sort Implementation in Python
def topological_sort(graph):
    visited = set()
    rec_stack = set()
    result = []
    has_cycle = [False]
    
    def dfs(node):
        if has_cycle[0]:
            return
        
        visited.add(node)
        rec_stack.add(node)
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs(neighbor)
            elif neighbor in rec_stack:
                has_cycle[0] = True
        
        rec_stack.remove(node)
        result.insert(0, node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return None if has_cycle[0] else result

# Topological Sort using Kahn's Algorithm (BFS approach)
def topological_sort_kahn(graph):
    in_degree = {}
    queue = []
    result = []
    
    # Calculate in-degrees
    for node in graph:
        in_degree[node] = 0
    
    for node in graph:
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
    
    # Add nodes with in-degree 0 to queue
    for node in in_degree:
        if in_degree[node] == 0:
            queue.append(node)
    
    # Process queue
    while queue:
        current = queue.pop(0)
        result.append(current)
        
        neighbors = graph.get(current, [])
        for neighbor in neighbors:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if all nodes were processed
    return result if len(result) == len(graph) else None

# Topological Sort with cycle detection
def topological_sort_with_cycle_detection(graph):
    visited = set()
    rec_stack = set()
    result = []
    cycle = []
    
    def dfs(node, path):
        if node in rec_stack:
            # Found a cycle
            cycle_start = path.index(node)
            cycle.extend(path[cycle_start:])
            return True
        
        if node in visited:
            return False
        
        visited.add(node)
        rec_stack.add(node)
        path.append(node)
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if dfs(neighbor, path):
                return True
        
        rec_stack.remove(node)
        path.pop()
        result.insert(0, node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node, []):
                return {'has_cycle': True, 'cycle': cycle}
    
    return {'has_cycle': False, 'result': result}

# Topological Sort for multiple components
def topological_sort_multiple(graph):
    visited = set()
    result = []
    
    def dfs(node):
        visited.add(node)
        
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                dfs(neighbor)
        
        result.insert(0, node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return result