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
DISCUSSION

What is good about DFS is that there are many examples if using it among TopCoder problems. Almost all problems of graph theory can be used here. But taking complex algorithms as examples is pretty senselessly, so I will try to talk about problems, where main part of algorithm and implementation is DFS.

First example is Marketing Problem. Problem is in how many ways we can divide goods between adults and teenagers. Some goods can’t be for the same group(like desktop computers and laptops for one group is too much), we will connect such vertices by edges. What do we do is just try to color all vertices into two colors (black and white), so that adjacent vertices have to be of different color. If we can do that we count number of components and return 2 in the power of this number. It is right because if component can be colored into two colors, we can color it in two different ways (it is obvious).
So we have two problems:
1)How to color all vertices in that way.
2)How to count number of components.

If we want to color all vertices into two colors (for example color 0 and color 1, there is what we do: we create array color[], where color[i] is color of i-th vertex. In the very beginning all vertices’ color is -1, and then we one by one call dfs with vertex if its color is -1. Dfs colors the vertex and calls dfs-s to color its neighbors with another color. But if any neighbor is already colored with wrong color means that it is impossible to color vertices into two colors: there is no solution.
If solution exists (while first stage we faced no problems), we just count number of components as it was explained.

class Marketing 
{
  public:
          //graph presentation: if there is an edge a<->b, then g[a][b] = 1 and g[b][a] = 1;
	  vector<vector<int> > g;
          // if a vertex a is visited, then visited[a] = 1; else visited[a] = 0
	  vector<int> visited;
          //number of vertices
	  int n;
 
	  bool dfs(int v, int c)//v is vertex id and c is the color in which we will paint this vertex
	  {
		  visited[v] = c;
 
		  for(int i = 0; i < n; i++)
			  if(g[v][i])//is there is an edge between vertices v and i
			  {
                                  //if vertex i is already visited and colored in wrong color it is bad and it is impossible to color whole graph
				  if(visited[i] != -1 && visited[i] == c)
						  return false;
                                  //if vertex i is not visited we call dfs from it and if returns false we return false too
				  if(visited[i] == -1 && !dfs(i, 1-c))
						  return false;
			  }
		  return true;
	  }
 
    long long howMany(vector <string> c)
	{
		n = c.size(); 
		
		g = vector<vector<int> > (n, vector<int> (n));
		visited = vector<int> (n, -1);
 
                //extracting information about graph from input data to fill g - our presentation of graph
		for(int i = 0; i < n; i++)
		{
			istringstream is(c[i]);
 
			int a;
			while(is >> a)
			{
				g[i][a] = 1;
				g[a][i] = 1;
			}
		}
 
 
                //k is number of components in graph
		int k = 0;
		for(int i = 0; i < n; i++)
		{
			if(visited[i] == -1)
			{
				if(!dfs(i, 0)) // if it is impossible to color graph we return -1 (No solution)
					return -1;
				k++;
			}
		}
 
		return (1LL << k);
      
    }
};
 




Another example of using DFS among TopCoder problems is Circuits. We are given an acyclic graph and we have to return length of the longest path in the graph. Special thing about this problem, which allows using DFS in solution, is that fact, we are given acyclic graph. As we need to find the longest path in it, we just will call DFS from each of vertices, while DFS will return length of maximal path from current vertex. Here is implementation:

class Circuits 
{
public:
        // our presentation of graph: g[i][j] = -1 if there is no edge i -> j else g[i][j] is its weight(or length)
	vector<vector<int> > g;
        // number of vertices
	int n;
 
 
        // v is vertex's id and father is id of vertex we came from(not to go to it again)
	int dfs(int v, int father)
	{
		int maxi = 0;
 
		for(int i = 0; i < n; i++)
                        //if it is not father and there is an edge we check if it is longer than current result
			if(i != father && g[v][i] != -1)
				maxi = max(maxi, dfs(i, v) + g[v][i]);
 
		return maxi;
	}
 
 
	int howLong(vector <string> connects, vector <string> costs) 
	{
		n = connects.size();
		g = vector<vector<int> > (n, vector<int> (n, -1));
		
                // extracting data from input
		for(int i = 0; i < n; i++)
		{
			istringstream iscon(connects[i]);
			istringstream iscos(costs[i]);
			int id, w;
			while(iscon >> id && iscos >> w)
				g[i][id] = w;
		}
 
		int maxi = -1;
		for(int i = 0; i < n; i++)
		{		
			fill(used.begin(), used.end(), false);
			maxi = max(maxi, dfs(i, -1));
		}
 
		return maxi;
 
	}
}
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?
Re: Searching a Graph Depth-First (response to post by ibra) | Reply
For the marketing problem, it seems BFS can also be used in place of DFS, making color assignments level by level. Correct me if i am wrong. Thanks.
RSS