|
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 GraphWe’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 AlgorithmThe 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 TogetherNow 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()
OutputTopological Order: [4, 5, 2, 0, 3, 1]
Time Complexity: O(N)
Auxiliary Space: O(N)
|
Sequence and Series in Python