Antoun J. Yaacoub Ph.D.

Perform a topological sort using DFS 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]; 
	int top;
} stack;

typedef struct node {
	int vertexNumber;
	struct node * next;
} node;
typedef struct {
	int V;
	int E;
	node** Adj;  //array of linked list
} Graph;




stack CreateStack()
{
	stack p;
	p.top = -1;
	return p;
}

int isEmptyStack(stack p)
{
	return (p.top == -1);
}

int isFullStack(stack p)
{
	return (p.top == N-1);
}

int Push(stack *p, element e)
{
	if (isFullStack(*p)) return 0;
	p->data[++p->top] = e;
	return 1;
}

int Pop(stack *p)
{
	if (isEmptyStack(*p)) return 0;
	p->top--;
	return 1;
}

int Top(stack p, element *e)
{
	if (isEmptyStack(p)) return 0;
	*e = p.data[p.top];
	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 DFSTraversal(Graph *G, int index, int Visited[]) {
	stack s;
	element e;
    	node * head;

	s=CreateStack();
		
	Push(&s,index);
	Visited[index] = 1;

	while(Top(s,&e))
	{
	    Pop(&s);
	    printf("%d ",e);
	    head=G->Adj[e];
	    while(head)
	    {
	        if(!Visited[head->vertexNumber])
	        {
	            Visited[head->vertexNumber] = 1;
	            Push(&s,head->vertexNumber);
	        }
	        head = head->next;
	    }
	}
}

void topological_helper(Graph * G, int index, int Visited[], stack *s)
{
	node * head;
	head=G->Adj[index]->next;
	while(head)
	{
		if(!Visited[head->vertexNumber])
	        {
	            Visited[head->vertexNumber] = 1;
	            topological_helper(G,head->vertexNumber,Visited,s);
	        }
	        head = head->next;
	}
	Push(s,index);
}

void topological(Graph *G)
{
	stack s;	
	int i;
	int *Visited;
	element e;

	s=CreateStack();
	Visited = (int *)malloc(G->V * sizeof(int));
	for (i = 0; i < G->V; i++)
		Visited[i] = 0;

	// this loop is required if the graph has more than one component
	for (i = 0; i < G->V; i++)
		if (!Visited[i])
		{
			Visited[i] = 0;
			topological_helper(G, i, Visited, &s);
		}
	while(Top(s,&e) && Pop(&s) && printf("%d ",e));
	
}

void test() {
	Graph *G = adjacencyList();
	topological(G);
}

int main()
{
	test();
	return 0;
}

Back to the list of exercises

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

Length of the longest ascending sequence of characters

Topological sort using DFS traversal of a graph using an adjacency list