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

Click For Summary
The discussion focuses on writing a function for the depth-first search (DFS) algorithm. The algorithm is outlined with a clear structure, initializing vertex colors to white and parent pointers to NIL, followed by a loop to visit each vertex. The visit function updates the vertex's color, discovery time, and explores adjacent vertices recursively. The conversation also touches on the source of the code, with one participant confirming it was from personal notes rather than a website. Overall, the exchange emphasizes understanding the DFS algorithm's implementation.
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)
 

Thread 'For those who ask: "What programming language should I learn?"'

Learn If you want to write code for Python Machine learning, AI Statistics/data analysis Scientific research Web application servers Some microcontrollers JavaScript/Node JS/TypeScript Web sites Web application servers C# Games (Unity) Consumer applications (Windows) Business applications C++ Games (Unreal Engine) Operating systems, device drivers Microcontrollers/embedded systems Consumer applications (Linux) Some more tips: Do not learn C++ (or any other dialect of C) as a...
View full post »

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
1K
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