Scribd
Upload
10 views3 pages

C++ Topological Sort Implementation

The document provides a C/C++ program that implements a method to obtain the topological ordering of vertices in a directed graph (digraph). It includes functions for depth-first search (DFS), stack operations, and the main logic for reading graph input and performing topological sorting. The output demonstrates the topological order for a sample graph with 6 vertices and 8 edges.

Uploaded by

Veeresha Gowda Bergi
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
10 views3 pages

C++ Topological Sort Implementation

The document provides a C/C++ program that implements a method to obtain the topological ordering of vertices in a directed graph (digraph). It includes functions for depth-first search (DFS), stack operations, and the main logic for reading graph input and performing topological sorting. The output demonstrates the topological order for a sample graph with 6 vertices and 8 edges.

Uploaded by

Veeresha Gowda Bergi
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

Program 05) Design and implement C/C++ Program to obtain the Topological ordering of

vertices in a given digraph.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Define maximum number of vertices
int adj[MAX][MAX]; // Adjacency matrix
int visited[MAX]; // Visited array
int stack[MAX]; // Stack to store the topological sort
int top = -1; // Stack top
void push(int vertex)
{
stack[++top] = vertex;
}
int pop( )
{
return stack[top--];
}
void dfs(int vertex, int n)
{
int i;
visited[vertex] = 1;
for ( i = 0; i < n; i++)
{
if (adj[vertex][i] == 1 && !visited[i])
{
dfs(i, n);
}
}
push(vertex);
}
void topologicalSort(int n)
{
int i;
for ( i = 0; i < n; i++)
{
visited[i] = 0;
}

for ( i = 0; i < n; i++)


{
if (!visited[i])
{
dfs(i, n);
}
}
while (top != -1)
{
printf("%d ", pop());
}
}
int main( )
{
int n, e, start, end;
int i,j;

printf("Enter the number of vertices: ");


scanf("%d", &n);

printf("Enter the number of edges: ");


scanf("%d", &e);

// Initialize adjacency matrix


for ( i = 0; i < n; i++) {
for ( j = 0; j < n; j++)
{
adj[i][j] = 0;
}
}

// Read edges
printf("Enter the edges (start end):\n");
for ( i = 0; i < e; i++)
{
scanf("%d%d", &start, &end);
adj[start][end] = 1;
}
printf("Topological Sorting:\n");
topologicalSort(n);
getch( );
return 0;
}
OUTPUT :

Enter the number of Vertices : 6


Enter the number of edges: 8
Enter the edges (Start End):
02
03
23
25
13
14
35
45
Topological Sorting
140235

You might also like