Articulation Point Explanation

Revision en1, by Ehsan_sShuvo, 2017-04-30 12:11:23

Could anyone please explain me clearly why we have to do

low[vertex]=min(low[vertex],dis[i]);

Yeah!I know that is for lowest discovery time determination.But my question is that all the time we put minimum time in the current node comparing with its adjacent nodes,but not increase the time.My question is two or more nodes cant visit at a time.But lowest time show that,it can do that.But how? Could anyone please clear me out?Actually,i read more than 5/6 resources,but i couldn't get that.There all says about subtree,ancestor,blah blah,but my memory couldn't make a sense for that,what they actually want to say.

Thanks in advance.

Following is the psuedocode of finding out articulation point. ~~~~~ time = 0 function DFS(adj[][], disc[], low[], visited[], parent[], AP[], vertex, V) visited[vertex] = true disc[vertex] = low[vertex] = time+1 child = 0 for i = 0 to V if adj[vertex][i] == true if visited[i] == false child = child + 1 parent[i] = vertex DFS(adj, disc, low, visited, parent, AP, i, n, time+1) low[vertex] = minimum(low[vertex], low[i]) if parent[vertex] == nil and child > 1 AP[vertex] = true if parent[vertex] != nil and low[i] >= disc[vertex] AP[vertex] = true else if parent[vertex] != i low[vertex] = minimum(low[vertex], disc[i]) ~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Ehsan_sShuvo 2017-04-30 12:13:02 4 Tiny change: '\nCould anyo' -> 'Could anyo' (published)
en1 English Ehsan_sShuvo 2017-04-30 12:11:23 1741 Initial revision (saved to drafts)