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