This post is completed by 1 user

  • 0
 Add to List
Medium

423. 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.

Example:

Approach: 

  1. Earlier we had seen Graph Implementation using Map. In this article, we will use this implementation.
  2. 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.
  3. 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.
  4. 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.
  5. See the code for more understanding.

Output:

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:

Related Problems: