# 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:

 import java.util.LinkedList; public class NonReachableVertices { static class Graph{ int vertices; LinkedList[] adjList; Graph(int vertices){ this.vertices = vertices; adjList = new LinkedList[vertices]; for (int i = 0; i (); } } public void addEgde(int source, int destination){ adjList[source].addFirst(destination); adjList[destination].addFirst(source); } public int calculateVertices(int vertex){ boolean [] visited = new boolean[vertices]; //Do the DFS from the given vertex dfs(vertex, visited); //count the number of non reached vertices int count = 0; for (int i = 0; i

Output:

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