Graph traversal refers to visiting all the nodes (vertices) in a graph systematically. Common traversal methods include:
- Breadth-First Search (BFS): Explores vertices level by level.
- Depth-First Search (DFS): Explores as far as possible along a branch before backtracking.
Shortest path algorithms find the shortest path between nodes in a weighted graph:
- Dijkstra’s Algorithm: Single-source shortest path for graphs with non-negative weights.
- Bellman-Ford Algorithm: Handles graphs with negative weights.
- Floyd-Warshall Algorithm: Finds shortest paths between all pairs of nodes.
1. Breadth-First Search (BFS)
BFS is used for:
- Traversal of graphs.
- Finding the shortest path in unweighted graphs.
C Code for BFS:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int queue[MAX];
int front = -1, rear = -1;
// Add to queue
void enqueue(int value) {
if (rear == MAX – 1) return;
if (front == -1) front = 0;
queue[++rear] = value;
}
// Remove from queue
int dequeue() {
if (front == -1 || front > rear) return -1;
return queue[front++];
}
// BFS Function
void bfs(int graph[MAX][MAX], int start, int n) {
int visited[MAX] = {0};
enqueue(start);
visited[start] = 1;
printf(“BFS Traversal: “);
while (front <= rear) {
int current = dequeue();
printf(“%d “, current);
for (int i = 0; i < n; i++) {
if (graph[current][i] == 1 && !visited[i]) {
enqueue(i);
visited[i] = 1;
}
}
}
}
int main() {
int n = 4; // Number of vertices
int graph[MAX][MAX] = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
bfs(graph, 0, n);
return 0;
}
2. Depth-First Search (DFS)
DFS is used for:
- Graph traversal.
- Detecting cycles.
C Code for DFS:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void dfs(int graph[MAX][MAX], int visited[MAX], int current, int n) {
printf(“%d “, current);
visited[current] = 1;
for (int i = 0; i < n; i++) {
if (graph[current][i] == 1 && !visited[i]) {
dfs(graph, visited, i, n);
}
}
}
int main() {
int n = 4; // Number of vertices
int graph[MAX][MAX] = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
int visited[MAX] = {0};
printf(“DFS Traversal: “);
dfs(graph, visited, 0, n);
return 0;
}
3. Dijkstra’s Algorithm
Dijkstra’s Algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative weights.
C Code for Dijkstra’s Algorithm:
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
int minDistance(int dist[], int visited[], int n) {
int min = INF, minIndex = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < min) {
min = dist[i];
minIndex = i;
}
}
return minIndex;
}
void dijkstra(int graph[MAX][MAX], int src, int n) {
int dist[MAX], visited[MAX] = {0};
for (int i = 0; i < n; i++) dist[i] = INF;
dist[src] = 0;
for (int count = 0; count < n – 1; count++) {
int u = minDistance(dist, visited, n);
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printf(“Vertex\tDistance from Source\n”);
for (int i = 0; i < n; i++) {
printf(“%d\t%d\n”, i, dist[i]);
}
}
int main() {
int n = 5;
int graph[MAX][MAX] = {
{0, 10, 0, 0, 5},
{0, 0, 1, 0, 2},
{0, 0, 0, 4, 0},
{7, 0, 6, 0, 0},
{0, 3, 9, 2, 0}
};
dijkstra(graph, 0, n);
return 0;
}
4. Bellman-Ford Algorithm
Bellman-Ford finds shortest paths from a source node even in graphs with negative weights.
C Code for Bellman-Ford:
#include <stdio.h>
#include <limits.h>
#define INF INT_MAX
#define MAX 100
void bellmanFord(int graph[MAX][3], int V, int E, int src) {
int dist[MAX];
for (int i = 0; i < V; i++) dist[i] = INF;
dist[src] = 0;
for (int i = 0; i < V – 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph[j][0];
int v = graph[j][1];
int weight = graph[j][2];
if (dist[u] != INF && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
printf(“Vertex\tDistance from Source\n”);
for (int i = 0; i < V; i++) {
printf(“%d\t%d\n”, i, dist[i]);
}
}
int main() {
int V = 5, E = 8;
int graph[MAX][3] = {
{0, 1, -1}, {0, 2, 4}, {1, 2, 3},
{1, 3, 2}, {1, 4, 2}, {3, 2, 5},
{3, 1, 1}, {4, 3, -3}
};
bellmanFord(graph, V, E, 0);
return 0;
}
5. Floyd-Warshall Algorithm
Floyd-Warshall computes shortest paths between all pairs of nodes in O(V3)O(V^3)O(V3).
C Code for Floyd-Warshall:
#include <stdio.h>
#define INF 99999
#define MAX 100
void floydWarshall(int graph[MAX][MAX], int n) {
int dist[MAX][MAX];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
printf(“Shortest distances between pairs of vertices:\n”);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF)
printf(“INF “);
else
printf(“%d “, dist[i][j]);
}
printf(“\n”);
}
}
int main() {
int n = 4;
int graph[MAX][MAX] = {
{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}
};
floydWarshall(graph, n);
return 0;
}
These algorithms serve various purposes depending on the graph type, edge weights, and the desired traversal or shortest path calculation.