C Programming data structures Topological Sorting Step by step Implementation and Top 10 Questions and Answers
 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    Last Update: April 01, 2025      21 mins read      Difficulty-Level: beginner

C Programming: Data Structures - Topological Sorting

Topological sorting is a fundamental concept in computer science, particularly in graph theory. It is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering. Topological sorting has several practical applications, including scheduling tasks where certain tasks must be completed before others and resolving dependencies in software projects.

In this article, we will explore topological sorting in detail, including its importance, algorithms to perform it, and a sample implementation in C programming.

Importance of Topological Sorting

  1. Scheduling Tasks: Topological sorting can be used to determine an order to perform tasks or events that have dependencies. This is often seen in project management and workflow scheduling.
  2. Course Prerequisites: In educational institutions, topological sorting can help in scheduling courses where some courses need to be completed before others.
  3. Dependency Resolution: In software engineering, topological sorting is used in resolving dependencies while compiling source files.
  4. Data Processing: In data processing pipelines, topological sorting ensures the correct order of data processing steps.

Algorithms for Topological Sorting

The primary algorithms for topological sorting are Kahn's algorithm and Depth-First Search (DFS).

Kahn's Algorithm

Kahn's algorithm uses the concept of in-degrees (the number of edges directed towards a vertex) to perform topological sorting. The algorithm works as follows:

  1. Compute the in-degree of each vertex.
  2. Add all nodes with zero in-degree to a queue.
  3. While the queue is not empty, repeat the following:
    • Dequeue a node from the queue and add it to the topological ordering.
    • For each neighbor of the dequeued node, reduce their in-degree by one.
    • If a neighbor’s in-degree becomes zero, add it to the queue.
  4. If the topological ordering contains all vertices, then the graph has no cycles; otherwise, the graph has a cycle.

Complexity: O(V + E), where V is the number of vertices and E is the number of edges.

Depth-First Search (DFS) Algorithm

The DFS-based algorithm for topological sorting works as follows:

  1. Perform a DFS traversal of the graph, keeping track of visited nodes.
  2. For each visited node, when you back out from the node in the DFS traversal, add it to the beginning of the topological ordering.
  3. Continue until all nodes have been visited.

Complexity: O(V + E), where V is the number of vertices and E is the number of edges.

Implementation in C

Below is a simple implementation using the DFS-based algorithm for topological sorting.

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

// Define a node in adjacency list
typedef struct Node {
    int value;
    struct Node* next;
} Node;

// Define a graph
typedef struct {
    int numVertices;
    Node** adjList;
    bool* visited;
} Graph;

// Create a node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjList = (Node**)malloc(vertices * sizeof(Node*));
    graph->visited = (bool*)malloc(vertices * sizeof(bool));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjList[i] = NULL;
        graph->visited[i] = false;
    }
    return graph;
}

// Add an edge to a graph
void addEdge(Graph* graph, int src, int dest) {
    // Add edge from src to dest
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

// Depth-First Search (DFS)
void DFS(Graph* graph, int vertex, int* stack, int* top) {
    graph->visited[vertex] = true;

    // Recursive call to the adjacent vertices
    Node* adjList = graph->adjList[vertex];
    while(adjList != NULL) {
        int connectedVertex = adjList->value;
        if(!graph->visited[connectedVertex]) {
            DFS(graph, connectedVertex, stack, top);
        }
        adjList = adjList->next;
    }
    stack[*top] = vertex;
    (*top)++;
}

// Topological Sort
void topologicalSort(Graph* graph) {
    int stack[graph->numVertices];
    int top = 0;

    // Call DFS for all vertices
    int i;
    for (i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            DFS(graph, i, stack, &top);
        }
    }

    // Print contents of stack
    printf("Topological Sort:\n");
    for (i = top - 1; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

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);

    topologicalSort(graph);

    return 0;
}

Explanation of the Code

  1. Structures and Functions:

    • Node structure: Represents a node in the adjacency list.
    • Graph structure: Represents a graph containing an array of adjacency lists and an array of visited nodes.
    • createNode(): Allocates memory for and returns a newNode.
    • createGraph(): Allocates memory for and returns a graph.
    • addEdge(): Adds a directed edge between two vertices.
    • DFS(): Recursive Depth-First Search function used to visit all nodes.
    • topologicalSort(): Uses the DFS function to determine the topological order and stores it in the stack.

  2. Graph Initialization and Operations:

    • A graph is created with 6 vertices (0 to 5).
    • Directed edges are added between the vertices.
    • The topologicalSort() function is called, which uses the DFS to generate and print the topological order.

Conclusion

Topological sorting is a critical concept in computer science with various applications in fields like scheduling, dependency resolution, and data processing. The DFS-based algorithm is commonly used due to its efficiency and simplicity, and it is easily implemented in C as shown in the above example. Understanding and implementing topological sorting can greatly enhance one's problem-solving skills in complex scenarios involving directed acyclic graphs.

