Scribd
Upload
2 views3 pages

Depth First Search in Graphs

The document provides C code implementations for Depth First Search (DFS) and Breadth First Search (BFS) algorithms in directed graphs. It includes functions to initialize the graph, input edges, and perform the respective search algorithms starting from a user-defined vertex. Both algorithms utilize an adjacency matrix to represent the graph and a visited array to track visited vertices.

Uploaded by

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

Depth First Search in Graphs

The document provides C code implementations for Depth First Search (DFS) and Breadth First Search (BFS) algorithms in directed graphs. It includes functions to initialize the graph, input edges, and perform the respective search algorithms starting from a user-defined vertex. Both algorithms utilize an adjacency matrix to represent the graph and a visited array to track visited vertices.

Uploaded by

btrnareshreddy
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

Depth First Search in Graphs

#include <stdio.h>
#define MAX 100
int adj[MAX][MAX], visited[MAX];
int n;
void dfs(int v) {
printf("%d\n", v);
visited[v] = 1;
for(int i = 1; i <= n; i++) {
if(adj[v][i] == 1 && visited[i] == 0) {
dfs(i);
} }}

int main() {
int edges, src, dest, start;
printf("Enter the number of vertices : \n");
scanf("%d", &n);
printf("Enter the number of edges : \n");
scanf("%d", &edges);
// Initialize
for(int i = 1; i <= n; i++) {
visited[i] = 0;
for(int j = 1; j <= n; j++) {
adj[i][j] = 0;
} }

// Input edges (DIRECTED)


for(int i = 0; i < edges; i++) {
printf("Enter source : \n");
scanf("%d", &src);
printf("Enter destination : \n");
scanf("%d", &dest);
// Ignore invalid vertices
if(src >= 1 && src <= n && dest >= 1 && dest <= n) {
adj[src][dest] = 1; // ✅ Only one direction
} }
printf("Enter Start Vertex for DFS : \n");
scanf("%d", &start);
printf("DFS of graph : \n");

if(start >= 1 && start <= n)


dfs(start);
return 0;
}
Breadth First Search in Graph

#include <stdio.h>
#define MAX 100
int adj[MAX][MAX], visited[MAX];
int queue[MAX];
int n;
// BFS function
void bfs(int start) {
int front = 0, rear = 0;
queue[rear++] = start;
visited[start] = 1;
while(front < rear) {
int v = queue[front++];
printf("%d\n", v);
for(int i = 1; i <= n; i++) {
if(adj[v][i] == 1 && visited[i] == 0) {
queue[rear++] = i;
visited[i] = 1;
}
}
}
}

int main() {
int edges, src, dest, start;
printf("Enter the number of vertices : \n");
scanf("%d", &n);
printf("Enter the number of edges : \n");
scanf("%d", &edges);
// Initialize
for(int i = 1; i <= n; i++) {
visited[i] = 0;
for(int j = 1; j <= n; j++) {
adj[i][j] = 0;
}
}

// Input edges (DIRECTED)


for(int i = 0; i < edges; i++) {
printf("Enter source : \n");
scanf("%d", &src);
printf("Enter destination : \n");
scanf("%d", &dest);
// Ignore invalid vertices
if(src >= 1 && src <= n && dest >= 1 && dest <= n) {
adj[src][dest] = 1;
}
}
printf("Enter Start Vertex for BFS : \n");
scanf("%d", &start);
printf("BFS of graph :\n");
if(start >= 1 && start <= n)
bfs(start);
return 0;
}

You might also like