JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Searching a Graph Depth-First | Reply
NAME
Searching a Graph Depth-First

PROBLEM
In this article we shall speak about Depth First Search algorithm and how to use it to solve problems. DFS is one of the most basic algorithms: many other algorithms use it and to tell the truth, DFS is a foundation of all these algorithms. The most common using of DFS is traversal of graph. Often it is used for determining whether a graph is acyclic, topsort, searching components.


SOLUTION
The main strategy of this algorithm (as it can be seen from its name) is going in depth while it is possible. I think that it is easier to understand recursive implementation of DFS, so here it is. Imagine that DFS–function is called from vertex v. What do we do is just go through all its neighbors, which we haven’t visited, and call DFS from each of them recurrently one after another. For example, if vertices are people and relations between vertices are father-son relations between people: let’s imagine that DFS is called from my grandfather. We call DFS from his first son (my father) then, we do the same with my father and call DFS from me. As I don’t have children, we do a step back to my father and call DFS from his second son (my brother). As you can see we went down from grandfather to me – to the depth. And if we can’t go deeper, we go one step back (using return from function).

Pseudocode for answering if is a path between vertices a and b exists is like this:
boolean  visited[N];
 
boolean  DFS(vertex a, vertex b)
{
	if(a == b) return true;
	if(visited [a]) return false;
	visited [a] = true;
 
	for(vertex c adjacent to a)
		if(DFS(c))
			return true;
	return false;
}


To do the same, but not recursively, e.g. faster implementation:
boolean  DFS(vertex a, vertex b)
{
	boolean  visited[N];
 
	stack<vertex> s;
	s.push(a);
	visited[a] = true;
 
	while(s is not empty)
	{
		vertex top = s.top();   s.pop();
		if(top == b) return true;                
 
		for(vertex c adjacent to top)
		{
                        if(visited[c] == false)
                        {
			            s.push(c);
                                    visited[c] = true;
                        }
		}		
	}
	return false;
}

Anyway, main thing this algorithm is used for is traversal of graph. And if we want to be in every vertex just once, we should use something to mark vertices we visited, not to go there once more, here we use array visited. When we visit a vertex a, we mark it: visited[a] = true.


If we want to find graph components, we need to go through vertices and if current vertex is not visited we call dfs from it. dfs goes through (visits) all vertices reachable from the current and adds them to the current component. Our pseudocode should look like this (N – number of vertices):

component comp;
boolean visited[N];
 
void dfs(vertex a)
{
	if(visited[a]) return;
	visited[a] = true;
	comp.add(a);
 
	for(vertex c adjacent to a)
		DFS(c);
 
	return;
}
 
int main()
{
	for(int i = 0; i < N; i++)
	{
		if(!visited[i])
		{
			comp.clear();
			DFS(i);
			comp.print();
		}
	}
	return 0;
}
Re: Searching a Graph Depth-First (response to post by ibra) | Reply
Re: Searching a Graph Depth-First (response to post by ibra) | Reply
It is a good DFS recipe right now.

The question is: shouldn't it be expanded? There are a lot of things to tell:
1. DFS time slice: white/grey/black vertices; in/out times for vertices; only tree edges and vertical edges in undirectional graph, maybe something else.
2. Determining whether a graph is acyclic.
3. Topsort (dump vertices on exit from DFS).
Not sure that it is wise to push all these things into this recipe...
Re: Searching a Graph Depth-First (response to post by syg96) | Reply
the problem is that if I begin writing about all algorithms that use DFS I will be doing it for a very long time... I think that here I should tell just about DFS, its nature and person who read it to be able to read articles about all these algorithms.
Of course if some admin will say me to add it, I will do it immediately :)
Re: Searching a Graph Depth-First (response to post by ibra) | Reply
Hi! I am a newbie here.

Can you list some more simple problems which can be solved by DFS?
RSS