C Programming: Data Structures - Topological Sorting

Introduction

Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge ( u \to v ), vertex ( u ) comes before ( v ) in the ordering. Topological sorting is useful in scenarios like scheduling tasks where certain tasks must be completed before others can start.

In this tutorial, we'll develop a simple application using C that implements topological sorting on a DAG. We will cover:

  1. Frontend: A basic command-line interface (CLI).
  2. Backend: Implementing topological sorting using C.
  3. Data Flow: Managing how data is handled from input to output.
  4. Running the Application: A step-by-step guide for beginners.

Step 1: Setting Up Your Environment

Before diving into code, ensure you have the necessary tools installed:

  • C Compiler: GCC (GNU Compiler Collection) is commonly used.
  • Text Editor or IDE: Visual Studio Code, Sublime Text, Code::Blocks, etc.

You can install GCC using your package manager. For example, on Ubuntu:

sudo apt-get install gcc

Step 2: Understanding the Algorithm

The process of topological sorting involves:

  1. Constructing the graph.
  2. Calculating the in-degree (number of incoming edges) of each vertex.
  3. Using a queue to store all nodes with zero in-degrees.
  4. Processing the nodes one at a time from the queue, reducing the in-degree of connected nodes, and adding them to the queue when their in-degree becomes zero.
  5. The order in which nodes are processed represents one valid topological sort.

Step 3: Backend Implementation in C

3.1 Creating a Representation of the Graph

We'll use an adjacency list to represent the graph.

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

struct Node {
    int dest;
    struct Node* next;
};

struct AdjList {
    struct Node *head; 
}; 

struct Graph {
    int V;
    struct AdjList* array;
};

struct Node* newAdjListNode(int dest);
struct Graph* createGraph(int V);
void addEdge(struct Graph* graph, int src, int dest); 
void topologicalSortUtil(int v, int visited[], int stack[], struct Graph* graph);
void topologicalSort(struct Graph* graph);

3.2 Defining Functions

Allocating Memory for Nodes and Graph
struct Node* newAdjListNode(int dest) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

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));

    int i;
    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}
Adding Edges
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}
Topological Sorting Utility Function

A recursive function to do DFS starting from v.

void topologicalSortUtil(int v, int visited[], int stack[], struct Graph* graph) {
    visited[v] = 1;
    
    struct Node* node = graph->array[v].head;
    
    while(node) {
        if(!visited[node->dest])
            topologicalSortUtil(node->dest, visited, stack, graph);
        
        node = node->next;
    }
    
    stack[++index] = v; // Add current vertex to stack which stores result
}
Topological Sorting Function

This function uses a recursive DFS to generate the topological sort of the graph.

int index = -1;

void topologicalSort(struct Graph* graph) {
    int *stack = (int*) malloc(graph->V * sizeof(int));
    int i;  
    for (i = 0; i < graph->V; i++)
        visited[i] = 0;

    for (i = 0; i < graph->V; i++)
        if (visited[i] == 0)
            topologicalSortUtil(i, visited, stack, graph);

    printf("Topological Sort:\n");
    for (i = index; i >= 0; i--)
        printf("%d ", stack[i]);
        
    printf("\n");

}

Step 4: Frontend Setup (Command-Line Interface)

4.1 Main Function

Here’s how the main function ties everything together:

int main()
{
    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("Constructed the following graph\n");
    printf("Edges: (source, destination)\n");
    printf("5 -> 2\n5 -> 0\n4 -> 0\n4 -> 1\n2 -> 3\n3 -> 1\n");
    
    topologicalSort(graph);
 
    return 0;
}

Step 5: Data Flow

The data flow in this application is as follows:

  1. Input: The user indirectly provides data by hardcoding the number of vertices and edges in the main() function.
  2. Process:
    • The graph is constructed using adjacency lists.
    • Topological sorting is performed using a DFS approach.
  3. Output: The sorted order of vertices, printed to the console.

Step 6: Running the Application

To compile and run the application, follow these steps:

  1. Save the code in a file, e.g., topsort.c.
  2. Open your terminal and navigate to the directory containing topsort.c.
  3. Compile the program using GCC: 
    gcc topsort.c -o topsort
  4. Run the generated binary: 
    ./topsort

Conclusion

This tutorial has provided an overview of implementing topological sorting in C, including setting up a graph, performing the sorting, and creating a simple CLI application to demonstrate the functionality.

While the frontend here is very basic, it can be extended using GUI frameworks like GTK or Qt (though this would complicate the implementation), or the application can be further improved by adding support for dynamic input from the user via the command line or even through a web interface.

By following these steps, beginners should have a foundational understanding of graph theory, topological sorting, and C programming practices.

