Related Topics
Data Structure
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:
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.
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.