Abstract:
Graph traversals, such as depth-first search and breadth-first search, are commonly used to solve many problems on graphs. By implementing a graph traversal, we consequently reach all graph vertices that belong to a connected component. The breadth-first search is the usual choice when constructing efficient algorithms for finding connected components of a graph. Methods of simple iteration for solving systems of linear equations with modified graph adjacency matrices can be considered as graph traversal algorithms if we use a properly specified right-hand side. These traversal algorithms, generally speaking, turn out to be neither equivalent to depth-first search nor to breadth-first search. An example of such a traversal algorithm is the one associated with the Gauss — Seidel method. For an arbitrary connected graph, the algorithm requires no more iterations to visit all its vertices than it takes for breadth-first search. For a large number of instances of the problem, fewer iterations will be required.
Keywords:graph traversals, connectivity problems on graphs.
Fulltext:
PDF file (1275 kB)