Key Concepts of Kahn’s Algorithm
- Directed Acyclic Graph (DAG): Kahn’s Algorithm can only be applied to DAGs. If the graph has cycles, it cannot be sorted topologically.
- In-degree: Each vertex has an in-degree that counts how many edges are directed toward it.
- Steps of Kahn’s Algorithm:
- Calculate the in-degree of each vertex.
- Initialize a queue with all vertices that have an in-degree of zero.
- Repeatedly remove a vertex from the queue, add it to the topological order, and decrease the in-degree of its neighbors. If a neighbor’s in-degree becomes zero, add it to the queue.
C Program for Topological Sort Using Kahn’s Algorithm
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Structure for the adjacency list node
struct Node {
int vertex;
struct Node* next;
};
// Structure for the graph
struct Graph {
int numVertices;
struct Node* adjList[MAX];
};
// Function to create a new adjacency list node
struct Node* createNode(int vertex) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
graph->adjList[i] = NULL; // Initialize adjacency list
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
}
// Function to perform topological sort using Kahn’s Algorithm
void topologicalSort(struct Graph* graph) {
int inDegree[MAX] = {0}; // Array to store in-degrees of all vertices
int topologicalOrder[MAX]; // Array to store the topological order
int index = 0;
// Calculate in-degrees of all vertices
for (int i = 0; i < graph->numVertices; i++) {
struct Node* temp = graph->adjList[i];
while (temp) {
inDegree[temp->vertex]++;
temp = temp->next;
}
}
// Initialize queue for vertices with in-degree of 0
int queue[MAX], front = 0, rear = 0;
for (int i = 0; i < graph->numVertices; i++) {
if (inDegree[i] == 0) {
queue[rear++] = i; // Enqueue vertex with in-degree 0
}
}
// Process the queue
while (front < rear) {
int currentVertex = queue[front++]; // Dequeue vertex
topologicalOrder[index++] = currentVertex; // Store in topological order
// Decrease in-degree for all neighbors
struct Node* temp = graph->adjList[currentVertex];
while (temp) {
inDegree[temp->vertex]--;
// If in-degree becomes 0, enqueue the neighbor
if (inDegree[temp->vertex] == 0) {
queue[rear++] = temp->vertex;
}
temp = temp->next; // Move to next neighbor
}
}
// Check if there was a cycle
if (index != graph->numVertices) {
printf("The graph has a cycle. Topological sort is not possible.\n");
return;
}
// Print the topological order
printf("Topological Sort: ");
for (int i = 0; i < index; i++) {
printf("%d ", topologicalOrder[i]);
}
printf("\n");
}
// Main function
int main() {
struct Graph* graph = createGraph(6); // Create a graph with 6 vertices
// Adding edges to the graph
addEdge(graph, 5, 2);
addEdge(graph, 5, 0);
addEdge(graph, 4, 0);
addEdge(graph, 4, 1);
addEdge(graph, 2, 3);
addEdge(graph, 3, 1);
// Perform topological sort
topologicalSort(graph);
return 0;
}
Explanation of the Code
- Graph Representation:
- The graph is represented using an adjacency list. Each vertex points to a list of its adjacent vertices using the
Nodestructure.
- The graph is represented using an adjacency list. Each vertex points to a list of its adjacent vertices using the
- Graph Functions:
- createNode: Creates a new node for the adjacency list.
- createGraph: Initializes a graph with a specified number of vertices.
- addEdge: Adds a directed edge from
srctodest.
- Kahn’s Algorithm:
- The
topologicalSortfunction calculates the in-degrees of all vertices and initializes a queue with vertices that have an in-degree of zero. - It processes the queue by repeatedly dequeuing a vertex, adding it to the topological order, and reducing the in-degrees of its neighbors. If a neighbor’s in-degree becomes zero, it is added to the queue.
- After processing, if the number of vertices in the topological order does not match the total number of vertices, it indicates a cycle.
- The
- Main Function:
- In the
mainfunction, we create a graph with 6 vertices and add directed edges. We then call thetopologicalSortfunction to perform the sorting and print the result.
- In the
Input and Output
Input (Edges of the graph):
The directed edges added to the graph are:
5 → 2
5 → 0
4 → 0
4 → 1
2 → 3
3 → 1
When you run the program, you will see the following output:
mathematicaCopy codeTopological Sort: 4 5 0 2 3 1
Conclusion
This program effectively implements Kahn’s Algorithm to perform a topological sort on a directed acyclic graph. It checks for cycles, ensuring that the sort can only be performed on valid DAGs. You can modify the graph structure by changing the edges to observe different topological sorts. This implementation provides a clear understanding of Kahn’s Algorithm and its applications in scheduling and task ordering problems.
