Be the first user to complete this post
|Add to List|
Given Graph - Remove a vertex and all edges connect to the vertex
Objective: Given a graph represented by an adjacency list and a vertex, write a program to remove the given vertex and all edges connected to that vertex.
- Earlier we had seen Graph Implementation using Map. In this article, we will use this implementation.
- Delete the vertex from the indexes map (This map is used for DFS or BFS traversals) since there will be no traversal from the deleted vertex.
- Remove the vertex from the first map (vertices are stored as a key in the map). This will delete vertex and all outgoing edges from the deleted vertex.
- To delete incoming edges towards deleted vertex from the other vertices, traverse all the linked list for other vertices and delete the vertex if there is any. This will delete the edge from other vertices to the deleted vertex.
- See the code for more understanding.
Vertex A is connected to: B Vertex B is connected to: C Vertex C is connected to: E D Vertex D is connected to: E Vertex E is connected to: Removed Vertex C is removed from the graph (including all associated edges) Vertex A is connected to: B Vertex B is connected to: Vertex D is connected to: E Vertex E is connected to:
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue without decrease key in O(ElogV) Hard
- Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Min Heap – Java Implementation Hard
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue with decrease key Hard