Certainly! Here's a detailed explanation of the "Top 10 Questions and Answers" related to Topological Sorting in C Programming with regard to Data Structures:

1. What is Topological Sorting?

Answer: Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of all vertices such that for every directed edge u → v, vertex u comes before vertex v in the ordering. In simpler terms, it is an ordering where you process all nodes in such a way that you can visit a node only after you have visited all its dependencies (incoming edges). This is particularly useful in task scheduling and prerequisites resolution in academic settings.

2. What are the Conditions for Applying Topological Sort?

Answer: Topological sorting can be applied only on Directed Acyclic Graphs (DAGs). If the graph contains cycles, a topological sort is not possible because there is no linear ordering where every edge u → v has u coming before v. In a DAG, at least one node exists with zero incoming degree, acting as a starting point for the topological sort.

3. Can a topologically sorted graph have more than one valid solution?

Answer: Yes, a DAG can have multiple valid topological sorts. For example, given a graph with three nodes A, B, and C, and only one edge A → B, both A, B, C and A, C, B are valid topological sorts if there is no edge connecting A directly or indirectly to C, and if C does not depend on either A or B.

4. What are the algorithms used for performing topological sorting?

Answer: There are two primary algorithms used for topological sorting:

  • Kahn's Algorithm: An iterative breadth-first algorithm using a queue and indegree concept.
  • Depth First Search (DFS) Algorithm: A recursive depth-first algorithm that uses a visited stack to store elements in reverse order of post-order completion.

5. How does Kahn’s Algorithm work for topological sorting?

Answer: Kahn’s Algorithm performs topological sorting for a DAG using a breadth-first approach:

  1. Compute Indegree: Calculate the number of incoming edges for each vertex in the graph.
  2. Initialize Queue: Enqueue all vertices with an indegree of zero into a queue. These vertices have no dependencies and can be processed first.
  3. Process Vertices: Dequeue a vertex from the front of the queue, insert it into the topological order, and reduce the indegree of its adjacent vertices by one. If any adjacent vertex's indegree becomes zero, enqueue it.
  4. Repeat Step 3: Continue this process until all vertices have been processed.
  5. Check Cycle: If the topological sort does not include all vertices (V), then the graph must have a cycle, but for a DAG, all vertices will get processed.

Here is a sample implementation in C:

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

#define MAX 100

struct Node {
    int value;
    struct Node *next;
};

void addEdge(struct Node* adj[], int s, int d) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->value = d;
    newNode->next = adj[s];
    adj[s] = newNode;
}

void topoSortKH(struct Node* adj[], int V) {
    int indegree[V] = {0}, i;
    
    // Calculate indegree of all nodes
    for (i = 0; i < V; i++) {
        struct Node *temp = adj[i];
        while (temp) {
            indegree[temp->value]++;
            temp = temp->next;
        }
    }

    // Queue implementation
    int queue[MAX], front = -1, rear = -1;
    
    // Insert 0 indegree elements into the queue
    for (i = 0; i < V; i++)
        if (indegree[i] == 0)
            queue[++rear] = i;
        
    int count = 0, v;

    // Process the queue
    while (front != rear) {
        v = queue[++front];
        printf("%d ", v);

        for (struct Node *temp = adj[v]; temp; temp = temp->next) {
            if (--indegree[temp->value] == 0)
                queue[++rear] = temp->value;
        }
        count++;
    }

    // Check if graph has a cycle
    if (count != V) {
        printf("Cycle detected.\n");
        return;
    }
}


int main() {
    int V = 6;
    struct Node* adjList[V];

    for (int i = 0; i < V; i++)
        adjList[i] = NULL;

    // Adding edges for the graph
    addEdge(adjList, 5, 2);
    addEdge(adjList, 5, 0);
    addEdge(adjList, 4, 0);
    addEdge(adjList, 4, 1);
    addEdge(adjList, 2, 3);
    addEdge(adjList, 3, 1);

    printf("Topologically Sorted Order:\n");
    topoSortKH(adjList, V);

    return 0;
}

6. How does Depth First Search (DFS) work for topological sorting?

Answer: The DFS approach is a recursive method that processes vertices by their post-order of finishing times:

  1. Perform DFS Traversal: Starting from any vertex, perform the DFS traversal.
  2. Store Post-order Finishing Times: Each time a vertex finishes, push it to a stack. The stack will implicitly store vertices according to their post-order.
  3. Reverse Stack: To get a topological sort, simply reverse the elements stored in the stack.

Here is a sample implementation using DFS in C:

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

struct Node {
    int dest;
    struct Node *next;
};

struct Stack {
    int data[MAX];
    int top;
};

struct Graph {
    int V;
    struct Node *adjList[MAX];
};

void createStack(struct Stack *S) {
    S->top = -1;
}

int isEmptyStack(struct Stack *S) {
    return S->top == -1;
}

