Which are in cormen book.
Algorithm 1
DFS(G).
1.FOR each v ∈ V do
2. visited(v) := 0
3. FOR each v ∈ V do
4. IF (visited(v) = 0) then
5. DFS(G, v)
DFS(G, v)
1. visited(v) := 1
2. FOR each y ∈ adj(v) do
3. IF (visited(y) = 0) then
4. DFS(G, y)
Algorithm 2
DFS(G)
1.FOR each v ∈ V do
2. v.color := WHITE
3. v.parent := NIL
4. time := 0
5. FOR each v ∈ V do
6. IF v.color = WHITE then
7 DFS-VISIT(G, v)
DFS-VISIT(G, v)
1. time := time + 1
2. v.d := time
3. v.color := GRAY
4. FOR each y ∈ adj(v) do
5. IF y.color = WHITE then
6. y.parent := v
7. DFS-VISIT(G, y)
8. v.color := BLACK
9. time = time + 1
It's just a basic level question. ResearchGate is a platform for professionals, not to answer such questions.
Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux.
ref. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp. 540–549.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence