This post is completed by 1 user
|
Add to List |
276. 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.
Output:
Number of non-reachable vertices from the vertex 0 are: 4 Number of non reachable vertices from the vertex 6 are: 5