|
This post is completed by 1 user
|
Add to List |
395. Implement Graph Using Map or dictionary
Earlier, we have seen Graph and its representations. A graph can be represented using adjacency list and adjacency matrix. So far we have seen the traditional implementation of the Graph. In this article, we will implement the Graph represented by Adjacency List using the HashMap data structure.
Use Hash Maps:
- We will use two maps.
- The first map for storing the vertices and edges.
- Second map for storing the index for each vertex. the second map will be used in traversing the graph to avoid going in loops. (used by the visited array in case of DFS or BFS ).
- The first map will have vertex as key and linked list (connected vertices will be stored in the list) as value.
- See the code below for more understanding.
Output:
Vertex A is connected to: G C B Vertex B is connected to: E D Vertex C is connected to: D Vertex D is connected to: E Vertex E is connected to: Vertex F is connected to: Vertex G is connected to: E Depth First Traversal A G E C D B F