×

# How to find unreachable nodes using DFS?

 0 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. asked 30 Dec '16, 18:44 115●2●10 accept rate: 0%

 4 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. answered 30 Dec '16, 19:38 371●2 accept rate: 23% I'v written the code as you said: http://ideone.com/GOFQ1P Is it correct? (03 Jan '17, 21:09) 2 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 (04 Jan '17, 00:34) Thank You once again!! (04 Jan '17, 16:46)
 1 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. answered 30 Dec '16, 19:37 3★prj18 56●1 accept rate: 50%
 0 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). https://www.youtube.com/watch?v=uT1p5Eiw9CE&list=PLuREqZJz3mfTX-5QnvKyackNLDGcweWnu&index=5 answered 04 Jan '17, 12:50 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,236
×734

question asked: 30 Dec '16, 18:44

question was seen: 2,297 times

last updated: 04 Jan '17, 16:46