Scribd
Upload
6 views

8. Implement Depth First Search Graph Traversal technique

The document outlines an experiment aimed at implementing the Depth First Search (DFS) graph traversal technique using C programming. It describes the DFS approach, provides a code implementation using an adjacency matrix, and details the process for creating a graph with user-defined edges and vertices. The conclusion states that the DFS technique was successfully implemented with 11 edges and 10 vertices.

Uploaded by

tuba.khan7575
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
6 views

8. Implement Depth First Search Graph Traversal technique

The document outlines an experiment aimed at implementing the Depth First Search (DFS) graph traversal technique using C programming. It describes the DFS approach, provides a code implementation using an adjacency matrix, and details the process for creating a graph with user-defined edges and vertices. The conclusion states that the DFS technique was successfully implemented with 11 edges and 10 vertices.

Uploaded by

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

EXPERIMENT NO.

8
Aim: Implement Depth First Search Graph Traversal technique.

LO:LO4: Students will be able to select appropriate searching techniques for given problems

Software: ‘C’ Programming

Theory: There are many ways to traverse a graph. We focus on depth-first. This approach seeks a
solution by going to the nodes furthest from the starting point.

Depth First Search is a graph traversal technique. The source is the first node to be visited, and then
the we traverse as far as possible from each branch, backtracking when the last node of that branch
has been visited. Here is the C implementation of Depth First Search using the Adjacency Matrix
representation of graph.

The example graph we use for our program is,

Program:

#include <stdio.h>

#include <stdlib.h>

/* ADJACENCY MATRIX */

int source,V,E,time,visited[20],G[20][20];

void DFS(int i)

{
int j;

visited[i]=1;

printf(" %d->",i+1);

for(j=0;j<V;j++)

if(G[i][j]==1&&visited[j]==0)

DFS(j);

int main()

int i,j,v1,v2;

printf("\t\t\tGraphs\n");

printf("Enter the no of edges:");

scanf("%d",&E);

printf("Enter the no of vertices:");

scanf("%d",&V);

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

for(j=0;j<V;j++)

G[i][j]=0;

/* creating edges :P */

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

printf("Enter the edges (format: V1 V2) : ");

scanf("%d%d",&v1,&v2);

G[v1-1][v2-1]=1;
}

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

for(j=0;j<V;j++)

printf(" %d ",G[i][j]);

printf("\n");

printf("Enter the source: ");

scanf("%d",&source);

DFS(source-1);

return 0;

Output:

Conclusion: We have implemented Depth First Search Graph Traversal technique using 11 edges
and 10 vertices.

You might also like