• July 23, 2024

MCA Fifth Semester Model Papers

Faculty: IT 2019 Sample Papers with Solutions Sr. No.  Paper Name  Question Paper Link  Solution Link 1.  Cloud Computing  Click Here  Click Here 2.  Analysis & Design of Algorithm  Click Here …

MCA Third Semester Model Papers

Faculty: IT 2019 Sample Papers with Solutions Sr. No.  Paper Name  Question Paper Link  Solution Link 1.  Java Technologies  Click Here  Click Here 2.  Web Technologies  Click Here  Click Here 3. …

MCA First Semester Model Papers

Faculty: IT 2019 Sample Papers with Solutions Sr. No.  Paper Name  Question Paper Link  Solution Link 1.  Discrete Mathematics  Click Here  Click Here 2.  Programming in C & C++  Click Here …

MSC (Biotechnology) Previous Year Model Papers

Faculty: Science 2019 Sample Papers with Solutions Sr. No.  Paper Name  Question Paper Link  Solution Link 1  Immunology, Virology and Pathogenesis  Click Here  Click Here 2.  Cell Biology  Click Here  Click …

MSC (Biotechnology) Final Year Model Papers

Faculty: Science 2019 Sample Papers with Solutions Sr. No.  Paper Name  Question Paper Link  Solution Link 1  Plant Biotechnology  Click Here  Click Here 2.  Genetic Engineering  Click Here  Click Here


Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking.
A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.

The order of Excution of nodes are as :1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
Pseudo code:
Input: A graph G and a vertex v of G
Output: All vertices reachable from v labeled as discovered
A recursive implementation of DFS:
1 procedure DFS(G,v):
2 label v as discovered
3 for all edges from v to w in G.adjacentEdges(v) do
4 if vertex w is not labeled as discovered then
5 recursively call DFS(G,w)
A non-recursive implementation of DFS:
1 procedure DFS-iterative(G,v):
2 let S be a stack
3 S.push(v)
4 while S is not empty
5 v = S.pop()
6 if v is not labeled as discovered:
7 label v as discovered
8 for all edges from v to w in G.adjacentEdges(v) do
9 S.push(w)

Applications: There are various applications of DFS.
• Finding connected components.
• Detecting cycle in a graph.
• Finding connected components.
• Finding the bridges of a graph.
• Generating words in order to plot the Limit Set of a Group.
• Finding strongly connected components.
• Planarity testing.
• Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)
• Maze generation may use a randomized depth-first search.
• Finding biconnectivity in graphs.

Prof. Vivek Sharma

Author

Leave a Reply