Adjacency List in Python Using defaultdict
Use
defaultdict
from thecollections
module where each key is a vertex, and the corresponding value is a list of its neighboring vertices.
Step-by-step algorithm:
- Initialize a
defaultdict
with a list as the default value. - Add edges between vertices by updating the
defaultdict
. - Display the adjacency list.
Below is the implementation of the above approach:
from collections import defaultdict
def adjacency_list_defaultdict(V, edges):
adjacency_list = defaultdict(list)
# Add edges to the defaultdict
for edge in edges:
vertex1, vertex2 = edge
adjacency_list[vertex1].append(vertex2)
# Display the adjacency list
for vertex, neighbors in adjacency_list.items():
print(f"{vertex} -> {' '.join(map(str, neighbors))}")
# test case 1
V1 = 3
edges1 = [[0, 1], [1, 2], [2, 0]]
adjacency_list_defaultdict(V1, edges1)
# test case 2
V2 = 4
edges2 = [[0, 1], [1, 2], [1, 3], [2, 3], [3, 0]]
adjacency_list_defaultdict(V2, edges2)
Output
0 -> 1 1 -> 2 2 -> 0 0 -> 1 1 -> 2 3 2 -> 3 3 -> 0
Time Complexity:
- Adding edges: O(E)
- Display: O(V + E)
Auxiliary Space: O(V + E)
Adjacency List in Python
Given the adjacency list and the number of vertices and edges of a graph, the task is to represent the adjacency list for a directed graph.
Examples:
Input:
V = 3
edges[][] = {{0, 1}, {1, 2}, {2, 0}}
Output:
0 -> 1
1 -> 2
2 -> 0
Explanation: The output represents the adjacency list for the given graph.Input:
V = 4
edges[][] = {{0, 1}, {1, 2}, {1, 3}, {2, 3}, {3, 0}}
Output:
0 -> 1
1 -> 2 3
2 -> 3
3 -> 0
Explanation: The output represents the adjacency list for the given graph.
Contact Us