C Online Compiler
Example: Topological Sort using DFS-based Algorithm in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Topological Sort using DFS-based Algorithm #include <stdio.h> #include <stdlib.h> // For malloc, free #include <stdbool.h> // For bool #define MAX_NODES 100 // Structure for an adjacency list node struct AdjNode { int dest; struct AdjNode* next; }; // Structure for the graph struct GraphDFS { int numVertices; struct AdjNode** adjLists; // Array of linked lists int* visited; // 0: unvisited, 1: visiting (in recursion stack), 2: visited }; // Structure for a stack struct Stack { int* arr; int top; int capacity; }; // Function to create an adjacency list node struct AdjNode* createAdjNodeDFS(int dest) { struct AdjNode* newNode = (struct AdjNode*)malloc(sizeof(struct AdjNode)); newNode->dest = dest; newNode->next = NULL; return newNode; } // Function to create a graph of 'vertices' number of nodes struct GraphDFS* createGraphDFS(int vertices) { struct GraphDFS* graph = (struct GraphDFS*)malloc(sizeof(struct GraphDFS)); graph->numVertices = vertices; graph->adjLists = (struct AdjNode**)malloc(vertices * sizeof(struct AdjNode*)); graph->visited = (int*)calloc(vertices, sizeof(int)); // Initialize all to 0 (unvisited) for (int i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; } return graph; } // Function to add an edge from src to dest void addEdgeDFS(struct GraphDFS* graph, int src, int dest) { struct AdjNode* newNode = createAdjNodeDFS(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; } // Stack functions struct Stack* createStack(int capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->capacity = capacity; stack->top = -1; stack->arr = (int*)malloc(capacity * sizeof(int)); return stack; } bool isEmpty(struct Stack* stack) { return stack->top == -1; } void push(struct Stack* stack, int item) { if (stack->top == stack->capacity - 1) { // Stack overflow, for simplicity in tutorial, we assume enough capacity return; } stack->arr[++stack->top] = item; } int pop(struct Stack* stack) { if (isEmpty(stack)) { // Stack underflow return -1; // Or handle error appropriately } return stack->arr[stack->top--]; } // Recursive DFS function for topological sort bool dfsTopologicalSort(struct GraphDFS* graph, int u, struct Stack* stack, bool* hasCycle) { graph->visited[u] = 1; // Mark as visiting (GRAY) struct AdjNode* temp = graph->adjLists[u]; while (temp != NULL) { int v = temp->dest; if (graph->visited[v] == 1) { // If neighbor is currently visiting, it's a back-edge (cycle) *hasCycle = true; return false; // Cycle detected } if (graph->visited[v] == 0) { // If neighbor is unvisited (WHITE) if (!dfsTopologicalSort(graph, v, stack, hasCycle)) { return false; // Propagate cycle detection } } temp = temp->next; } graph->visited[u] = 2; // Mark as visited (BLACK) - finished processing this node and its descendants push(stack, u); // Push to stack after all descendants are processed return true; } // Function to perform topological sort using DFS-based algorithm void topologicalSortDFS(struct GraphDFS* graph) { struct Stack* stack = createStack(graph->numVertices); bool hasCycle = false; for (int i = 0; i < graph->numVertices; i++) { if (graph->visited[i] == 0) { // If unvisited if (!dfsTopologicalSort(graph, i, stack, &hasCycle)) { break; // Cycle detected, no need to continue } } } if (hasCycle) { printf("Graph contains a cycle. Topological Sort not possible.\n"); } else { printf("Topological Sort (DFS-based Algorithm): "); while (!isEmpty(stack)) { printf("%d ", pop(stack)); } printf("\n"); } free(stack->arr); free(stack); } // Function to free graph memory void freeGraphDFS(struct GraphDFS* graph) { for (int i = 0; i < graph->numVertices; i++) { struct AdjNode* temp = graph->adjLists[i]; while (temp != NULL) { struct AdjNode* toFree = temp; temp = temp->next; free(toFree); } } free(graph->adjLists); free(graph->visited); free(graph); } int main() { // Example 1: Graph with 6 vertices and 6 edges // Dependencies: A->B, A->C, B->D, C->D, E->F (using 0-indexed: 0->1, 0->2, 1->3, 2->3, 4->5) int numVertices1 = 6; struct GraphDFS* graph1 = createGraphDFS(numVertices1); addEdgeDFS(graph1, 0, 1); // A -> B addEdgeDFS(graph1, 0, 2); // A -> C addEdgeDFS(graph1, 1, 3); // B -> D addEdgeDFS(graph1, 2, 3); // C -> D addEdgeDFS(graph1, 4, 5); // E -> F topologicalSortDFS(graph1); // Expected: 4 0 2 1 3 5 or 4 0 1 2 3 5 etc. freeGraphDFS(graph1); printf("\n"); // Example 2: Graph with a cycle (0->1, 1->2, 2->0) int numVertices2 = 3; struct GraphDFS* graph2 = createGraphDFS(numVertices2); addEdgeDFS(graph2, 0, 1); addEdgeDFS(graph2, 1, 2); addEdgeDFS(graph2, 2, 0); // Creates a cycle topologicalSortDFS(graph2); // Expected: "Graph contains a cycle..." freeGraphDFS(graph2); return 0; }
Output
Clear
ADVERTISEMENTS