Graphs BFS DFS

GRAPHS

GRAPH REPRESENTATION
Let us see an example of a simple graph

Our graph has 4 vertices and 4 edges, and we can clearly see its directional nature. We can see that if there are 4 vertices, four spaces will be required to store those vertices, and there can be a possibility of each vertex being connected to the other vertex, such that there can be 4 * 4 = 16 possibilities of graph being connected. Therefore, we need a way to represent the edges for each vertex.

To make things simpler, we’d use an 2D array, also known as the adjacency matrix, where i [row] represents vertex, and j [column] represents the edge leading to the new vertex.

When accessing a row, it represents that we are standing on the vertex, on which we add 1’s if we find a edge towards the new vertex.

Here, the vertexes are represented and accessed as indexes. We know that we have 4 vertices, hence we need ( v - 1 ) indexes in array for its 2-dimensional nature.

We hold the convention in graphs that the vertex from where the edge goes is represented as u, and the vertex where the edge has gone, is represented as v.

The array we have taken is such that the edges that exist are represented and marked as one. Whereas the empty spaces are represented and marked as zero.

When the edge goes from u to v, we say, u of v, then [u][v] is marked from 0 to 1. Otherwise, the matrix stays in its default value of zero.

What if the graph was undirected in nature? Without arrows. Then the same edge, can go both ways ahead and back. For example, taking the vertex 0, the edge can go from 0 of 1, to 1 of 0 as well, and also from 0 of 2, to 2 of 0 as well.

Fun fact, an undirected graph represented through adjacency matrix is symmetric along its diagonal. A mirror image of edge direction.

ADJACENCY MATRIX IMPLEMENTATION

#include<stdio.h>
intmain(){
int e;
printf("Enter the number of vertices: ");
scanf("%d", &e);
int graph[e][e]; // adjacency matrix

printf("Enter 1 to create a edge \nEnter 0 otherwise\n\n");
int scan;
for(int u = 0; u < e; u++){ // accessing rows [u]
for(int v = 0; v < e; v++){ // accessing columns [v]
graph[u][v] = 0; // all edges of every vertex initially zero
if(u == v){ continue; } // vertex cannot come to itself
printf("do you want edge, %d ---> %d ", u, v);
scan = 0; // edge not selected
scanf("%d", &scan);
if(scan == 1){ // edge selected
graph[u][v] = 1;
}
}
}

printf("\n\n");
// print adjacency matrix
for(int u = 0; u < e; u++){
for(int v = 0; v < e; v++){
printf(" %d ", graph[u][v]);
}
printf("\n");
}
return0;
}

We have entered the same vertexes and edges as the graph we have demonstrated for an ease of understanding.

Despite adjacency matrix being easy, it has major drawbacks of taking unnecessary empty spaces wherever the memory block is zero. Along with that, the diagonal itself will always be zero, because the vertex cannot go to itself, 1 of 1 doesn’t makes any sense.

Let us go towards the optimal representation, Adjacency List.

We store the vertices in a single array of fixed size n, where the value at a vertex points a list that represents the number of edges pointing to other vertexes.

In C++, implementing this list is essentially easy, where a map from the built-in collections can be used, that would be storing the vertexes as the keys, returning back a list of edges, where the list is a dynamic vector array. In Java as well, similar implementation can be done using a built-in MapSet<Integer, ArrayList<Integer>>

What if the graph was undirectional in nature? Then the list would contain double the number of edges than what it holds beforehand.

However, to implement this in C, we’d need an 1D array, storing vertexes that are actually pointers to a dynamic linked list implementation, giving us the values of edge.

We are straightaway taking vertex as a pointer of structure node which itself has no value but are pointers to our list. We are doing this because the values of the vertex are same as the indexes of the array, so the index itself will give us the value of that vertex.

Space complexity of an adjacency list is O(V + E) where V is the number of vertices, and E is the number of edges in the list. It is much better than O(V^2) for adjacency matrix where V is the number vertices.

