Let G be a directed graph with nodes numbered 1 through 7 and the following edge

Question

Let G be a directed graph with nodes numbered 1 through 7 and the following edges:

(1, 2),(1, 6),(3, 4),(4, 1),(4, 5),(5, 6),(6, 3),(6, 7),(7, 5)

Run the depth-first search algorithm on G. Use node 1 as the starting node. Assume that the algorithm considers neighbors in numerical order. List the nodes in the order that they are visited by the algorithm. For each node, give the node that the previous pointer points to. In addition, draw the depth-first tree generated by those previous pointers. 2

Explanation / Answer

Answer for Question:

Step 1: Construct the graph for the given nodes.

4----   1 ----2
|       |
|       |
|       |
3-----6-----5----- is having relation with 4 also
| |
| |
| |
       -----7
Step 2: Run the depth first search on the given graph start from node 1.

---> 1 have the relation with 4 , 2 and 6
---> next start from 4 have the 3, 1 and 5 (i is already visited)
Cycle break the cycle ..
---> next start from node 5 have the 6 , 4 and 7 (4 is visited)
---> next Start from node 7 have the 6 and 5 (5 is done)

1----2----4----5----7---6----3

Node Pointer 1 Pointer 2
1 1 2
2 none           1
4 5 1
5 7 4
7 6 5
6 3 7
3 none 6

The above listed nodes not having the cycles

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.