[go: up one dir, main page]
Scribd
Upload
35 views2 pages

DFS Using Stack

The document describes the Depth First Search (DFS) algorithm using a stack in C programming. It includes a graph representation, an adjacency matrix, and the C code implementation for performing DFS. The step-by-step execution illustrates how the algorithm traverses the graph, resulting in the output of the traversal order starting from vertex 0.

Uploaded by

yashodapawar10
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
35 views2 pages

DFS Using Stack

The document describes the Depth First Search (DFS) algorithm using a stack in C programming. It includes a graph representation, an adjacency matrix, and the C code implementation for performing DFS. The step-by-step execution illustrates how the algorithm traverses the graph, resulting in the output of the traversal order starting from vertex 0.

Uploaded by

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

Depth First Search (DFS) Using Stack in C

Depth First Search (DFS) is a graph traversal algorithm that explores as deeply as possible before
backtracking.
This implementation uses an explicit stack instead of recursion to perform DFS.

Graph Representation
0
/ \
1 2
/ \ \
3 4 4

Adjacency Matrix
0 1 2 3 4
0 [0, 1, 1, 0, 0]
1 [1, 0, 0, 1, 1]
2 [1, 0, 0, 0, 1]
3 [0, 1, 0, 0, 0]
4 [0, 1, 1, 0, 0]

C Code for DFS Using Stack


#include <stdio.h>
#include <stdlib.h>

#define MAX 5

int graph[MAX][MAX] = {0};


int visited[MAX] = {0};
int stack[MAX];
int top = -1;

void push(int vertex) { stack[++top] = vertex; }


int pop() { return stack[top--]; }

void DFS(int start) {


push(start);
visited[start] = 1;
printf("Depth First Search Order: ");
while (top != -1) {
int vertex = pop();
printf("%d ", vertex);
for (int i = MAX - 1; i >= 0; i--) {
if (graph[vertex][i] == 1 && !visited[i]) {
push(i);
visited[i] = 1;
}
}
}
printf("\n");
}

int main() {
graph[0][1] = 1; graph[1][0] = 1;
graph[0][2] = 1; graph[2][0] = 1;
graph[1][3] = 1; graph[3][1] = 1;
graph[1][4] = 1; graph[4][1] = 1;
graph[2][4] = 1; graph[4][2] = 1;

printf("DFS Traversal starting from vertex 0:\n");


DFS(0);

return 0;
}

Step-by-Step Execution
| Step | Stack (Top -> Bottom) | Visited Nodes | Output |
|------|----------------------|---------------|--------|
| 1 | 0 | {0} | |
| 2 | 2, 1 | {0,1,2} | |
| 3 | 2 | {0,1,2,3} | 3 |
| 4 | 2, 4 | {0,1,2,3,4} | 4 |
| 5 | 2 | {0,1,2,3,4} | 2 |
| 6 | Empty | {0,1,2,3,4} | 0 1 3 4 2 |

Final Output
DFS Traversal starting from vertex 0:
0 1 3 4 2

You might also like