Editing Depth-first search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 106: | Line 106: | ||
<pre> | <pre> | ||
function DFS(u,v) | function DFS(u,v) | ||
− | if id[v] = -1 | + | if id[v] = -1 |
id[v] = cnt | id[v] = cnt | ||
let pred[v] = u | let pred[v] = u | ||
Line 121: | Line 121: | ||
</pre> | </pre> | ||
After the termination of this algorithm, ''cnt'' will contain the total number of connected components, ''id[u]'' will contain an ID number indicating the connected component to which vertex ''u'' belongs (an integer in the range [0,''cnt'')) and ''pred[u]'' will contain the parent vertex of ''u'' in some spanning tree of the connected component to which ''u'' belongs, unless ''u'' is the first vertex visited in its component, in which case ''pred[u]'' will be ''u'' itself. | After the termination of this algorithm, ''cnt'' will contain the total number of connected components, ''id[u]'' will contain an ID number indicating the connected component to which vertex ''u'' belongs (an integer in the range [0,''cnt'')) and ''pred[u]'' will contain the parent vertex of ''u'' in some spanning tree of the connected component to which ''u'' belongs, unless ''u'' is the first vertex visited in its component, in which case ''pred[u]'' will be ''u'' itself. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==References== | ==References== |