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

Discussion Overview

The discussion revolves around writing a function for depth-first search (DFS) in graph traversal. Participants share algorithmic details and seek clarification on the implementation of DFS.

Discussion Character

  • Technical explanation
  • Homework-related

Main Points Raised

  • One participant requests guidance on how to write a function for depth-first search.
  • Another participant provides a detailed algorithm for depth-first search, outlining the steps involved in the process.
  • A participant expresses curiosity about the source of the provided code, questioning whether it was obtained from a website.
  • The participant who shared the algorithm indicates that it was found in their notes.

Areas of Agreement / Disagreement

The discussion does not appear to have significant disagreement, as participants are primarily focused on sharing and clarifying the algorithm for depth-first search.

Contextual Notes

There are no explicit limitations or unresolved issues mentioned in the discussion.

Who May Find This Useful

This discussion may be useful for individuals looking to understand or implement depth-first search in graph algorithms, particularly students or those new to algorithm design.

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