Techniques for graphs:
Printed From: One Stop GATE
Category: GATE Technical Discussions
Forum Name: GATE CS
Forum Discription: General Technical Discussions, Queries, doubts etc. for GATE in CS.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=1102
Printed Date: 26Feb2025 at 6:53am
Topic: Techniques for graphs:
Posted By: gita
Subject: Techniques for graphs:
Date 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);
}
}
|
|