Related Topics
Data Structure
0 1 2 3
-------------
0 | 0 1 1 0
1 | 1 0 1 1
2 | 1 1 0 1
3 | 0 1 1 0
An adjacency list is a collection of linked lists where each vertex has its own linked list containing the vertices it is adjacent to. For a weighted graph, each vertex’s linked list contains pairs of the adjacent vertex and the weight of the edge. An adjacency list can be more space-efficient than an adjacency matrix for sparse graphs.
Here’s an example of an adjacency list for the same graph as above:
0 -> [1, 2]
1 -> [0, 2, 3]
2 -> [0, 1, 3]
3 -> [1, 2]
In this example, vertex 0 is adjacent to vertices 1 and 2, vertex 1 is adjacent to vertices 0, 2, and 3, and so on.
from collections import deque
def topological_sort(graph):
# Step 1
topological_order = []
# Step 2
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
# Step 3
source_nodes = deque([node for node in in_degree if in_degree[node] == 0])
# Step 4-7
while source_nodes:
node = source_nodes.popleft()
topological_order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
source_nodes.append(neighbor)
# Step 8
if len(topological_order) != len(graph):
raise ValueError("Graph contains a cycle")
return topological_order
The above implementation takes a dictionary graph that maps each node to a list of its neighbors. The function returns a list of nodes in topological order if the input graph is a DAG, or raises a ValueError if the graph contains a cycle.
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.