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

AI Thread 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 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
Back
Top