ADJACENCY LIST IMPLEMENTATION

#include<stdio.h>
#include<stdlib.h>
// Adjacency List
// Array of pointer of type list
// Linked List with edges connected
typedefstructnode {
int vertex_value;
structnode* next;
} NODE;

voidaddedge(NODE* graph[], int u, int v){
NODE* newedge = (NODE*)malloc(sizeof(NODE));
newedge->vertex_value = v;
newedge->next = graph[u];
graph[u] = newedge;
}

intmain(){
int e;
printf("Enter the number of vertices: ");
scanf("%d", &e);

NODE* graph[e]; // array pointers of vertices
for(int u = 0; u < e; u++){
graph[u] = NULL; // initialize all vertices pointers to null
}

printf("Enter 1 to create a edge \nEnter 0 otherwise\n\n");
int scan;
for(int u = 0; u < e; u++){ // vertex
for(int v = 0; v < e; v++){ // possibilities of having edges
if(u == v){ continue; } // ingoring edge to iself
printf("do you want edge, %d ---> %d ", u, v);
scan = 0; // edge not selected
scanf("%d", &scan);
if(scan == 1){ // edge selected
addedge(graph, u, v);
}
}
}

printf("\n\n");
// print adjacency list
for(int u = 0; u < e; u++){ // vertex u
NODE* list = graph[u];
printf("Vertex %d ---> ", u);
while(list != NULL){ // checking every edge v in list
printf(" %d", list->vertex_value);
list = list->next;
}
printf("\n");
}
return0;
}

A graph problem can be identified if they are numbered [labeled], or they represent some relations to other indexes [edges], or they directly ask about from a graph specific topic.

GRAPH TRAVERSAL

Traversal means that we have to visit every node in the graph at least once so that we could get the value at those vertices.

There are 2 ways to traverse a graph, bfs and dfs.

DFS [DEPTH FIRST SEARCH]

In dfs, we explore the depth of a vertex till no more edges remain or till we find a already visited vertex if graph is cyclic in nature.

Let us take a cyclic graph as an example,

DRY RUN

In the graph above, dfs will say, hey vertex 1, check your edges, it says 1 of 2, visit it, then it goes to vertex 2, dfs will say, hey vertex 2, check your edges, it says 2 of 3 and 2 of 0, then it goes to vertex 3, dfs will say, hey vertex 3, give me your edges, there are no further edges of vertex 3 so it comes back, from vertex 2, it goes to vertex 0, dfs will say, hey vertex 0, give me your edges, says 0 of 1 and 0 of 2.

Here’s the catch, when vertex 0 further goes to either of its edges 1 and 2, duplicate values and infinite loop will begin because vertices at those edges have already been visited and the graph is cyclic.

We have to take account of whether we have already visited the vertex or not, we will take a boolean array of the same size of the number of vertices we have, and we will check whether we have already visited the vertex from this array, if not, then we’ll mark that vertex as visited, if already visited, we’ll not consider it in dfs.

Being at vertex 1, mark as visited, we move to 1 of 2, mark as visited, we move to 2 of 3, mark as visited, then to 2 of 0, mark as visited, further moving to 0 of 1 or 0 of 2, but hey, already visited, hence not considered and the traversal be done.

DFS IMPLEMENTATION

#include<stdio.h>

// dfs begins from the vertex passed to the function, marks it as visited, and begins searching for the edges that are connected to it.

// as soon as it finds an unvisited edge, it quickly jumps over it, calling the function again, the recursive function, marks that edge as visited, and in the similar way, its further edges are checked, and the first unvisited edge to be found is jumped upon quickly again, reaching over the next edge, and it keeps going into the depth till it reaches the base case, that the edges have already been visited.

// when the recursive functions will come backwards to their respective callers, they’ll also check for the remaining edges, but if they have already been visited, which they most likely would, the recursive functions will come to end.

