You are not logged in. Please login at www.codechef.com to post your questions!

×

How to find unreachable nodes using DFS?

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

aniketsanadhya's gravatar image

1★aniketsanadhya
115210
accept rate: 0%


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.

link

answered 30 Dec '16, 19:38

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

I'v written the code as you said: http://ideone.com/GOFQ1P Is it correct?

(03 Jan '17, 21:09) aniketsanadhya1★
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) nikhil_chandak5★

Thank You once again!!

(04 Jan '17, 16:46) aniketsanadhya1★

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.

link

answered 30 Dec '16, 19:37

prj18's gravatar image

3★prj18
561
accept rate: 50%

link

answered 30 Dec '16, 19:33

vpriyanshu40's gravatar image

2★vpriyanshu40
815
accept rate: 12%

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

link

answered 04 Jan '17, 12:50

pijushsaha's gravatar image

0★pijushsaha
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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