Breadth First Search
#include <stdio.h>
#define MAX 10
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int vertex) {
if (rear == MAX - 1)
printf("Queue is full\n");
else {
if (front == -1)
front = 0;
rear++;
queue[rear] = vertex;
}
}
int dequeue() {
int vertex;
if (front == -1 || front > rear)
return -1;
vertex = queue[front];
front++;
return vertex;
}
int isEmpty() {
if (front == -1 || front > rear)
return 1;
return 0;
}
void BFS(int adj[MAX][MAX], int n, int start) {
int visited[MAX];
int i, current;
for (i = 0; i < n; i++)
visited[i] = 0;
enqueue(start);
visited[start] = 1;
printf("BFS Traversal: ");
while (!isEmpty()) {
current = dequeue();
printf("%d ", current);
for (i = 0; i < n; i++) {
if (adj[current][i] == 1 && visited[i] == 0) {
enqueue(i);
visited[i] = 1;
}
}
}
printf("\n");
}
int main() {
int n, i, j, start;
int adj[MAX][MAX];
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
}
}
printf("Enter starting vertex: ");
scanf("%d", &start);
BFS(adj, n, start);
return 0;
}
Enter number of vertices: 4
Enter adjacency matrix:
0110
1001
1001
0110
Enter starting vertex: 0
(0)
/ \
(1) (2)
|
(3)
BFS Traversal: 0 1 2 3
************************************************************************************************
*********
Depth First Search
#include <stdio.h>
#define MAX 10
int visited[MAX];
int adj[MAX][MAX];
int n; // Number of vertices
void DFS(int vertex) {
int i;
visited[vertex] = 1;
printf("%d ", vertex);
for (i = 0; i < n; i++) {
if (adj[vertex][i] == 1 && visited[i] == 0)
DFS(i);
}
}
int main() {
int i, j, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
for (i = 0; i < n; i++)
visited[i] = 0;
printf("Enter the starting vertex: ");
scanf("%d", &start);
printf("Depth First Search traversal starting from vertex %d:\n", start);
DFS(start);
return 0;
}
Enter number of vertices: 4
Enter the adjacency matrix:
0110
1011
1100
0100
Enter the starting vertex: 0
Depth First Search traversal starting from vertex 0:
0123
(0)
/ \
(1)---(2)
|
(3)
***********************************************************************************************
Applications of Spanning Trees
Network Design (Minimum Cost Connection)
● Use: Designing efficient and cost-effective networks — like computer,
electrical, or road networks.
● Example:
When connecting several computers (nodes) using cables (edges), a
Minimum Spanning Tree (MST) ensures all computers are connected with
minimum total cable length and no cycles.
● Algorithm Used: Kruskal’s or Prim’s algorithm.
Circuit Design and Layout
● Use: Helps in minimizing wiring and interconnections between components on
a circuit board.
● Example:
Layout design for Very-Large-Scale Integration (VLSI) chips.
Broadcasting in Computer Networks
● Use: In broadcasting or multicasting messages efficiently across a network.
● Example:
Using MST ensures that the message reaches all nodes with minimum
number of transmissions.
Urban Planning
● Use: For optimal layout of water supply, gas pipelines, or underground cabling
systems.
● Example:
Connecting various distribution points in a city with minimal total length of
pipe.
*****************************************************************************************
Main applications of Dijkstra’s Algorithm (Shortest Path Algorithm):
GPS Navigation and Route Planning
● Use: To find the shortest path between two locations on a map.
● Example: Google Maps or any GPS device uses Dijkstra’s algorithm to find
the fastest route between cities or places.
Network Routing (Data Communication)
● Use: To determine the shortest and most efficient route for data packets in
computer networks.
● Example: Internet routing protocols like OSPF (Open Shortest Path First) use
Dijkstra’s algorithm to find optimal paths between routers.
Transportation and Traffic Systems
● Use: For planning and managing road, railway, and airline networks.
● Example: Finding the shortest route for trains, or optimal bus route scheduling
between stops.
Urban Infrastructure Planning
● Use: For planning shortest water pipelines, power lines, or underground
cables.
● Example: Finding minimal cost connections from a central plant to multiple
delivery points.