Scribd
Upload
2 views3 pages

DFS Lab Report

The document details the implementation of the Depth First Search (DFS) algorithm using C programming, focusing on graph traversal through recursion and stack concepts. It includes theoretical background, algorithm steps, pseudocode, and a sample C program demonstrating DFS functionality. The document also discusses time complexity and various applications of DFS in computer science.

Uploaded by

zayanfaris31
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
2 views3 pages

DFS Lab Report

The document details the implementation of the Depth First Search (DFS) algorithm using C programming, focusing on graph traversal through recursion and stack concepts. It includes theoretical background, algorithm steps, pseudocode, and a sample C program demonstrating DFS functionality. The document also discusses time complexity and various applications of DFS in computer science.

Uploaded by

zayanfaris31
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

Algorithm Lab Report

Depth First Search (DFS) using C Programming Language

1. Objective

To implement the Depth First Search (DFS) algorithm using C and understand graph traversal
using recursion and stack concepts.

2. Theory

Depth First Search (DFS) is a graph traversal technique that explores a graph by going as deep as
possible before backtracking. It uses recursion or stack (LIFO).

3. Concepts Used

• Graph – collection of vertices and edges.

• Adjacency Matrix – 2D array to represent edges.

• Visited Array – prevents revisiting nodes.

• Recursion – explores neighbors deeply.

• Stack (LIFO) – supports DFS traversal behavior.

4. DFS Algorithm Steps

• Start from source vertex.

• Mark the vertex visited.

• Print the vertex.

• Visit all unvisited adjacent vertices recursively.

• Repeat until all nodes are visited.

5. DFS Pseudocode
DFS(v):
mark v visited
print v
for each neighbor u:
if u not visited:
DFS(u)

6. C Program
#include <stdio.h>

#define MAX 10

int graph[MAX][MAX];
int visited[MAX];
int n;

void dfs(int v)
{
int i;
visited[v] = 1;
printf("%d ", v);

for(i = 0; i < n; i++)


{
if(graph[v][i] == 1 && visited[i] == 0)
{
dfs(i);
}
}
}

int main()
{
int i, j, start;

printf("Enter number of vertices: ");


scanf("%d", &n);

printf("Enter adjacency matrix:\n");

for(i = 0; i < n; i++)


for(j = 0; j < n; j++)
scanf("%d", &graph[i][j]);

for(i = 0; i < n; i++)


visited[i] = 0;

printf("Enter starting vertex: ");


scanf("%d", &start);

printf("DFS Traversal: ");


dfs(start);

return 0;
}

7. Explanation of Code

• #include → for input/output functions.

• #define MAX → maximum vertices.

• graph[][] → stores adjacency matrix.

• visited[] → tracks visited nodes.

• dfs() → recursive DFS traversal function.

• visited[v] = 1 → marks node visited.

• printf → prints node.

• for loop → checks neighbors.

• dfs(i) → recursive call for neighbor.

• main() → handles input and starts DFS.

8. Sample Input
4
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0
Start: 0

9. Sample Output
DFS Traversal: 0 1 2 3

10. Time Complexity

Time Complexity: O(V + E) where V = vertices and E = edges.

11. Applications

• Path finding

• Cycle detection

• Maze solving

• Topological sorting

• Connected components

12. Conclusion

DFS efficiently traverses graphs using recursion and stack behavior. The algorithm is simple and
widely used in computer science problems.

You might also like