One Stop GATE Forum: Techniques for graphs:

Message

7.3 Techniques for graphs:

A fundamental problem concerning graphs is the reachability
problem. In its simplest form it requires us to determine whether there
exists a path in the given graph G=(V,E) such that this path starts at
vertex v and ends at vertex u. A more general form is to determine for
a given starting 

Vertex
v belonging to V all vertices u such that there is a path from v to u.
This latter problem can be solved by starting at vertex v and
systematically searching the graph G for vertices that can be reached
from v. The 2 search methods for this are :

Breadth first search.
Depth first search.

7.3.1 Breadth first search:

In
Breadth first search we start at vertex v and mark it as having been
reached. The vertex v at this time is said to be unexplored. A vertex
is said to have been explored by an algorithm when the algorithm has
visited all vertices adjacent from it. All unvisited vertices adjacent
from v are visited next. There are new unexplored vertices. Vertex v
has now been explored. The newly visited vertices have not been
explored and are put onto the end of the list of unexplored vertices.
The first vertex on this list is the next to be explored. Exploration
continues until no unexplored vertex is left. The list of unexplored
vertices acts as a queue and can be represented using any of the
standard queue representations.

7.3.2 Depth first search:

 A depth first search of a graph differs from a breadth first
search in that the exploration of a vertex v is suspended as soon as a
new vertex is reached. At this time the exploration of the new vertex u
begins. When this new vertex has been explored, the exploration of u
continues. The search terminates when all reached vertices have been
fully explored. This search process is best-described recursively.

	Algorithm DFS(v)
	{
		visited[v]=1
		for each vertex w adjacent from v do
		{
			If (visited[w]=0)then
			DFS(w);
		}
	}

Author	Message
gita Newbie Joined: 08Apr2007 Online Status: Offline Posts: 19	Topic: Techniques for graphs: Posted: 08Apr2007 at 11:22pm
	7.3 Techniques for graphs: A fundamental problem concerning graphs is the reachability problem. In its simplest form it requires us to determine whether there exists a path in the given graph G=(V,E) such that this path starts at vertex v and ends at vertex u. A more general form is to determine for a given starting Vertex v belonging to V all vertices u such that there is a path from v to u. This latter problem can be solved by starting at vertex v and systematically searching the graph G for vertices that can be reached from v. The 2 search methods for this are : Breadth first search. Depth first search. 7.3.1 Breadth first search: In Breadth first search we start at vertex v and mark it as having been reached. The vertex v at this time is said to be unexplored. A vertex is said to have been explored by an algorithm when the algorithm has visited all vertices adjacent from it. All unvisited vertices adjacent from v are visited next. There are new unexplored vertices. Vertex v has now been explored. The newly visited vertices have not been explored and are put onto the end of the list of unexplored vertices. The first vertex on this list is the next to be explored. Exploration continues until no unexplored vertex is left. The list of unexplored vertices acts as a queue and can be represented using any of the standard queue representations. 7.3.2 Depth first search: A depth first search of a graph differs from a breadth first search in that the exploration of a vertex v is suspended as soon as a new vertex is reached. At this time the exploration of the new vertex u begins. When this new vertex has been explored, the exploration of u continues. The search terminates when all reached vertices have been fully explored. This search process is best-described recursively. Algorithm DFS(v) { visited[v]=1 for each vertex w adjacent from v do { If (visited[w]=0)then DFS(w); } } Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE Technical Discussions : GATE CS