voiddfs(int graph[][4], int u, int visited[], int graph_size){
if(visited[u] == 1){
return;
}
visited[u] = 1;
printf(" %d ", u);
for(int v = 0; v < graph_size; v++){
if(visited[v] == 0 && graph[u][v] == 1){
dfs(graph, v, visited, graph_size);
}
}
}
intmain(){
int graph[][4] = {
{0, 1, 1, 0},
{0, 0, 1, 0},
{1, 0, 0, 1},
{0, 0, 0, 0}
};
for(int u = 0; u < 4; u++){
int visited[] = {0,0,0,0};
printf("DFS on Vertex %d : ", u);
dfs(graph, u, visited, 4);
printf("\n");
}
return0;
}





BFS [BREADTH FIRST SEARCH]

In bfs, we traverse the next neighbours of a vertex, before going further to traverse the next neghbours of those next neighbours. In other words, all edges of a vertex are traversed once, before going deeper into the edges of the next vertex.

How do we know which neighbour vertex to go to traverse its edges once all edges of the current vertex has been traversed?

If we look back into binary trees, bfs works on the principle of level order traversal, where nodes nodes are traversed level-wise, it cannot do deeper to its children, once all the nodes at the current level has been traversed.

How do we do a level order traversal? Using queues.
You may think why would we use queues in a graph?

Lets look deeper, the first neighbour to come will also be the first to traverse its neighbours once all neighbours of our chosen vertex have been visited.

Let us take an analogy, I want to send an invitation to my wedding, I’ll first send it to all my friends that are connected to me, I am the vertex and my friends are edges. Now, I have visited all my friends and they want me to invite their friends too. Once, all my friends connected to me have received the invitation, then I’ll go to send invitation to all the friends of my friends that were connected to me. In that way, all friends of friends will also receive invitation but at the next level. Giving invitation to all my friends first was the first level traversal. And giving invitation to the friends of friends, that also keeping the priority of who asked first in mind, it’ll be the second level traversal.

DRY RUN

We choose 0 as our vertex, we mark it as visited and push it to the queue. We’ll pop the chosen vertex, and at the same instance, we’ll traverse its neighbours, mark them as visited and push it to the queue. Then we’ll do the same for next vertex 1, we’ll pop it, and traverse its neighbours, but hey, 1 of 2 is already visited, so it’ll push it to the queue. Then vertex 2 will be popped, and its neighbours are traversed, 2 of 3, 3 is pushed to queue and marked as visited, whereas 2 of 0 is already visited, so it’ll be ignored. At last, 3 is popped, and it having no further neighbours, traversal be done.

bfs is always used in shortest path algorithms, because it covers all the edges of a layer then goes to the next layer, level by level.
BFS IMPLEMENTATION

#include<stdio.h>
#define MAX 100
staticintqueue[MAX];
int front = 0, rear = 0;
voidqueue_push(int e){
if(rear >= MAX){ printf("overflow"); }
queue[rear++] = e;
}
intqueue_pop(){
if(front >= rear){ printf("underflow"); return-1; }
int e = queue[front++]; return e;
}
intqueue_empty(){
if(front >= rear){ return1; }
elsereturn0;
}

// bfs function begins with taking the vertex passed to it as the starting point, marking it as visited and pushing it to the queue before looping over the queue.

// because the queue is not empty now as it holds starting vertex, it’ll go inside the while loop, and pop the vertex the next instance.

// Now the popped vertex is the one that has been already visited, and its time to visit its neighbours, one after another. Neighbours that have not already been visited and are present in the graph, are pushed to the queue, and marked as visited.

// In the similar way, the next vertex is popped out, and its time for its neighbours to visit one by one. When its neighbors have already been visited, they’d not be pushed to queue. And the loop will end soon, once all neighbours are visited.

