Home | | **User Interface Design** | Depth First Search(DFS) Algorithm: Working Principle, Forest, Application

Depth-first search starts visiting vertices of a graph at an arbitrary vertex by marking it as having been visited.

**DEPTH
FIRST SEARCH**

**WORKING PRINCIPLE**

â™¦ Depth-first
search starts visiting vertices of a graph at an arbitrary vertex by marking it
as having been visited.

â™¦ On each
iteration, the algorithm proceeds to an unvisited vertex that is adjacent to
the one it is currently in.

â™¦ The
algorithm stops, when there is no unvisited adjacent unvisited vertex.

â™¦ At a dead
end, the algorithm backs up one edge to the vertex it came from and tries to
continue visiting unvisited vertices from there.

â™¦ The
algorithm eventually halts, when there is no unvisited unvisited vertex.

â™¦ Stack is
used totrace the operation of depth-first search.

â™¦ Push a
vertex onto the stack when the vertex is reached for the first time (i.e., the
visit of the vertex starts), and pop a vertex off the stack when it becomes a
dead end (i.e., the visit of the vertex ends).

**1. DEPTH FIRST SEARCH FOREST**

â™¦ It is
also very useful to accompany a depth-first search traversal by constructing
the so called **depth-first search forest***.*

â™¦ The
traversal's starting vertex serves as the root of the first tree in such a
forest. Whenever a new unvisited vertex is reached for the first time, it is
attached as a child to the vertex from which it is being reached. Such an edge
is called a **tree edge** because the
set of all such edges forms a forest.

â™¦ The
algorithm may also encounter an edge leading to a previously visited vertex
other than its immediate predecessor (i.e., its parent in the tree). Such an
edge is called a **back** **edge **because it connects a vertex to
its ancestor, other than the parent, in the depth-first** **search forest.

â™¦ Here is a
pseudo code of the depth-first search.

**2. ALGORITHM DFS(G)**

*Algorithm Dfs(G)*

*//Implements a depth-first search
traversal of a given graph //Input: Graph G = (V, E)*

*//0utput: Graph G with its
vertices marked with consecutive integers in the order they've been first
encountered by the DFS traversal mark each vertex in V with 0 as a mark of
being "unvisited"*

*count *^{!}* 0*

*for **each vertex v in V do*

*if v is
marked with 0 dfs (v)*

*dfs(v)*

*//visits recursively all the
unvisited vertices connected to vertex v and assigns them the numbers in the
order they are encountered via global variable count count *^{!}*count +
1; mark v with count*

*for **each
vertex w in V adjacent to v do if w
is marked with 0*

*dfs(w)*

**Fig: Example of a DFS traversal**

*(a) Graph. (b) Traversal's stack
(the first subscript number indicates the order in which a vertex was visited,
i.e., pushed onto the stack; the second one indicates the order in which it
became a dead-end, i.e., popped off the stack). (c) DFS forest (with the tree
edges shown with solid lines and the back edges shown with dashed lines).*

â™¦ A DFS
traversal itself and the forest-like representation of a graph it provides have
proved to be extremely helpful for the development of efficient algorithms for
checking many important properties of graphs.

â™¦ DFS
yields two orderings of vertices:

1. The order
in which the vertices are reached for the first time (pushed onto the stack)

2. The order
in which the vertices become dead ends (popped off the stack).

These
orders are qualitatively different, and various applications can take advantage
of either of them.

**3. APPLICATIONS OF DFS**

â™¦ DFS is
used for

â™¦ Checking connectivity
of the graph

â™¦ Checking
a cyclicity of a graph.

**Checking connectivity of the
graph**

â™¦ Checking
a graph's connectivity can be done as follows.

â™¦ Start a
DFS traversal at an arbitrary vertex

â™¦ Check,
after the algorithm halts, whether all the graph's vertices will have been
visited.

â™¦ If they
have, the graph is connected; otherwise, it is not connected

**Checking a cyclicity of a graph**

â™¦ If there
is a back edge in DFS forest , then the
graph is acyclic.

â™¦ If there
is a back edge,from some vertex u to its ancestor *v* (e.g., the back edge from *d*
to *a* in Figure 5.5c), the graph has a
cycle that comprises the path from :J to *u*
via a sequence of tree edges in the DFS forest followed by the back edge from *u* to *v.*

**Articulation point**

â™¦ A
vertex of a connected graph is said to be its articulation point if its removal
with all edges incident to it breaks the graph into disjoint pieces.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Analysis and Design of Algorithm : Traversals, Branch and Bound : Depth First Search(DFS) Algorithm: Working Principle, Forest, Application |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.