Kahn’s Algorithm in Python

Kahn’s Algorithm is used for topological sorting of a directed acyclic graph (DAG). The algorithm works by repeatedly removing nodes with no incoming edges and recording them in a topological order. Here’s a step-by-step implementation of Kahn’s Algorithm in Python.

Example:

Input: V=6 , E = {{2, 3}, {3, 1}, {4, 0}, {4, 1}, {5, 0}, {5, 2}}

Output: 5 4 2 3 1 0
Explanation: In the above output, each dependent vertex is printed after the vertices it depends upon.

Input: V=5 , E={{0, 1}, {1, 2}, {3, 2}, {3, 4}}

Output: 0 3 4 1 2
Explanation: In the above output, each dependent vertex is printed after the vertices it depends upon.

Step-by-Step Implementation:

Step 1: Representing the Graph

We’ll represent the graph using an adjacency list. Additionally, we need to keep track of the in-degree (number of incoming edges) of each node.

Python

from collections import defaultdict, deque

class Graph:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.in_degree = [0] * n
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.in_degree[v] += 1

Step 2: Implementing Kahn’s Algorithm

The algorithm uses a queue to manage nodes with no incoming edges.

Python

def kahn_topological_sort(graph):
    # Queue to hold nodes with no incoming edges
    queue = deque([node for node in range(graph.n) if graph.in_degree[node] == 0])
    
    topological_order = []
    
    while queue:
        node = queue.popleft()
        topological_order.append(node)
        
        # For each outgoing edge from the current node
        for neighbor in graph.graph[node]:
            # Decrease the in-degree of the neighbor
            graph.in_degree[neighbor] -= 1
            # If the neighbor has no other incoming edges, add it to the queue
            if graph.in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if topological sorting is possible (graph should have no cycles)
    if len(topological_order) == graph.n:
        return topological_order
    else:
        # If not all nodes are in topological order, there is a cycle
        return "Graph has at least one cycle"

Step 3: Putting It All Together

Now we can combine the graph creation and Kahn’s Algorithm into a complete example.

Python

# Example usage
def main():
    # Number of nodes in the graph
    n = 6
    # List of edges in the graph
    edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
    
    # Create a graph with n nodes
    graph = Graph(n)
    
    # Add edges to the graph
    for u, v in edges:
        graph.add_edge(u, v)
    
    # Perform topological sort using Kahn's Algorithm
    topological_order = kahn_topological_sort(graph)
    
    print("Topological Order:", topological_order)

if __name__ == "__main__":
    main()

Explanation:

Graph Representation: The graph is represented using an adjacency list, and the in-degree of each node is tracked.
Queue Initialization: Nodes with no incoming edges are added to the queue initially.
Topological Sorting: Nodes are processed in the order they are dequeued. For each node, its neighbors’ in-degrees are reduced by 1. If a neighbor’s in-degree becomes 0, it is added to the queue.
Cycle Detection: After processing all nodes, if the topological order contains all nodes, the graph is a DAG. Otherwise, the graph contains at least one cycle.

Python Implementation:

Here is the complete code for Kahn’s Algorithm in Python:

Python

from collections import defaultdict, deque

class Graph:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.in_degree = [0] * n
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.in_degree[v] += 1

def kahn_topological_sort(graph):
    # Queue to hold nodes with no incoming edges
    queue = deque([node for node in range(graph.n) if graph.in_degree[node] == 0])
    
    topological_order = []
    
    while queue:
        node = queue.popleft()
        topological_order.append(node)
        
        # For each outgoing edge from the current node
        for neighbor in graph.graph[node]:
            # Decrease the in-degree of the neighbor
            graph.in_degree[neighbor] -= 1
            # If the neighbor has no other incoming edges, add it to the queue
            if graph.in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if topological sorting is possible (graph should have no cycles)
    if len(topological_order) == graph.n:
        return topological_order
    else:
        # If not all nodes are in topological order, there is a cycle
        return "Graph has at least one cycle"

# Example usage
def main():
    # Number of nodes in the graph
    n = 6
    # List of edges in the graph
    edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
    
    # Create a graph with n nodes
    graph = Graph(n)
    
    # Add edges to the graph
    for u, v in edges:
        graph.add_edge(u, v)
    
    # Perform topological sort using Kahn's Algorithm
    topological_order = kahn_topological_sort(graph)
    
    print("Topological Order:", topological_order)

if __name__ == "__main__":
    main()

Output

Topological Order: [4, 5, 2, 0, 3, 1]

Time Complexity: O(N)
Auxiliary Space: O(N)

Step-by-Step Implementation:

Step 1: Representing the Graph

Step 2: Implementing Kahn’s Algorithm

Step 3: Putting It All Together

Explanation:

Python Implementation:

Contact Us