Antoun J. Yaacoub Ph.D.

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

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 node {
	int vertexNumber;
	struct node * next;
} node;
typedef struct {
	int V;
	int E;
	node** Adj;  //array of linked list
} 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* adjacencyList() {
	int i, x, y;
	node * temp, *temp2;
	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 = (node **)malloc(G->V * sizeof(node));
	for (i = 0; i < G->V; i++) {
		G->Adj[i] = (node *)malloc(G->V * sizeof(node));
		G->Adj[i]->vertexNumber = i;
		G->Adj[i]->next = NULL;
	}
 
	for (i = 0; i < G->E; i++) {
		printf("Enter the edge: ");
		scanf("%d %d", &x,&y);
		temp = (node*)malloc(sizeof(node));
		temp->vertexNumber = y;
        temp->next = NULL;
        
		temp2 = G->Adj[x];
		while (temp2->next != NULL)
			temp2 = temp2->next;
		temp2->next = temp;
		
	}
	return G;
}

 

void topologicalSort(Graph *G) {
	queue q, topologicalorder;
	int counter;
	int v, w;
	int *indegree;
	node * head;

	// 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 linked lists to fill indegrees of 
	// vertices.   
	for (v = 0; v < G->V; v++)
	{
		head=G->Adj[v]->next;
		while(head)
		{
			indegree[head->vertexNumber]++;
			head=head->next;
		}
	}
       
	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 
		head=G->Adj[v]->next;
		while(head)
		{
			if(--indegree[head->vertexNumber] == 0)
				EnQueue(&q, head->vertexNumber);
			head=head->next;
		}

	}
	if (counter != G->V)
		printf("Graph has cycle!\n");

	while (Front(topologicalorder, &v) && DeQueue(&topologicalorder))
			printf("%d ", v);
}



void test() {
	Graph *G = adjacencyList();
	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 list