Depth-first search and linear graph algorithms
R Tarjan - SIAM journal on computing, 1972 - SIAM
SIAM journal on computing, 1972•SIAM
The value of depth-first search or “backtracking” as a technique for solving problems is
illustrated by two examples. An improved version of an algorithm for finding the strongly
connected components of a directed graph and at algorithm for finding the biconnected
components of an undirect graph are presented. The space and time requirements of both
algorithms are bounded by k_1V+k_2E+k_3 for some constants k_1,k_2, and k_3, where V
is the number of vertices and E is the number of edges of the graph being examined.
illustrated by two examples. An improved version of an algorithm for finding the strongly
connected components of a directed graph and at algorithm for finding the biconnected
components of an undirect graph are presented. The space and time requirements of both
algorithms are bounded by k_1V+k_2E+k_3 for some constants k_1,k_2, and k_3, where V
is the number of vertices and E is the number of edges of the graph being examined.
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples. An improved version of an algorithm for finding the strongly connected components of a directed graph and at algorithm for finding the biconnected components of an undirect graph are presented. The space and time requirements of both algorithms are bounded by for some constants , and , where V is the number of vertices and E is the number of edges of the graph being examined.
Society for Industrial and Applied Mathematics