How Do You Write a Function for Depth First Search in Graph Traversal?

  • Context: MHB 
  • Thread starter Thread starter Henry R
  • Start date Start date
  • Tags Tags
    Depth Graph Search
Click For Summary
SUMMARY

The discussion focuses on implementing the Depth First Search (DFS) algorithm for graph traversal. The provided pseudocode outlines the DFS function, which initializes vertex colors, parent pointers, and timestamps for discovery and finishing times. The algorithm recursively visits adjacent vertices, marking them as visited and updating their properties. This implementation is crucial for understanding graph traversal techniques in computer science.

PREREQUISITES
  • Understanding of graph theory concepts, including vertices and edges.
  • Familiarity with recursive programming techniques.
  • Knowledge of algorithm complexity analysis.
  • Basic understanding of data structures, particularly adjacency lists.
NEXT STEPS
  • Study the implementation of DFS in Python using the provided pseudocode.
  • Explore the differences between Depth First Search and Breadth First Search (BFS).
  • Learn about graph representation techniques, such as adjacency matrices and lists.
  • Investigate applications of DFS in solving problems like topological sorting and cycle detection.
USEFUL FOR

Students, software developers, and computer scientists interested in algorithm design and graph theory will benefit from this discussion.

Henry R
Messages
25
Reaction score
0
Hello... how to write the function of depth first search?

Thank you.
 
Technology news on Phys.org
Henry R said:
Hello... how to write the function of depth first search?

Thank you.

Hi! (Wave)

That's the algorithm of depth-first-search:

Code: 
Depthfirstsearch(G)
   for each v ∈ V
        color[v]=white
        p[v]=NIL
   time=0
   for each v ∈ V
       if color[v]=white then
          Visit(v)

Code: 
Visit(u)
  color[u]=gray
  time=time+1
  d[u]=time
  for each v ∈ Adj[u]
       if color[v]=white then
          p[v]=u
          Visit(v)
  color[u]=black
  time=time+1
  f[u]=time
 
evinda said:
Hi! (Wave)

That's the algorithm of depth-first-search:

Code: 
Depthfirstsearch(G)
   for each v ∈ V
        color[v]=white
        p[v]=NIL
   time=0
   for each v ∈ V
       if color[v]=white then
          Visit(v)

Code: 
Visit(u)
  color[u]=gray
  time=time+1
  d[u]=time
  for each v ∈ Adj[u]
       if color[v]=white then
          p[v]=u
          Visit(v)
  color[u]=black
  time=time+1
  f[u]=time
Hey! Thanks. But, did u get the code by any websites? Oh okay, I understand. Thanks for helping.
 
Last edited:
Henry R said:
Hey! Thanks. But, did u get the code by any websites? Oh okay, I understand. Thanks for helping.

I found it in my notes.. (Smile)
 

Similar threads

MHB How to check if search problem has no solution in depth limit search?
  • · Replies 1 ·
Replies
1
Views
1K
Python Solving UnboundLocalError for Python Iterative Deepening Depth First Search
  • · Replies 1 ·
Replies
1
Views
2K
Python Confused about recursion in python-depth first search-:
  • · Replies 3 ·
Replies
3
Views
1K
How to check if search problem has no solution in depth limit search?
  • · Replies 2 ·
Replies
2
Views
2K
How do programs draw function graphs?
  • · Replies 14 ·
Replies
14
Views
2K
Java FileFinder using Breadth First Search algorithm fails
  • · Replies 2 ·
Replies
2
Views
2K
How to search just the first two characters in a c-string?
  • · Replies 18 ·
Replies
18
Views
4K
MHB Apply Depth-first Search Algorithm Example
  • · Replies 4 ·
Replies
4
Views
2K
Python Graphing a piecewise function (Python)
  • · Replies 2 ·
Replies
2
Views
4K
Comp Sci Exception has occurred: UnboundLocalError local variable 'depth' refer
  • · Replies 2 ·
Replies
2
Views
1K