Scribd
Upload
28 views5 pages

Daa 5

The document outlines an assignment to write a C program for performing Breadth First Search (BFS) and Depth First Search (DFS) on a graph. It includes algorithms for both searches, code for implementing the graph structure and the search functions, and a complexity analysis indicating both BFS and DFS have a time complexity of O(V + E) and space complexity of O(V). The program allows user input for the number of vertices and edges, and the starting vertex for the searches.

Uploaded by

rohxn16
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
28 views5 pages

Daa 5

The document outlines an assignment to write a C program for performing Breadth First Search (BFS) and Depth First Search (DFS) on a graph. It includes algorithms for both searches, code for implementing the graph structure and the search functions, and a complexity analysis indicating both BFS and DFS have a time complexity of O(V + E) and space complexity of O(V). The program allows user input for the number of vertices and edges, and the starting vertex for the searches.

Uploaded by

rohxn16
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/ 5

ASSIGNMENT 5

PROBLEM STATEMENT
Write a program in C to perform Breadth First Search and Depth First Search.

ALGORITHM
BFS
1. Start from a selected node (source).
2. Mark the node as visited and enqueue it.
3. While the queue is not empty:
 Dequeue a node from the front of the queue.
 Process the node.
 Enqueue all unvisited neighbours of the node and mark them as visited.
DFS
1. Start from a selected node (source).
2. Mark the node as visited.
3. Process the node.
4. For each unvisited neighbour, recursively perform DFS.

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

#define MAX 100

struct Graph {
int numVertices;
int adj[MAX][MAX];
};

struct Graph* createGraph(int vertices) {


struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;

for (int i = 0; i < vertices; i++) {


for (int j = 0; j < vertices; j++) {
graph->adj[i][j] = 0;
}
}
return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {


graph->adj[src][dest] = 1;
graph->adj[dest][src] = 1;
}

void DFSUtil(struct Graph* graph, int vertex, int visited[]) {


visited[vertex] = 1;
printf("%d ", vertex);

for (int i = 0; i < graph->numVertices; i++) {


if (graph->adj[vertex][i] == 1 && !visited[i]) {
DFSUtil(graph, i, visited);
}
}
}

void DFS(struct Graph* graph, int startVertex) {


int visited[MAX] = {0};
printf("DFS Traversal starting from vertex %d:\n", startVertex);
DFSUtil(graph, startVertex, visited);
printf("\n");
}

void BFS(struct Graph* graph, int startVertex) {


int visited[MAX] = {0};
int queue[MAX], front = 0, rear = 0;

visited[startVertex] = 1;
queue[rear++] = startVertex;

printf("BFS Traversal starting from vertex %d:\n", startVertex);


while (front < rear) {
int currentVertex = queue[front++];
printf("%d ", currentVertex);

for (int i = 0; i < graph->numVertices; i++) {


if (graph->adj[currentVertex][i] == 1 && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
printf("\n");
}

int main() {
int vertices, edges, src, dest;

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


scanf("%d", &vertices);

struct Graph* graph = createGraph(vertices);


printf("Enter the number of edges: ");
scanf("%d", &edges);

printf("Enter the edges (src dest):\n");


for (int i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}

int startVertex;
printf("Enter the starting vertex for DFS and BFS: ");
scanf("%d", &startVertex);

DFS(graph, startVertex);
BFS(graph, startVertex);

free(graph);

return 0;
}
OUTPUT

COMPLEXITY ANALYSIS
 BFS:
 Time Complexity: (O(V + E))
 Space Complexity: (O(V))
 DFS:
 Time Complexity: (O(V + E))
 Space Complexity: (O(V))

You might also like