Scribd
Upload
5 views1 page

LabProgram5 ADA

The document presents a C/C++ program that implements a method to obtain the topological ordering of vertices in a directed graph using Depth-First Search (DFS). It includes an adjacency matrix to represent the graph, a stack to store the topological order, and functions to perform DFS and print the order. The program prompts the user for the number of vertices and edges, and the edges themselves, before executing the algorithm.

Uploaded by

kanchanar.cse
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views1 page

LabProgram5 ADA

The document presents a C/C++ program that implements a method to obtain the topological ordering of vertices in a directed graph using Depth-First Search (DFS). It includes an adjacency matrix to represent the graph, a stack to store the topological order, and functions to perform DFS and print the order. The program prompts the user for the number of vertices and edges, and the edges themselves, before executing the algorithm.

Uploaded by

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

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

vertices in a given digraph.


#include <stdio.h>
#define MAX 20 // Maximum number of vertices
int n, m; // n = number of vertices, m = number of edges
int adj[MAX][MAX]; // Adjacency matrix representation of graph
int visited[MAX]; // Array to mark visited vertices
int stack[MAX], top = -1; // Stack to store topological order

// DFS function to visit vertices


void DFS(int v) {
visited[v] = 1; // Mark current vertex as visited
// Visit all adjacent vertices
for (int i = 0; i < n; i++) {
if (adj[v][i] == 1 && !visited[i]) {
DFS(i); // Recursive DFS call
}
}
stack[++top] = v; // Push vertex into stack after visiting all its neighbours
}

int main() {
printf("Enter number of vertices: "); // Input number of vertices
scanf("%d", &n);
printf("Enter number of edges: "); // Input number of edges
scanf("%d", &m);
printf("Enter edges (u v) meaning u -> v:\n"); // Input directed edges
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = 1; // Mark edge in adjacency matrix
}
for (int i = 0; i < n; i++) // Initialize all vertices as unvisited
visited[i] = 0;
for (int i = 0; i < n; i++) { // Perform DFS for each unvisited vertex
if (!visited[i])
DFS(i);
}
printf("Topological Order:\n"); // Print topological order by popping stack
while (top != -1)
printf("%d ", stack[top--]);
return 0;
}

You might also like