I am fairly new to Graph Theory, just learned DFS algorithm and found number of connected components using DFS. Now I had to find number of unreachable nodes using DFS. I am failing to build a solid logic that will help me finding the nodes. For finding connected components, I just checked if the visited nodes if it is false or not.
This link is helpful.
https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm
let us assume that you have total n vertices numbered(1 to n) , and let visited[1 … n] be an array all of which’s elements are initialized to false. Now you run the dfs from the source and all the nodes that are reachable from the dfs will
have the entry true in the visited array after the function completes it’s work.
Now all the nodes that have false in their visited array index are unreachable so you could simply count them.
1 Like
If you know DFS, then you must be knowing that to perform DFS you need a start vertex (lets say s) and a list of nodes which keeps track of the visited ones.
To find all the nodes which are unreachable from s, you simply start DFS from s. After the subroutine ends, all the nodes which are not visited by s are all the unreachable nodes. The number of unreachable nodes is hence, total number of nodes - number of visited nodes.
2 Likes
Yea, almost correct. c should be initially 1 as source vertex is always reachable from itself and you’re printing the number of reachable nodes. Since you want the number of unreachable nodes, you may print “nodes - c”. Here’s the link with the modifications : http://ideone.com/2mH587
1 Like
For unreachable nodes, I think we need to restart the dfs process again, and for that we need a loop to start dfs for every unvisited node.
The link given, has a clear explanation(watch it till the end).
Thank You once again!!