voidbfs(int graph[][4], int u, int visited[], int graph_size){
visited[u] = 1;
queue_push(u);
printf("BFS on Vertex %d : ", u);

while(!queue_empty()){
u = queue_pop();
printf(" %d ", u);
for(int v = 0; v < graph_size; v++){
if(visited[v] == 0 && graph[u][v] == 1){
visited[v] = 1;
queue_push(v);
}
}
}

}
intmain(){
int graph[][4] = {
{0, 1, 1, 0},
{0, 0, 1, 0},
{1, 0, 0, 1},
{0, 0, 0, 0}
};
for(int u = 0; u < 4; u++){
int visited[] = {0,0,0,0};
bfs(graph, u, visited, 4);
printf("\n");
}
return0;
}



Total Time Complexity of BFS / DFS = O(V) + O(E)
where, O(V) are number of vertices, O(E) are number of edges

GRAPHS

CYCLE DETECTION [ UNDIRECTED GRAPH ]
USING DFS

Let us take an example of a cyclic graph,

How do we detect that our graph is cyclic in nature?

You can say it is pretty simple, as we are marking every visited vertex, next time we encounter an already visited vertex, we’ll say that marked vertex connected to our vertex is our detected cycle.

But hey, it’s an undirected graph, it’s not that simple, every edge will not only go forwards, but backwards as well.

We can say, if we start from 0 marking it as visited, then going to next vertex 0 of 1, marking it as visited, now being at vertex 1, it’ll also check all its edges, and when 1 of 0 is checked again, because 0 was already visited, it will be marked as a cycle, which actually is not.

That means we cannot trust completely on the visited mark, we need to track something else, what could it be? We have to track the path that has been travelled, from where our vertex has came.
How do we track the travelled path?

The vertex that has called the dfs function again on one of its edges will also tell dfs function that hey, I am the one that called you, which means to say, I am that from where you originated [I am your parent].

If we track the parent vertex from where the new vertex has been reached, we’ll be able to detect the already travelled path among all the edges of the new vertex.

DRY RUN

Let us dry run now, we start from vertex 0, mark as visited, it has no parent, suppose [-1], then it’s edge, 0 of 1 is travelled, on vertex 1, mark as visited, it has been passed parent 0, now among it’s edges 1 of 0, 1 of 2, 1 of 4, smallest one is first to be checked, before travelling 1 of 0, it checks whether the edge is the same as where it has came from, the travelled path, and when it finds 1 of 0 has parent 0, it’ll simply continue over to next edges. . .

1 of 2, check for parent, called dfs on vertex 2 with parent of 2 as 1 and mark vertex 2 as visited, then 2 of 1, check for parent, continued, then 2 of 3, check for parent, called dfs on vertex 3 with parent of 3 as 2 and mark vertex 3 as visited, then 3 of 2, check for parent, continued, then 3 of 4, check for parent, called dfs on vertex 4 with parent of 4 as 3 and mark vertex 4 as visited . .

Now the main deal, 4 of 1, check for parent, which it is not, then dfs is called only if the vertex next to it has not been visited, but because it has already been visited, and it is not the parent as well, it definitely is the cycle.

However, the code has not ended yet, it’ll also check for the remaining edges, 4 of 3, check for parent, continued, edges of 4 checked, returns to 3, its edges also checked, returns to 2, also checked, return to 1, edge 4 still remaining, 1 of 4, check for parent, 1 has parent 0, and vertex 4 has already been marked as visited, then it means it is definitely a cycle.

So, the cycle has been detected in both directions in an undirected graph, which is completely fine, and even better than detecting an unidirectional cycle when it was actually bidirectional.

