Scribd
Upload
21 views

BFS Code AND DFS Code

The document contains code for performing breadth-first search (BFS) and depth-first search (DFS) on graphs represented using adjacency lists and adjacency matrices. The BFS code uses a queue to traverse the graph in a level-order fashion, while the DFS code performs a recursive traversal and uses global visited array to track nodes explored.

Uploaded by

Neelam Yadav Noida
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
21 views

BFS Code AND DFS Code

The document contains code for performing breadth-first search (BFS) and depth-first search (DFS) on graphs represented using adjacency lists and adjacency matrices. The BFS code uses a queue to traverse the graph in a level-order fashion, while the DFS code performs a recursive traversal and uses global visited array to track nodes explored.

Uploaded by

Neelam Yadav Noida
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/ 7

BFS Code:

#include <stdio.h>

#include <stdlib.h>

#define MAX_VERTICES 100

// Structure to represent a node in adjacency list

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int data)

struct Node* newNode

= (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

// Function to add an edge to the graph

void addEdge(struct Node* adjList[], int u, int v)

struct Node* newNode = createNode(v);

newNode->next = adjList[u];

adjList[u] = newNode;

}
// Function to perform Breadth First Search on a graph

// represented using adjacency list

void bfs(struct Node* adjList[], int vertices,

int startNode, int visited[])

// Create a queue for BFS

int queue[MAX_VERTICES];

int front = 0, rear = 0;

// Mark the current node as visited and enqueue it

visited[startNode] = 1;

queue[rear++] = startNode;

// Iterate over the queue

while (front != rear) {

// Dequeue a vertex from queue and print it

int currentNode = queue[front++];

printf("%d ", currentNode);

// Get all adjacent vertices of the dequeued vertex

// currentNode If an adjacent has not been visited,

// then mark it visited and enqueue it

struct Node* temp = adjList[currentNode];

while (temp != NULL) {

int neighbor = temp->data;

if (!visited[neighbor]) {

visited[neighbor] = 1;

queue[rear++] = neighbor;

temp = temp->next;

}
}

int main()

// Number of vertices in the graph

int vertices = 5;

// Adjacency list representation of the graph

struct Node* adjList[vertices];

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

adjList[i] = NULL;

// Add edges to the graph

addEdge(adjList, 0, 1);

addEdge(adjList, 0, 2);

addEdge(adjList, 1, 3);

addEdge(adjList, 1, 4);

addEdge(adjList, 2, 4);

// Mark all the vertices as not visited

int visited[vertices];

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

visited[i] = 0;

// Perform BFS traversal starting from vertex 0

printf(

"Breadth First Traversal starting from vertex 0: ");

bfs(adjList, vertices, 0, visited);

return 0;

}
DFS Code

// C code to implement above approach

#include <stdio.h>

#include <stdlib.h>

// Globally declared visited array

int vis[100];

// Graph structure to store number

// of vertices and edges and

// Adjacency matrix

struct Graph {

int V;

int E;

int** Adj;

};

// Function to input data of graph

struct Graph* adjMatrix()

struct Graph* G = (struct Graph*)

malloc(sizeof(struct Graph));
if (!G) {

printf("Memory Error\n");

return NULL;

G->V = 7;

G->E = 7;

G->Adj = (int**)malloc((G->V) * sizeof(int*));

for (int k = 0; k < G->V; k++) {

G->Adj[k] = (int*)malloc((G->V) * sizeof(int));

for (int u = 0; u < G->V; u++) {

for (int v = 0; v < G->V; v++) {

G->Adj[u][v] = 0;

G->Adj[0][1] = G->Adj[1][0] = 1;

G->Adj[0][2] = G->Adj[2][0] = 1;

G->Adj[1][3] = G->Adj[3][1] = 1;

G->Adj[1][4] = G->Adj[4][1] = 1;

G->Adj[1][5] = G->Adj[5][1] = 1;
G->Adj[1][6] = G->Adj[6][1] = 1;

G->Adj[6][2] = G->Adj[2][6] = 1;

return G;

// DFS function to print DFS traversal of graph

void DFS(struct Graph* G, int u)

vis[u] = 1;

printf("%d ", u);

for (int v = 0; v < G->V; v++) {

if (!vis[v] && G->Adj[u][v]) {

DFS(G, v);

// Function for DFS traversal

void DFStraversal(struct Graph* G)

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


vis[i] = 0;

for (int i = 0; i < G->V; i++) {

if (!vis[i]) {

DFS(G, i);

// Driver code

void main()

struct Graph* G;

G = adjMatrix();

DFStraversal(G);

You might also like