Adjacency List in Python Using Dictionary
Use a dictionary where each key is a vertex, and the corresponding value is a list of its neighboring vertices.
Step-by-step algorithm:
- Initialize an empty dictionary.
- Add vertices to the dictionary.
- Add edges between vertices by updating the dictionary.
- Display the adjacency list.
Below is the implementation of the above approach:
def adjacency_list_dictionary(V, edges):
adjacency_list = {}
# Add vertices to the dictionary
for i in range(V):
adjacency_list[i] = []
# Add edges to the dictionary
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))}")
# testcase 1
V1 = 3
edges1 = [[0, 1], [1, 2], [2, 0]]
adjacency_list_dictionary(V1, edges1)
# testcase 2
V2 = 4
edges2 = [[0, 1], [1, 2], [1, 3], [2, 3], [3, 0]]
adjacency_list_dictionary(V2, edges2)
Output
0 -> 1 1 -> 2 2 -> 0 0 -> 1 1 -> 2 3 2 -> 3 3 -> 0
Time Complexity:
- Initialization: O(V)
- 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