Steps of Kahn's Algorithm
Calculate In-Degrees: The process starts by determining the in-degree (total number of incoming edges) for every vertex within the graph. This procedure requires looping through all edges and tallying the incoming edges for each individual vertex.
Initialize Queue: The queue is set up with vertices that possess a zero in-degree, indicating they lack dependencies and are ready for immediate processing.
Process the Queue: The algorithm proceeds by handling every vertex stored in the queue:
The vertex gets dequeued and included in the topological sequence.
For every neighboring vertex of the deleted vertex, the in-degree is reduced by one (due to the removal of an edge).
If the incoming degree of a neighboring vertex reaches zero, it gets enqueued for further processing, as it is now ready to be handled.
Verify for Cycles: Following the traversal of all vertices, the algorithm verifies whether the count of vertices appended to the topological sequence matches the overall number of vertices in the graph. If these counts do not align, it indicates the presence of a cycle within the graph, rendering a topological sorting operation unfeasible.
Approach-1: Standard Queue Implementation
Kahn's method for performing topological sorting can be executed by employing a regular queue data structure. This technique requires monitoring the in-degree of every vertex and using a queue to handle vertices that do not have any incoming edges (in other words, vertices with an in-degree of zero).
Program:
#include <stdio.h>
#include <stdlib.h>
// Define the maximum number of vertices
#define MAX 100
// Adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Graph structure
struct Graph {
int V;
struct AdjList* array;
};
// Create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
//Function to perform Kahn's algorithm for topological sorting using a queue
void topologicalSort(struct Graph* graph) {
int V = graph->V;
int* in_degree = (int*)malloc(V * sizeof(int));
for (int i = 0; i < V; i++)
in_degree[i] = 0;
// Calculate in-degrees of all vertices
for (int u = 0; u < V; u++) {
struct AdjListNode* node = graph->array[u].head;
while (node != NULL) {
in_degree[node->dest]++;
node = node->next;
}
}
// Enqueue vertices with in-degree 0
int* queue = (int*)malloc(V * sizeof(int));
int front = 0, rear = 0;
for (int i = 0; i < V; i++)
if (in_degree[i] == 0)
queue[rear++] = i;
int count = 0;
int* topOrder = (int*)malloc(V * sizeof(int));
while (front < rear) {
int u = queue[front++];
topOrder[count++] = u;
struct AdjListNode* node = graph->array[u].head;
while (node != NULL) {
if (--in_degree[node->dest] == 0)
queue[rear++] = node->dest;
node = node->next;
}
}
// Check if there was a cycle
if (count != V) {
printf("There exists a cycle in the graph\n");
return;
}
// Print topological order
for (int i = 0; i < count; i++)
printf("%d ", topOrder[i]);
printf("\n");
// Free allocated memory
free(in_degree);
free(queue);
free(topOrder);
}
// Driver program to test the above functions
int main() {
// Create a graph given in the above diagram
int V = 6;
struct Graph* graph = createGraph(V);
addEdge(graph, 5, 2);
addEdge(graph, 5, 0);
addEdge(graph, 4, 0);
addEdge(graph, 4, 1);
addEdge(graph, 2, 3);
addEdge(graph, 3, 1);
printf("Following is a Topological Sort of the given graph\n");
topologicalSort(graph);
return 0;
}
Output:
Following is a Topological Sort of the given graph
4 5 0 2 3 1
Explanation:
- Graph Representation: The graph is represented using an adjacency list. In this representation, each vertex has a list of vertices iLogic Practices to. This is a common and efficient way to represent graphs, especially when they are sparse (few edges compared to the number of vertices). The graph structure contains an array of adjacency lists, and each list corresponds to a vertex in the graph.
- Adjacency List Node: The adjacency list node structure represents an element in an adjacency list. Each node contains the destination vertex (i.e., a vertex that the current vertex points to) and a pointer to the next node in the list. This forms a linked list where each node points to the next vertex in the adjacency list.
- Graph Initialization: The graph is initialized with a given number of vertices (V). Memory is allocated for the graph structure and the array of adjacency lists. Each list is initially set to NULL, indicating that no edges have been added yet.
- Adding Edges: To add an edge from a source vertex to a destination vertex, a new adjacency list node is created with the destination vertex. This node is then inserted at the beginning of the adjacency list for the source vertex. This insertion at the beginning ensures efficient edge addition with a time complexity of O(1).
Topological Sort with Kahn's Algorithm:
Calculate In-Degrees:
An array in_degree stores each vertex's in-degree (number of incoming edges). Initially, all in-degrees are set to zero.
The process of moving through the graph involves cycling through the adjacency list of each vertex. Every neighboring vertex encountered results in an increase in its in-degree. This particular action guarantees the accurate computation of in-degrees for all vertices.
Initialize the Queue:
A queue is set up to hold vertices that have an in-degree of zero. These vertices do not rely on any other vertices and can be handled right away. All vertices with an in-degree of zero are added to the queue. This represents the first group of vertices that can be processed securely without disrupting the topological sequence.
Process the Queue:
The algorithm initiates a loop in which it continuously removes a vertex from the front of the queue. The removed vertex is then included in the topological sequence, guaranteeing its placement before any vertices related to iLogic Practices.
For every neighboring vertex of the vertex that was removed from the queue, the number of incoming edges is reduced by one. When the in-degree of an adjacent vertex reaches zero as a result, it is added to the queue. This process guarantees the sequential processing of vertices in the accurate sequence.
This process continues until all elements in the queue have been processed. Each node is handled exactly once to guarantee the inclusion of all nodes in the specified order.
- Detecting Cycles: Upon completion of processing all nodes, the algorithm verifies if the count of nodes in the ordered sequence matches the total number of nodes in the graph. A count lower than the total indicates the presence of a cycle within the graph. The existence of a cycle disrupts a valid topological arrangement, creating a scenario where no linear sequence can meet the requirements. If a cycle is identified, a notification regarding its presence is displayed by the algorithm. Otherwise, it presents the topological sequence.
- Main Function: The main function initializes a graph with a designated number of nodes (typically six nodes in this scenario). It establishes connections between nodes to represent task dependencies within the graph. Subsequently, the topologicalSort Function is invoked to execute the topological sorting process and display the outcome.
Complexity Analysis:
Time Complexity
The time complexity of Kahn's algorithm can be dissected into multiple stages:
Graph Representation Initialization:
Generating the graph and setting up the adjacency list arrays takes O(V) time, with V representing the total vertex count.
Computing In-Degrees:
Initializing the in-degree array takes O(V) time.
Determining the in-degrees requires iterating through all the graph's edges. For every vertex, we iterate through its list of adjacent vertices. The computational complexity is directly related to the combined lengths of all adjacency lists, equivalent to the number of edges (E). Consequently, this process consumes O(E) time.
Queue Initialization:
Adding all vertices with a zero in-degree involves iterating through the in-degree array once, which consumes a time complexity of O(V).
Processing the Queue:
Every single vertex is added to and removed from the queue precisely one time. The enqueue and dequeue actions of the queue each have a time complexity of O(1) per action. As there are a total of V vertices, the combined time complexity of these actions amounts to O(V).
Reducing the in-degree of neighboring vertices requires iterating through all edges once more. Every edge is handled when its initial vertex is removed from the queue, thereby decreasing the in-degree of its destination vertex. This operation has a time complexity of O(E).
Cycle Detection and Final Check:
Verifying whether the number of vertices that have been processed matches the total number of vertices requires a straightforward comparison operation, which has a constant time complexity of O(1).
By merging these stages, the total time complexity of Kahn's algorithm is calculated as: O(V)+O(E)+O(V)+O(E)+O(1)=O(V+E)
Therefore, the time complexity of Kahn's algorithm is O(V+E), where V represents the number of vertices and E represents the number of edges in the graph. This linear time complexity ensures that the algorithm is well-suited for handling large graphs.
Space Complexity
The evaluation of space complexity involves assessing the memory consumption of the data structures within the algorithm.
Graph Representation:
The graph is illustrated through an adjacency list data structure. Within the adjacency list array, there exist V lists, with E nodes distributed among them. Consequently, the space complexity for storing the adjacency list amounts to O(V + E).
In-Degree Array:
An array with a capacity of V elements is employed to store the in-degree of each vertex, requiring O(V) memory space.
Queue:
The queue holds vertices with a zero in-degree. In the most unfavorable scenario, all vertices might need to be added to the queue, leading to a space complexity of O(V).
Topological Order Array:
An array for storing the ordering of vertices topologically also necessitates O(V) memory space.
Combining these, the overall space complexity of the algorithm can be expressed as: O(V+E) + O(V) + O(V) + O(V) = O(V+E)
Therefore, the space complexity of Kahn's algorithm is O(V+E). This efficient use of memory ensures that the algorithm remains effective, even when dealing with extensive graphs.
Approach-2: Kahn's Algorithm Using Vectors
Utilizing vectors to implement Kahn's algorithm presents an alternative approach to accomplishing topological sorting. This technique deviates from the typical queue implementation by employing a vector to store the collection of vertices that possess a zero in-degree.
Program:
#include <stdio.h>
#include <stdlib.h>
// Define the maximum number of vertices
#define MAX 100
// Adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Graph structure
struct Graph {
int V;
struct AdjList* array;
};
// Create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
//Function to perform Kahn's algorithm for topological sorting using a vector
void topologicalSort(struct Graph* graph) {
int V = graph->V;
int* in_degree = (int*)malloc(V * sizeof(int));
for (int i = 0; i < V; i++)
in_degree[i] = 0;
// Calculate in-degrees of all vertices
for (int u = 0; u < V; u++) {
struct AdjListNode* node = graph->array[u].head;
while (node != NULL) {
in_degree[node->dest]++;
node = node->next;
}
}
// Vector to store vertices with in-degree 0
int* zero_in_degree = (int*)malloc(V * sizeof(int));
int zero_count = 0;
for (int i = 0; i < V; i++)
if (in_degree[i] == 0)
zero_in_degree[zero_count++] = i;
int count = 0;
int* topOrder = (int*)malloc(V * sizeof(int));
while (zero_count > 0) {
int u = zero_in_degree[--zero_count];
topOrder[count++] = u;
struct AdjListNode* node = graph->array[u].head;
while (node != NULL) {
if (--in_degree[node->dest] == 0)
zero_in_degree[zero_count++] = node->dest;
node = node->next;
}
}
// Check if there was a cycle
if (count != V) {
printf("There exists a cycle in the graph\n");
return;
}
// Print topological order
for (int i = 0; i < count; i++)
printf("%d ", topOrder[i]);
printf("\n");
// Free allocated memory
free(in_degree);
free(zero_in_degree);
free(topOrder);
}
// Driver program to test the above functions
int main() {
// Create a graph given in the above diagram
int V = 6;
struct Graph* graph = createGraph(V);
addEdge(graph, 1, 2);
addEdge(graph, 3, 0);
addEdge(graph, 4, 0);
addEdge(graph, 4, 2);
addEdge(graph, 2, 3);
addEdge(graph, 4, 1);
printf("Following is a Topological Sort of the given graph\n");
topologicalSort(graph);
return 0;
}
Output:
Following is a Topological Sort of the given graph
5 4 1 2 3 0
Explanation:
- Graph Representation The graph is represented using an adjacency list. In this representation, each vertex has a list of vertices iLogic Practices to (i.e., its outgoing edges). The graph structure contains an array of adjacency lists, with each list representing the neighbors of a vertex. This is an efficient way to represent graphs, especially when they are sparse, as it uses memory proportional to the number of edges.
- Creating and Adding Edges to the Graph The graph is initialized with a given number of vertices (V). Memory is allocated for the graph structure and the array of adjacency lists. Each list is initially set to NULL, indicating no edges have been added yet. To add an edge from a source vertex to a destination vertex, a new node representing the destination vertex is created and added to the beginning of the adjacency list for the source vertex.
- In-Degree Calculation An array in_degree is used to store the in-degree of each vertex. The in-degree of a vertex is the number of incoming edges it has. Initially, the in-degree of all vertices is set to zero. The algorithm then traverses the adjacency list of each vertex. For each vertex iLogic Practices to, the corresponding in-degree is incremented. This step ensures that the in-degrees of all vertices are accurately calculated.
- Initializing the Vector for Zero In-Degree Vertices A vector zeroindegree stores vertices with an in-degree of zero. These vertices have no dependencies and can be processed immediately. The vector is initialized by scanning the in_degree array and adding all vertices with an in-degree of zero to it. This setup is crucial as it identifies the starting points for the topological sort.
- Processing the Vector The algorithm enters a loop where it processes vertices from the zeroindegree vector. The steps involved are: Vertex Processing: The last vertex from the vector is removed and added to the topological order. In-Degree Update: The algorithm traverses the adjacency list of the processed vertex, decrementing the in-degree of each adjacent vertex by one. If an adjacent vertex's in-degree becomes zero, it is added to the zeroindegree vector. This ensures that vertices are processed in the correct order, maintaining the topological sort property.
- Cycle Detection and Final Check After processing all vertices, the algorithm checks if the number of vertices in the topological order equals the total number of vertices in the graph. If the counts do not match, it indicates the presence of a cycle in the graph, as a cycle would prevent a valid topological sort. If a cycle is detected, the algorithm prints a message indicating its presence. Otherwise, it prints the topological order.
Complexity Analysis:
Time Complexity
The time complexity of Kahn's algorithm can be divided into multiple separate stages:
Graph Representation Initialization:
Generating the graph and setting up the adjacency list array demands O(V) time complexity, with V representing the total vertex count.
In-Degree Calculation:
Initializing the in-degree array takes O(V) time.
Determining the number of in-degrees requires examining every edge within the graph. When analyzing each vertex, we iterate through its list of adjacent vertices. The computational complexity for this task directly correlates with the combined lengths of all adjacency lists, ultimately equivalent to the total number of edges (E). Consequently, this process operates within O(E) time.
Setting up the Vector for Vertices with Zero In-Degree:
Scanning the array holding in-degrees of vertices just once is needed to enqueue all vertices with a zero in-degree, which consumes a time complexity of O(V).
Processing Vertices:
Each individual vertex undergoes processing precisely one time. This processing includes appending the vertex to the topological sequence and subsequently cycling through its list of adjacent vertices to adjust the in-degrees of those neighbors.
When processing each vertex u, the operation of traversing its list of adjacent vertices and reducing the in-degrees of those neighbors requires a time complexity of O(degree(u)). Here, degree(u) represents the count of edges originating from vertex u.
Thus, the overall time complexity for handling all vertices and edges is O(V) for the vertices and O(E) for the edges, resulting in a combined complexity of O(V + E).
Cycle Detection and Final Check:
Verifying whether the count of vertices in the topological sequence matches the total vertex count can be easily done through a straightforward comparison operation, which has a time complexity of O(1).
Combining these procedures, the total time complexity can be expressed as: O(V) + O(E) + O(V) + O(V + E) + O(1) = O(V + E)
Therefore, the computational efficiency of Kahn's algorithm when utilizing vectors is O(V + E).
Space Complexity
The evaluation of space complexity involves examining the amount of memory that the algorithm's data structures consume:
Graph Representation:
The graph is illustrated through an adjacency list structure. This array of adjacency lists consists of V lists, with a total of E nodes spread across all lists. Consequently, the space complexity needed for the adjacency list amounts to O(V + E).
In-Degree Array:
An array with a length of V is employed to hold the in-degree of every vertex, requiring O(V) storage space.
Vector for Zero In-Degree Vertices:
The array zeroindegree keeps track of vertices with a zero in-degree. In the worst scenario, all vertices might need to be included in the array, leading to a space complexity of O(V).
Topological Order Array:
An array for storing the ordering of vertices topologically also necessitates O(V) memory space.
Combining these, the overall space complexity of the algorithm can be expressed as: O(V+E)+O(V)+O(V)+O(V)=O(V+E)
Therefore, Kahn's algorithm employing vectors exhibits a space complexity of O(V + E). This linear spatial complexity guarantees that the algorithm remains memory-efficient, even when dealing with extensive graphs.