Question
How can I create a sample directed graph in code and implement a topological sort algorithm?
# Sample Python code for creating a directed graph and performing topological sort
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def topological_sort_util(self, v, visited, stack):
visited[v] = True
for node in self.graph[v]:
if not visited[node]:
self.topological_sort_util(node, visited, stack)
stack.append(v)
def topological_sort(self):
visited = {node: False for node in self.graph}
stack = []
for node in self.graph:
if not visited[node]:
self.topological_sort_util(node, visited, stack)
print(stack[::-1]) # reversed stack for topological order
# Using the Graph class
g = Graph()
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.topological_sort()
Answer
Creating a directed graph and implementing a topological sort involves understanding both data structures and algorithms. A directed graph is composed of vertices and edges, where each edge has a direction. Topological sorting is an ordering of the vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def topological_sort_util(self, v, visited, stack):
visited[v] = True
for node in self.graph[v]:
if not visited[node]:
self.topological_sort_util(node, visited, stack)
stack.append(v)
def topological_sort(self):
visited = {node: False for node in self.graph}
stack = []
for node in self.graph:
if not visited[node]:
self.topological_sort_util(node, visited, stack)
print(stack[::-1]) # reversed stack for topological order
# Example usage
g = Graph()
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.topological_sort()
Causes
- Misunderstanding of graph structures
- Incorrect implementation of sorting logic
Solutions
- Use depth-first search (DFS) to traverse the graph
- Utilize a stack to store the sorted elements
- Check for cycles in the graph before sorting
Common Mistakes
Mistake: Not handling cycles in the graph properly
Solution: Before performing topological sort, ensure the graph is acyclic.
Mistake: Confusing directed and undirected graphs
Solution: Clarify the type of graph you are working with; directed graphs require different handling.
Helpers
- directed graph
- topological sort
- graph algorithms
- data structures
- Python graph implementation
- DFS topological sort