#include<stdio.h>
intdetectcycle(int graph[][5], int u, int visited[], int graph_size, int parent){
if(visited[u] == 1){
return0;
}

visited[u] = 1;
for(int v = 0; v < graph_size; v++){
if(v == parent || u == v){
continue;
}
if(visited[v] == 0 && graph[u][v] == 1){
detectcycle(graph, v, visited, graph_size, u);
} elseif(visited[v] == 1 && graph[u][v] == 1){
printf("Cycle detected %d ---> %d\n", u, v);
}
}
return0;
}
intmain(){
int visited[5] = {0};
int graph[][5] = {
{0,1,0,0,0},
{1,0,1,0,1},
{0,1,0,1,0},
{0,0,1,0,1},
{0,1,0,1,0}
};
detectcycle(graph, 0, visited, 5, -1);
return0;
}



CYCLE DETECTION [ UNDIRECTED GRAPH ]
USING BFS
Let us take an un-connected cyclic graph,

remember that bfs relies on queues for visiting the neighbours and once all neighbours of our vertex has been visited then the neighbours of the neighbours will be visited.

there is a catch here in bfs, the vertices that are its neighbours are added to the queue to be checked for its neighbours in the future, but a part of graph that is un-connected will not be considered as a neighbour, and it will never to be pushed to the queue.

In the above graph, beginning from vertex 0, its neighbours 1 and 2 will be pushed to the queue, but once they have been popped out and their neighbours have also been checked, there’ll be no further traversal of the un-connected graph.

How do we make sure that all vertices have been traversed?

check for the condition whether the queue is empty before it has visited all the vertices, and if there exists a vertex that has not been visited till now, we’ll push it to the queue and begin from that vertex as the new starting point.

now that we know how to traverse an un-connected graph, let us move on to detect a cycle in undirected graph through bfs.

as we know that we have to track the travelled path and consider the parent vertex that has called the new vertex, to avoid detecting un-directed nature of an edge to be cycle itself, we have to consider a way to store and check for the parent vertex.

and because we use queues to store the neighbours that will checked for its neighbours in the future on a first come first serve basis, in the similar way, we’ll store parent vertex in the queue at the same time when the neighbour has been pushed to queue.

using two queues, we can establish a relation between them, that at every push and pop operation, we are able to push and pop two values at a time, such that the pointers of the queue are common and shared among them.

DRY RUN

Let us begin from vertex 0, the starting point is pushed to the queue, and marked as visited, and the queue loop begins. Vertex 0 is popped out, its neighbours are checked, they are un-visited, so they are marked as visited, and pushed to the queue, but along with that, its parent vertex has also been passed to the parent queue, at the same index location, then vertex 1 is popped along with its parent, and the neighbours of vertex 1 is checked, 1 of 0 being its parent, it’s not checked whether it has already been visited, otherwise it’d wrongly detect a cycle, it’ll simply be skipped, similarly the neighbours of vertex 2 are checked, and no further neighbour is pushed to the queue.

As the queue becomes empty, it’ll check for the remaining un-visited vertices in the un-connected graph, and if there exists a vertex that has not been visited, that vertex will be taken as the new starting point, and it’ll be marked as visited, and pushed to the queue.

And because the queue still is not empty, it’ll continue its bfs traversal, beginning from the new vertex 3, having no parent, it’ll mark its neighbours as visited, and push them to the queue, along with itself being their parent, now when the vertex 4 has been popped, it’ll check okay, vertex 3 is my parent, so i’ll not check whether it’s visited or not, but hey, vertex 5 is not my parent, and still it has already been visited by some other path, that means it’s definitely a cycle, and the cycle has been detected.

Similarly, when the last vertex 5 pops out from the queue, it also checks that hey, vertex 3 is my parent, so i’ll not check whether it’s visited or not, but hey, vertex 4 is not my parent, and it has indeed been visited by some other path, hence it is definitely a cycle.

