Depth-First Search in Graphs
(Page 1 of 4 )
Anyone or anything that can search effectively will eventually make a major impact on its environment. For a prime example just look at Google -- from a simple search engine came one of the largest companies in the world of IT. So here, in this article, we will discuss a good search algorithm for graphs. What importance may it yield in the future?
Last time I presented the breadth-first search and as I told you then, I am continuing this series of articles about graphs with the second main search algorithm: the depth-first search. Our objective is to visit all points of the graph by starting from a root item and traveling through the edges.
During this article I will focus just as much on the application of the depth-first search algorithm as on the technique itself, so beyond the search itself we are going to solve issues like determining if there is a circle in the graph, the basic circle system of a graph, and categorizing the edges according the depth-first search.
We will sort the tree into a topological order; during a future article, we will find the strong connected components of a graph, and the disconnecting set. These are those edges that, if we remove them, we will increase the number of strongly connected components in the graph (articulation edges). In addition, of course, we will look at the bond, which is the same, but for a set of vertexes (articulation vertexes).
The depth first search's short description is as follows. Visit the root item. Visit the child of that item, and follow on with the child of that item and so on until we find the "bottom" of the graph. Now step back and visit the second child of the previous item, and so on.
The main difference between this and the breadth-first search is that, while the breadth-first search will first visit all the neighbors of the root item and continue only after doing this, the DFS will visit a vertex and immediately step ahead to the child of that item if it is possible. Otherwise, it steps back and tries to do the same with the second vertex, after that with the third (if it exists of course) until it has visited all of the neighbor edges. When we arrive at a child item, the same plan is applied.
Next: The code snippet and classification >>
More Code Examples Articles
More By Gabor Bernat
/ 5 
