Scribd
Upload
29 views1 page

Dfs Tracing

The document outlines the steps for implementing a Depth-First Search (DFS) algorithm on a graph. It describes user input for the number of vertices and edges, the edges themselves, and the starting vertex for traversal. An example is provided, demonstrating the order of visited vertices during the DFS process, resulting in the output '1 2 4 5 3'.

Uploaded by

abbaskhankar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
29 views1 page

Dfs Tracing

The document outlines the steps for implementing a Depth-First Search (DFS) algorithm on a graph. It describes user input for the number of vertices and edges, the edges themselves, and the starting vertex for traversal. An example is provided, demonstrating the order of visited vertices during the DFS process, resulting in the output '1 2 4 5 3'.

Uploaded by

abbaskhankar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

1. User inputs the number of vertices (let's say n) and the number of edges (m).

2. User inputs the edges of the graph.


3. User inputs the initial vertex v from which the DFS traversal will start.
4. The program initializes the adjacency matrix c, visited, and visit arrays.
5. The DFS() function is called.
6. In the DFS() function:
 The initial vertex v is printed and marked as visited.
 The program enters a while loop that continues until the stack stk is empty (top
becomes -1).
 Inside the loop, the program pops a vertex v from the stack stk and prints it.
 Then, for each adjacent vertex j of v, if j is not visited, it is marked as visited and
pushed onto the stack stk.
7. The loop continues until all vertices reachable from the initial vertex are visited.

Let's go through an example with sample inputs:

Suppose we have a graph with 5 vertices and 6 edges, and the edges are:

Copy code
121324253545

Let's say the initial vertex is 1.

 Initially, stk is empty (top = -1).


 v is set to 1, and it's marked as visited.
 The while loop starts:
 Vertex 1 is printed.
 Vertices 2 and 3 are adjacent to 1, and they are pushed onto stk.
 Now, stk contains [3, 2] (top = 1).
 The loop continues:
 Vertex 2 is popped from stk, printed, and its adjacent vertices are checked.
 Vertex 4 is adjacent to 2 and is pushed onto stk.
 Now, stk contains [3, 4] (top = 1).
 The loop continues:
 Vertex 4 is popped from stk, printed, and its adjacent vertices are checked.
 Vertex 5 is adjacent to 4 and is pushed onto stk.
 Now, stk contains [3, 5] (top = 1).
 The loop continues:
 Vertex 5 is popped from stk, printed, and its adjacent vertices are checked.
 No new vertices are pushed onto stk.
 Now, stk contains [3] (top = 0).
 The loop continues:
 Vertex 3 is popped from stk, printed, and its adjacent vertices are checked.
 Vertex 5 is already visited, so no new vertices are pushed onto stk.
 Now, stk is empty (top = -1), and the while loop exits.

The output of the program will be:

cssCopy code
Order of visited vertices: 1 2 4 5 3

This is the order in which the DFS algorithm visited the vertices starting from vertex 1.

You might also like