void pushStack(struct Stack *S, int x) {
    S->data[++S->top] = x;
}

int popStack(struct Stack *S) {
    return S->data[S->top--];
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

void topoSortUtil(struct Graph* graph, int v, int visited[], struct Stack* s) {
    struct Node* adjNode = graph->adjList[v];
    visited[v] = 1;

    while (adjNode) {
        int connectedVertex = adjNode->dest;
        if (!visited[connectedVertex])
            topoSortUtil(graph, connectedVertex, visited, s);
        adjNode = adjNode->next;
    }

    pushStack(s, v);
}

void topoSortDFS(struct Graph* graph) {
    struct Stack *s = malloc(sizeof(struct Stack));
    createStack(s);
    int i, visited[graph->V];

    for (i = 0; i < graph->V; i++)
        visited[i] = 0;

    for (i = 0; i < graph->V; i++)
        if (!visited[i])
            topoSortUtil(graph, i, visited, s);

    while (!isEmptyStack(s))
        printf("%d ", popStack(s));
}


int main() {
    struct Graph *graph = malloc(sizeof(struct Graph));
    graph->V = 6;

    int i;
    for (i = 0; i < graph->V; i++)
        graph->adjList[i] = NULL;

    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("Topologically Sorted Order:\n");
    topoSortDFS(graph);

    return 0;
}

7. What are the applications of topological sorting?

Answer: Some common applications of topological sorting include:

  • Task Scheduling: Useful in project planning where tasks must be ordered based on dependencies.
  • Course Prerequisites: Organizing courses based on prerequisite requirements.
  • Data Serialization: Ensuring dependencies are resolved during serialization and deserialization processes.
  • Compiling Language Dependencies: Resolving dependencies within the source code files during compilation.
  • Event Simulation: Managing events in simulations according to sequence dependencies.

8. How do you check if a graph has a cycle when using DFS for topological sorting?

Answer: When using DFS for topological sorting, detecting a cycle can be done by checking for back edges. During the DFS traversal, maintain a recursive stack that stores all vertices being visited from the start of the DFS. If a back edge (an edge pointing to a vertex already in the recursion stack) is encountered, the graph contains a cycle.

In a DAG, it might be simpler to use the fact that topological sorting should cover all vertices. If there are still vertices left in the graph after topological sorting, a cycle exists.

int isCyclicUtil(struct Graph* graph, int v, int visited[], int recStack[]) {
    // Mark current vertex as visited and part of recursion stack
    if (recStack[v]) return 1;
    if (visited[v]) return 0;

    visited[v] = recStack[v] = 1;

    struct Node* adjNode = graph->adjList[v];

    while (adjNode) {
        int connectedVertex = adjNode->dest;
        if (isCyclicUtil(graph, connectedVertex, visited, recStack))
            return 1;
        adjNode = adjNode->next;
    }

    recStack[v] = 0;
    return 0;
}

int isCyclic(struct Graph* graph) {
    int *visited = (int*)malloc(graph->V * sizeof(int));
    int *recStack = (int*)malloc(graph->V * sizeof(int));
    int i;

    for (i = 0; i < graph->V; i++) {
        visited[i] = recStack[i] = 0;
    }

    for (i = 0; i < graph->V; i++)
        if (isCyclicUtil(graph, i, visited, recStack)) // if cycle detected, return true
            return 1;

    return 0;
}

9. Can topological sorting be used in graphs that are not acyclic?

Answer: No, topological sorting cannot be directly applied to graphs that contain cycles. The presence of a cycle means there is at least one dependency loop making it impossible to establish a linear ordering for all vertices. If you try to apply topological sorting to a cyclic graph, you may encounter infinite loops or erroneous results, as algorithms assume a Directed Acyclic Graph (DAG).

10. What is the time complexity of topological sorting using Kahn's algorithm vs. DFS algorithm?

Answer: Both Kahn's algorithm and the DFS-based topological sorting algorithm have a time complexity of O(V+E), where:

  • V represents the number of vertices (nodes).
  • E represents the number of edges between these vertices.

This is because both algorithms require processing every vertex and its associated edges exactly once.

  • Kahn's Algorithm: Maintains an indegree array, iterates over vertices, and utilizes a queue.
  • DFS Algorithm: Uses a visited and recursive stack array.

The space complexity in both cases also depends on storing the adjacency list, vertices, and some auxiliary structures. So, it can be considered O(V+E) as well.

Summary:

Understanding topological sorting is crucial for many applications involving task scheduling or resolving dependencies. By leveraging Kahn's algorithm and DFS, developers can effectively manage the linear ordering required in DAGs, avoiding potential pitfalls related to cycle detection and incorrect ordering. Both algorithms have similar efficiency, making them suitable choices depending on specific requirements and implementation nuances.

References:

Feel free to reach out if you need more details or examples for any of these concepts!