Detailed Explanation of Topological Sorting

1. Definition

Topological sorting is a linear ordering of the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge ( u \rightarrow v ), vertex ( u ) comes before vertex ( v ) in the ordering. In short, topological sorting takes a set of prerequisites and finds an ordering that satisfies all of them.

2. Properties of Topological Sorting

1. Directed Acyclic Graph: Only DAGs can be topologically sorted.
2. Uniqueness: A DAG may have multiple topological orderings. However, if the graph contains a cycle, topological sorting is not possible.
3. Topological Sequence: The result of a topological sort is a linear sequence of all vertices.

3. Topological Sorting Algorithms

There are two commonly used algorithms for topological sorting:

1. Kahn's Algorithm: A BFS-based approach using in-degrees.
2. DFS Algorithm: A DFS-based approach.

3.1 Kahn's Algorithm

Kahn's algorithm uses the concept of in-degrees for sorting. The specific steps are as follows:

1. Find all vertices with in-degree 0 and add them to a queue.
2. Dequeue a vertex, output it to the topological sort result, and remove all edges originating from it.
3. Update the in-degrees of the vertices pointed to by these edges. If any vertex's in-degree becomes 0, add it to the queue.
4. Repeat the above process until the queue is empty.
5. If all vertices have been output, the sort is complete; otherwise, the graph contains a cycle.

Algorithm Complexity: Time complexity is $O(V + E)$, and space complexity is $O(V)$.

3.2 DFS Algorithm

The DFS algorithm uses recursion for sorting. The specific steps are as follows:

1. Initialize all vertices as unvisited.
2. Start a DFS from any unvisited vertex.
3. During DFS, recursively visit all adjacent vertices of each vertex.
4. After visiting all adjacent vertices of a vertex, push the vertex onto a stack.
5. The final vertex sequence in the stack is the topological sort result.

Algorithm Complexity: Time complexity is $O(V + E)$, and space complexity is $O(V)$.

4. Code Implementation of Topological Sorting (C)

4.1 Kahn's Algorithm Implementation

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Adjacency list structure
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* inDegree;
} Graph;

// Create graph
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->inDegree = malloc(vertices * sizeof(int));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->inDegree[i] = 0;
    }
    return graph;
}

// Add edge
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    graph->inDegree[dest]++;
}

// Topological sort
void topologicalSort(Graph* graph) {
    int* queue = malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;
    int* topOrder = malloc(graph->numVertices * sizeof(int));
    int index = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    
    while (front < rear) {
        int currentVertex = queue[front++];
        topOrder[index++] = currentVertex;
        
        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            graph->inDegree[adjVertex]--;
            if (graph->inDegree[adjVertex] == 0) {
                queue[rear++] = adjVertex;
            }
            temp = temp->next;
        }
    }
    
    if (index != graph->numVertices) {
        printf("Graph has a cycle\n");
        return;
    }
    
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", topOrder[i]);
    }
    printf("\n");
    
    free(queue);
    free(topOrder);
}

int main() {
    Graph* graph = createGraph(6);
    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("Topological Sort of the given graph:\n");
    topologicalSort(graph);
    
    return 0;
}

4.2 DFS Algorithm Implementation

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Adjacency list structure
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

// Create graph
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// Add edge
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// DFS algorithm
void dfs(Graph* graph, int vertex, int* stack, int* top) {
    graph->visited[vertex] = 1;
    Node* temp = graph->adjLists[vertex];
    
    while (temp) {
        int adjVertex = temp->vertex;
        if (!graph->visited[adjVertex]) {
            dfs(graph, adjVertex, stack, top);
        }
        temp = temp->next;
    }
    
    stack[(*top)++] = vertex;
}

// Topological sort
void topologicalSort(Graph* graph) {
    int* stack = malloc(graph->numVertices * sizeof(int));
    int top = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            dfs(graph, i, stack, &top);
        }
    }
    
    for (int i = top - 1; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
    
    free(stack);
}

int main() {
    Graph* graph = createGraph(6);
    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("Topological Sort of the given graph:\n");
    topologicalSort(graph);
    
    return 0;
}

5. Complexity Analysis

1. Time Complexity: Both Kahn's algorithm and the DFS algorithm have a time complexity of $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. This is because each vertex and each edge is processed exactly once.
2. Space Complexity: The space complexity primarily depends on the data structures used to store the graph (adjacency list) and auxiliary data structures (such as a queue or stack). The total space complexity is $O(V + E)$.

6. Applications of Topological Sorting

Topological sorting is widely used in the following areas:

1. Compiler Construction: Determining the compilation order of code modules.
2. Project Management: Task scheduling and dependency management.
3. Data Serialization: Ensuring that dependencies are processed before the items that depend on them.

Through the above content, you can gain a better understanding of topological sorting and its implementation. If you need more detailed information or have other questions, feel free to discuss further.