Graph – Find Number of non reachable vertices from a given vertex

Objective: Given undirected graph write an algorithm to count the number of non reachable vertices from a given vertex

Example:

Approach:

Use DFS

  • Do the DFS (Depth-First Search) from the given vertex A, Recursively do the DFS from all the adjacent vertices of given vertex A.
  • Use the visited array to keep track of visited vertices.
  • Once the DFS is completed, count the number of false in visited array. These are the vertices which did not get visit.

Code:


Output:

Number of non reachable vertices from the vertex 0 are: 4
Number of non reachable vertices from the vertex 6 are: 5

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: