Scribd
Upload
1 views2 pages

Topological Sort

The document presents a C program that implements topological sorting of a directed acyclic graph (DAG) using an adjacency matrix. It reads the number of vertices and their connections, computes the indegree of each vertex, and processes them in a queue to ensure a lexicographically smallest order. If a cycle is detected, it outputs an error message; otherwise, it prints the topological order of the vertices.

Uploaded by

Kavitha S Assistant Professor
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views2 pages

Topological Sort

The document presents a C program that implements topological sorting of a directed acyclic graph (DAG) using an adjacency matrix. It reads the number of vertices and their connections, computes the indegree of each vertex, and processes them in a queue to ensure a lexicographically smallest order. If a cycle is detected, it outputs an error message; otherwise, it prints the topological order of the vertices.

Uploaded by

Kavitha S Assistant Professor
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

TOPOLOGICAL SORT

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

#define MAX 100

// Simple queue structure


int queue[MAX];
int front = 0, rear = -1;

// Function to enqueue an element


void enqueue(int x) {
queue[++rear] = x;
}

// Function to dequeue an element


int dequeue() {
return queue[front++];
}

// Function to check if queue is empty


int isEmpty() {
return front > rear;
}

int main() {
int n;
scanf("%d", &n);

int adj[MAX][MAX];
int indegree[MAX] = {0};

// Read adjacency matrix and compute indegree


for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
if (adj[i][j] == 1)
indegree[j]++;
}
}

// Enqueue all vertices with indegree 0


for (int i = 0; i < n; i++) {
if (indegree[i] == 0)
enqueue(i);
}

int result[MAX], count = 0;

// Process vertices in queue


while (!isEmpty()) {
// To ensure lexicographically smallest, find smallest vertex in the queue
int min_index = front;
for (int i = front + 1; i <= rear; i++) {
if (queue[i] < queue[min_index])
min_index = i;
}

// Remove smallest vertex from queue


int u = queue[min_index];

// Shift elements left to remove it properly


for (int i = min_index; i < rear; i++)
queue[i] = queue[i + 1];
rear--;

// Add to result
result[count++] = u;

// For all adjacent vertices of u, decrease their indegree


for (int v = 0; v < n; v++) {
if (adj[u][v] == 1) {
indegree[v]--;
// If indegree becomes 0, add to queue
if (indegree[v] == 0)
enqueue(v);
}
}
}

// If all vertices are not processed, graph has a cycle


if (count != n) {
printf("Cycle detected or invalid DAG\n");
return 0;
}

// Print the topological order


for (int i = 0; i < count; i++)
printf("%d ", result[i]);
printf("\n");

return 0;
}

You might also like