Antoun J. Yaacoub Ph.D.

Perform a topological sort using BFS traversal of a graph using an adjacency matrix.

Difficulty level

This exercise is mostly suitable for students

#include<stdio.h>
#include<stdlib.h>
#define N 20

typedef int element;

typedef struct 
{
	element data[N]; /* queue content */
	int front, length;
} queue;

 
typedef struct {
	int V;
	int E;
	int **Adj; // since we need 2 dimensional matrix
} Graph;




queue CreateQueue()
{
	queue q;
	q.front = 0; q.length=0;
	return q;
}
int isEmptyQueue(queue q)
{
	return q.length == 0;
}

int isFullQueue(queue q)
{
	return q.length ==N;
}

int EnQueue(queue *q, element e)
{
	if (isFullQueue(*q)) return 0;
	q->data[(q->front + q->length)%N] = e;
	q->length = q->length + 1;
	return 1;
}

int DeQueue(queue *q)
{
	if (isEmptyQueue(*q)) return 0;
	q->front=(q->front + 1) % N;
	q->length--;
	return 1;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.data[q.front];
	return 1;
}

 


Graph* adjacencyMatrix() {
	int i, u, v;
	Graph* G=(Graph*) malloc(sizeof(Graph));
	printf("Enter the number of Vertices: ");
	scanf("%d", &G->V);
	printf("Enter the number of Edges: ");
	scanf("%d", &G->E);
	G->Adj = (int **)malloc(G->V * sizeof(int*));
	for (u = 0; u < G->V; u++)
		G->Adj[u] = (int *)malloc(G->V * sizeof(int));

	for (u = 0; u<G->V; u++)
		for (v = 0; v<G->V; v++)
			G->Adj[u][v] = 0;
	for (i = 0; i < G->E; i++) {
		printf("Enter the edge: ");
		scanf("%d %d", &u,&v);
		// for undirected graph, set both
		G->Adj[u][v] = 1;
		// G->Adj[v][u] = 1;
	}
	return G;
}

 

void topologicalSort(Graph *G) {
	queue q, topologicalorder;
	int counter;
	int v, w;
	int *indegree;

	// Create an array to store indegrees of all 
	// vertices. Initialize all indegrees as 0. 
	indegree= (int *)malloc(G->V * sizeof(int));
	for (v = 0; v < G->V; v++)
		indegree[v] = 0;


	// Traverse adjacency lists to fill indegrees of 
	// vertices.  This step takes O(V+E) time 
	//for each edge(src,dest) in Edges
	//indegree[dest]++
	for (v = 0; v < G->V; v++)
		for (w = 0; w < G->V; w++)
			if (G->Adj[v][w] == 1)
				indegree[w]++;
 
       
	q = CreateQueue();
	topologicalorder = CreateQueue();
	// Initialize count of visited vertices 
	counter = 0;
	for (v = 0; v < G->V; v++)
		if (indegree[v]==0)
			EnQueue(&q, v);
	while (Front(q,&v)) {
		DeQueue(&q);
		++counter;
		EnQueue(&topologicalorder,v );
		// Iterate through all its neighbouring nodes 
		// of dequeued node v and decrease their in-degree 
		// by 1 
		for (w = 0; w < G->V; w++)
			if (G->Adj[v][w] == 1)
				if(--indegree[w] == 0)
					EnQueue(&q, w);

	}
	if (counter != G->V)
		printf("Graph has cycle!\n");

	while (Front(topologicalorder, &v) && DeQueue(&topologicalorder))
			printf("%d ", v);
}

void test() {
	int u, v;
	Graph *G = adjacencyMatrix();
	topologicalSort(G);
}


int main()
{
	test();
	return 0;
}

Back to the list of exercises

Looking for a more challenging exercise, try this one !!

Binary Search Tree of Events

Topological sort using BFS traversal of a graph using an adjacency matrix