Welcome to our deep dive into C Graph Algorithms! In this comprehensive guide, we'll explore various algorithms used in graph theory, focusing on practical applications and real-world examples. Let's get started!
<a name="intro"></a>
A graph is a non-linear data structure consisting of nodes (also known as vertices) and edges. It's a powerful tool for modeling relationships and connections between objects in various domains, such as social networks, computer networks, and artificial intelligence.
<a name="terminologies"></a>
<a name="matrix-list"></a>
Graphs can be represented using two main data structures: Adjacency Matrix and Adjacency List.
Adjacency Matrix: A two-dimensional array, where each cell represents whether there is an edge between two nodes or not.
Adjacency List: An array of linked lists, where each linked list contains the nodes that are adjacent to a particular node.
<a name="dfs"></a>
Depth-First Search (DFS) is a popular graph traversal algorithm that explores as far as possible along each branch before backtracking.
<a name="dfs-algorithm"></a>
<a name="dfs-recursive"></a>
#include <stdio.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];
void dfsRecursive(int node, int vertices) {
visited[node] = 1;
printf("Visiting vertex %d\n", node);
for (int i = 0; i < vertices; i++) {
if (graph[node][i] && !visited[i]) {
dfsRecursive(i, vertices);
}
}
}<a name="dfs-iterative"></a>
#include <stdio.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int stack[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];
int vertices, edges;
void dfsIterative(int node) {
stack[0] = node;
int top = 0;
visited[node] = 1;
while (top > 0) {
int currentNode = stack[top - 1];
top--;
printf("Visiting vertex %d\n", currentNode);
for (int i = 0; i < vertices; i++) {
if (graph[currentNode][i] && !visited[i]) {
stack[++top] = i;
visited[i] = 1;
break;
}
}
if (top == 0) {
if (stack[top] != node) {
stack[++top] = stack[top - 1];
}
}
}
}<a name="dfs-quiz"></a>
What is the main goal of Depth-First Search (DFS)?
<a name="bfs"></a>
Breadth-First Search (BFS) is another graph traversal algorithm that explores all nodes at the current depth level before moving to the next level.
<a name="bfs-algorithm"></a>
<a name="bfs-iterative"></a>
#include <stdio.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int queue[MAX_VERTICES];
int front = 0, rear = -1;
int graph[MAX_VERTICES][MAX_VERTICES];
int vertices, edges;
void enqueue(int node) {
if (rear == MAX_VERTICES - 1) {
printf("Queue is full.\n");
return;
}
queue[++rear] = node;
}
int dequeue() {
if (front > rear) {
printf("Queue is empty.\n");
return -1;
}
return queue[front++];
}
void bfsIterative(int node) {
visited[node] = 1;
printf("Visiting vertex %d\n", node);
enqueue(node);
while (front <= rear) {
int currentNode = dequeue();
for (int i = 0; i < vertices; i++) {
if (graph[currentNode][i] && !visited[i]) {
visited[i] = 1;
printf("Visiting vertex %d\n", i);
enqueue(i);
}
}
}
}<a name="bfs-quiz"></a>
What is the main goal of Breadth-First Search (BFS)?
<a name="mst"></a>
A Minimum Spanning Tree (MST) is a tree that connects all vertices in a graph with the minimum total edge weight.
<a name="kruskal"></a>
Kruskal's Algorithm builds an MST by selecting the minimum-weight edges in non-decreasing order and adding them to the tree incrementally.
<a name="prims"></a>
Prim's Algorithm builds an MST by starting with an arbitrary vertex and adding the minimum-weight edge connecting the tree to the remaining graph incrementally.
<a name="mst-quiz"></a>
What is a Minimum Spanning Tree (MST)?
<a name="shortest-path"></a>
Shortest Path algorithms find the shortest path between two nodes or all pairs of nodes in a graph.
<a name="dijkstra"></a>
Dijkstra's Algorithm finds the shortest path from a single source node to all other nodes in a graph.
<a name="floyd-warshall"></a>
Floyd-Warshall Algorithm finds the shortest path between all pairs of nodes in a graph.
<a name="shortest-path-quiz"></a>
What is Dijkstra's Algorithm used for?
<a name="topological-sort"></a>
Topological Sort is a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.
<a name="topological-sort-algorithm"></a>
<a name="topological-sort-implementation"></a>
#include <stdio.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int stack[MAX_VERTICES];
int graph[MAX_VERTICES][MAX_VERTICES];
int vertices, edges;
void topologicalSort(int node, int vertices) {
visited[node] = 1;
for (int i = 0; i < vertices; i++) {
if (graph[node][i] && !visited[i]) {
topologicalSort(i, vertices);
}
}
stack[vertices - visitedCount] = node;
visitedCount--;
}
void topologicalSortRecursive() {
int i;
for (i = 0; i < vertices; i++) {
visited[i] = 0;
}
visitedCount = vertices;
for (i = 0; i < vertices; i++) {
if (!visited[i]) {
topologicalSort(i, vertices);
}
}
for (i = 0; i < vertices; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}<a name="topological-sort-quiz"></a>
What is Topological Sort used for?
That's it! You now have a good understanding of various graph traversal and graph theory algorithms, such as Depth-First Search (DFS), Breadth-First Search (BFS), Minimum Spanning Tree (MST), Shortest Path algorithms (Dijkstra's and Floyd-Warshall), and Topological Sort. Keep learning and practicing to become a master in graph algorithms!