A DFS algorithm, as the name implies, is used to search deeper in the graph, whenever possible. The edges are explored, out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the search backtracks to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the source vertex. DFS uses stack structure to maintain the order in which the vertices are to be Read More

Stack and queue are data structures whose elements are ordered based on the sequence in which they have been inserted. The pop operation retrieves the last element inserted, and the remove operation retrieves the first element inserted. If there is an intrinsic order among the elements themselves (for example, numeric order or alphabetic order), it is ignored in the stack or queue operations. The priority queue is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations. There are two types Read More

The former method discussed is quite inefficient. Let us see if a more efficient method to compute path can be produced. Let us define the matrix path k such that path k [i][j] is true if and only if there is a path from node i to node j that does not pass through any nodes numbered higher than k (except, possibly, for i and j themselves). How can the value of path k+ J [i][j] be obtained from path k? Clearly for any i and j such that path Read More