AIM:-
Implement BFT and DFT for given graph, when graph is represented by
Descrition:-
Breadth-First Traversal (BFT)
Breadth-First Traversal (BFT), also known as Breadth-First Search (BFS), is an algorithm for
traversing or searching tree or graph data structures. It starts at a given node (often called the 'root' in
the context of trees or the 'starting vertex' in graphs) and explores all its neighboring nodes at the
present depth level before moving on to nodes at the next depth level.
Depth-First Traversal (DFT)
Depth-First Traversal (DFT), also known as Depth-First Search (DFS), is an algorithm for
traversing or searching tree or graph data structures. It starts at a given node and explores as far as
possible along each branch before backtracking.
a) Adjacency Matrix
BFT:-
Program
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void BFT(int graph[MAX][MAX], int n, int start) {
int queue[MAX], front = 0, rear = -1;
int visited[MAX] = {0};
int currentNode;
queue[++rear] = start;
visited[start] = 1;
while (front <= rear) {
currentNode = queue[front++];
printf("%d ", currentNode);
for (int i = 0; i < n; i++) {
if (graph[currentNode][i] == 1 && !visited[i]) {
queue[++rear] = i;
visited[i] = 1;
int main() {
int graph[MAX][MAX], n, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("Breadth-First Traversal starting from vertex %d: ", start);
BFT(graph, n, start);
return 0;
OUTPUT:-
Enter number of vertices: 5
Enter adjacency matrix:
01100
10110
11001
01000
00100
Enter starting vertex: 0
Breadth-First Traversal starting from vertex 0: 0 1 2 3 4
Result:-
This code implements Breadth-First Traversal for a graph represented by adjacency matrix.
DFT:-
Program:-
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void DFTUtil(int graph[MAX][MAX], int n, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < n; i++) {
if (graph[v][i] == 1 && !visited[i]) {
DFTUtil(graph, n, i, visited);
void DFT(int graph[MAX][MAX], int n, int start) {
int visited[MAX] = {0};
DFTUtil(graph, n, start, visited);
int main() {
int graph[MAX][MAX], n, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("Depth-First Traversal starting from vertex %d: ", start);
DFT(graph, n, start);
return 0;
OUTPUT:-
Enter number of vertices: 5
Enter adjacency matrix:
01100
10110
11001
01000
00100
Enter starting vertex: 0
Depth-First Traversal starting from vertex 0: 0 1 2 4 3
Result:-
This code implements Depth-First Traversal for a graph represented by adjacency matrix.
b) Adjacency Lists
BFT Program:-
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Structure for adjacency list node
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// Structure for adjacency list
typedef struct Graph {
int numVertices;
Node** adjLists;
} Graph;
// Queue structure for BFT
typedef struct Queue {
int items[MAX];
int front;
int rear;
} Queue;
Node* createNode(int v) {
Node* newNode = malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
return graph;
void addEdge(Graph* graph, int src, int dest) {
// Add edge from src to dest
Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src (for undirected graph)
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
Queue* createQueue() {
Queue* q = malloc(sizeof(Queue));
q->front = -1;
q->rear = -1;
return q;
int isEmpty(Queue* q) {
return q->rear == -1;
void enqueue(Queue* q, int value) {
if (q->rear == MAX - 1) {
printf("\nQueue is full!");
} else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
int dequeue(Queue* q) {
int item;
if (isEmpty(q)) {
printf("\nQueue is empty!");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
return item;
void BFT(Graph* graph, int startVertex) {
Queue* q = createQueue();
int* visited = malloc(graph->numVertices * sizeof(int));
for (int i = 0; i < graph->numVertices; i++)
visited[i] = 0;
visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
int currentVertex = dequeue(q);
printf("%d ", currentVertex);
Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
visited[adjVertex] = 1;
enqueue(q, adjVertex);
temp = temp->next;
free(visited);
int main() {
int vertices, edges, src, dest, start;
printf("Enter number of vertices: ");
scanf("%d", &vertices);
Graph* graph = createGraph(vertices);
printf("Enter number of edges: ");
scanf("%d", &edges);
for (int i = 0; i < edges; i++) {
printf("Enter edge (src dest): ");
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("Breadth-First Traversal starting from vertex %d: ", start);
BFT(graph, start);
printf("\n");
return 0;
OUTPUT:-
Enter number of vertices: 5
Enter number of edges: 5
Enter edge (src dest): 0 1
Enter edge (src dest): 0 2
Enter edge (src dest): 1 2
Enter edge (src dest): 1 3
Enter edge (src dest): 2 4
Enter starting vertex: 0
Breadth-First Traversal starting from vertex 0: 0 1 2 3 4
Result:-
This code implements Breadth-First Traversal for a graph represented by adjacency lists. .
DFT Program;-
#include <stdio.h>
#include <stdlib.h>
// Structure for adjacency list node
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// Structure for adjacency list
typedef struct Graph {
int numVertices;
Node** adjLists;
} Graph;
Node* createNode(int v) {
Node* newNode = malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
return graph;
void addEdge(Graph* graph, int src, int dest) {
// Add edge from src to dest
Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src (for undirected graph)
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
void DFTUtil(Graph* graph, int vertex, int* visited) {
visited[vertex] = 1;
printf("%d ", vertex);
Node* temp = graph->adjLists[vertex];
while (temp) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
DFTUtil(graph, adjVertex, visited);
temp = temp->next;
void DFT(Graph* graph, int startVertex) {
int* visited = malloc(graph->numVertices * sizeof(int));
for (int i = 0; i < graph->numVertices; i++)
visited[i] = 0;
DFTUtil(graph, startVertex, visited);
free(visited);
int main() {
int vertices, edges, src, dest, start;
printf("Enter number of vertices: ");
scanf("%d", &vertices);
Graph* graph = createGraph(vertices);
printf("Enter number of edges: ");
scanf("%d", &edges);
for (int i = 0; i < edges; i++) {
printf("Enter edge (src dest): ");
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("Depth-First Traversal starting from vertex %d: ", start);
DFT(graph, start);
printf("\n");
return 0;
OUTPUT:-
Enter number of vertices: 5
Enter number of edges: 5
Enter edge (src dest): 0 1
Enter edge (src dest): 0 2
Enter edge (src dest): 1 2
Enter edge (src dest): 1 3
Enter edge (src dest): 2 4
Enter starting vertex: 0
Depth-First Traversal starting from vertex 0: 0 1 2 4 3
Result:-
This code implements Depth-First Traversal for a graph represented by adjacency lists.