#include<stdio.h>
#define MAX 100
staticint vertex_queue[MAX];
staticint parent_queue[MAX];
int front = 0, rear = 0;
voidpush(int v, int u){
if(rear >= MAX){ printf("overflow"); return; }
parent_queue[rear] = u;
vertex_queue[rear++] = v;
}
intpop_parent(){
if(front >= rear){ printf("underflow"); return0;}
return parent_queue[front];
}
intpop_vertex(){
if(front >= rear){ printf("underflow"); return0;}
return vertex_queue[front++];
}
intisempty(){
if(front >= rear){ return1; }
elsereturn0;
}
intdetectcycle_bfs(int graph[][6], int u, int visited[], int graph_size, int p){
visited[u] = 1;
push(u, p);
while(!isempty()){
p = pop_parent();
u = pop_vertex();
for(int v = 0; v < graph_size; v++){
if(v == p){
continue;
}
if(visited[v] == 0 && graph[u][v] == 1){
visited[v] = 1;
push(v, u);
} elseif(visited[v] == 1 && graph[u][v] == 1){
printf("\nCycle Detected %d ---> %d", u, v);
}
}
// check for un-visited vertices in an un-connected graph
for(int v = 0; v < graph_size; v++){
if(isempty() && visited[v] == 0){
u = v;
visited[u] = 1;
push(u, -1);
break;
}
}
}
return0;
}
intmain(){
int visited[6] = {0};
int graph[][6] = {
// Graph part 1
{0,1,1,0,0,0},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
// Graph part 2
{0,0,0,0,1,1},
{0,0,0,1,0,1},
{0,0,0,1,1,0}
};
detectcycle_bfs(graph, 0, visited, 6, -1);
return0;
}





DETECT CYCLES IN DIRECTED GRAPH
USING DFS
Let us take a directed graph as an example,

You may think it’s easy, track the travelled path storing parent vertex, and when you find a already visited vertex that is not the travelled path [not parent], then we detected the cycle.

DRY RUN

Let us see, we start at graph 1, taking vertex 0, it checks its edges, 0 of 1 being unvisited and not same parent, quickly jumps over it, then at vertex 1, 1 of 2 being unvisited and not same parent, quickly jumps over it, at vertex 2, no edges that goes from 2, it comes back to the caller 1, and to the caller 0.

Then it travels to 0 of 3 being unvisited and not same parent, marks as visited and quickly jumps over it, at vertex 3, 3 of 2 is now already visited, and also does not have a same parent, according to our logic beforehand, it’ll mark it as a cycle, which is wrong.

How do we think of a new way to detect a cycle in directed graph?

dfs uses recursion, there might be a solution hidden beneath it. If the visited vertex returns back to their caller once they do not find further connected vertices, then that vertex which has returned back should not be considered to detect a cycle, because in a directed way, there is one and only direction to a path, and if in that direction, we do not find what we are looking for, we should not even consider holding that direction in our cycle detection. Now, this itself is the key.

and how do we track which vertices to consider for cycle detection?

we have been tracking whether vertices has been visited or not for a while now, tracking recursive scope is not different, we’d take an array that is initially zero, with no recursive call for now.

DRY RUN

as soon as our beginning vertex 0 is called, it is a part of the recursive stack, considered and marked as true, further it calls and jumps over its neighbour vertex 1, its also considered in recursive stack and marked as true, then to vertex 2, considered and marked true. .

now look, there are no further edges, vertex 2 returns to the caller, but before returning, it marks itself as untrue, because it is not a part of the recursive stack anymore. Similarly, vertex 1 returns to the caller, marking itself as untrue, and vertex 0 jumps over to its next neighbour vertex 3 . .

now both vertex 0 and 3 are parth of recursive call stack, but not vertex 1 and 2, so when vertex 3 checks over to its neighbour vertex 2, it’ll find that even though it has been already visited, however, it is not a part of the recursive stack from where a new path originated, hence no cycle has been detected in graph 1, which is correct.

Let us take another directed graph to understand it,

Our first recursive call stack was from vertex 0 to vertex 1, which did not detected any cycle, so we marked them as untrue while returning back to their respective callers. Similarly, we’d go to a new vertex 2 because all vertices has not been visited till now, it’s a completely new recursive call, and even though vertex 1 has already been visited, it not a part of the same path, hence no cycle detected.

Let us take a last example of a directed graph which has cycle,

It will detect a cycle, at 2 of 0, because vertex 0 has already been visited, and it is also a part of the same recursive call stack.

#include<stdio.h>
voiddetectcycle_dfs(int graph[][3], int u, int visited[], int recursion[], int graph_size){
if(visited[u] == 1){ return; }
visited[u] = 1;
recursion[u] = 1;
for(int v = 0; v < graph_size; v++){
if(visited[v] == 0 && graph[u][v] == 1){
detectcycle_dfs(graph, v, visited, recursion, graph_size);
} elseif(visited[v] == 1 && graph[u][v] == 1 && recursion[v] == 1){
printf(" Cycle detected %d ---> %d ", u, v);
}
}
recursion[u] = 0;
return;
}
intmain(){
int visited[3] = {0};
int recursion[3] = {0};
int graph[][3] = {
{0,1,0},
{0,0,1},
{1,0,0}
};
printf("\nGraph : ");
detectcycle_dfs(graph, 0, visited, recursion, 3);
return0;
}





Topological Sort

We’d have to traverse a graph, so we’d use dfs. Topological sort says, that for a graph that has vertices u and edges v, any vertex-edge pair u of v is such that u always comes first and before the v. But isn’t this obvious that u always comes first and foremost before visiting its neighbours and edges.

But we’ve to store this information, so we can use stack, when the call to recursive dfs ends, then at the moment of returning back, it’d first store value that vertex holds in the stack, and when they’ll be popped out, the last one to be stored that is from where the dfs began will be the first one to be popped out.

Let us take a directed graph example,

DRY RUN

We’ll begin dfs traversal from the vertex 0, following dfs rules, it’ll jump quickly to either 3 or 2, suppose it was vertex 3, then it’ll jump to vertex 1, then to vertex 4, now as no neighbours of vertex 4 remain, it’ll return back to its caller, but before returning back, it’ll make sure to push its value to the stack, as we know, the first one to be pushed in stack will be the last one to come out, and similarly, vertex 1 and 3 will be pushed, but when it reaches back to vertex 0, it’ll find the remaining traversed edge 0 of 2, and it’ll jump to it, vertex 2, once finding that its neighbours are already visited, will push itself and return back, and at last, vertex 5 will be pushed independently, as it was the last one left unvisited.

By popping out from the stack, we got 5, 0, 2, 3, 1, 4
We can see that the numbers we got by popping out are topologically sorted, we can clearly see that for every vertex u, there exists a edge v, such that u is always visited before v.
We can remember this a easy way,


#include<stdio.h>
#define MAX 100
staticintstack[MAX];
int top = 0;
voidpush(int e){
if(top >= MAX){ printf("overflow"); return; }
stack[top++] = e;
}
intpop(){
if(top == 0){ printf("underflow"); return-1; }
returnstack[--top];
}
voidtopological_sort(int graph[][6], int u, int visited[], int graph_size){
if(visited[u] == 1){
return;
}

visited[u] = 1;
for(int v = 0; v < graph_size; v++){
if(visited[v] == 0 && graph[u][v] == 1){
topological_sort(graph, v, visited, graph_size);
}
}

push(u);

// check for unvisited vertices from a new path
for(int v = 0; v < graph_size; v++){
if(u == 0 && visited[v] == 0){
topological_sort(graph,v,visited, graph_size);
}
}
}
intmain(){
int visited[6] = {0};
int graph[][6] = {
{0,0,1,1,0,0},
{0,0,0,0,1,0},
{0,1,0,1,0,0},
{0,1,0,0,0,0},
{0,0,0,0,0,0},
{0,1,0,0,1,0}
};
topological_sort(graph, 0, visited, 6);
printf("Topological Sort: ");
while(top != 0){ printf(" %d ", pop()); }
return0;
}