Bellman Ford Algorithm


Hello people…! In this post I will talk about another single source shortest path algorithm, the Bellman Ford Algorithm. Unlike Dijkstra’s Algorithm, which works only for a graph positive edge weights, the Bellman Ford Algorithm will give the shortest path from a given vertex for a graph with negative edge weights also. Due to this, the Bellman Ford Algorithm is more versatile, but, it’s speciality comes at a cost. The runtime complexity of Bellman Ford Algorithm is O(|V||E|), which is substantially more than that of Dijkstra’s Algorithm. Sometimes this algorithm is called Bellman Ford Moore Algorithm, as the same algorithm was published by another researcher.

Before we get started, there are a couple of things that we must understand. Firstly, why does Dijkstra’s Algorithm fail for negative edge weights and second, the concept of Negative Cycles.

Why does Dijkstra fail?

Consider, the graph below,

bellman1

The Dijkstra’s Algorithm is based on the principle that, if S → V1 → … → Vk is the shortest path from S → Vk then D(S, Vi) ≤ D(S, Vj). But in the above given graph, clearly that principle is violated. In the above graph, the shortest path from V1 to V3 is of length 3 units but the shortest path to V4 is of length 1 unit which means that V4 is actually closer to V1 than V3, which is contradicting Dijkstra’s principle.

Negative Cycles

A Negative Cycle is a path V1 → V 2 → V3 → … Vk → V1 where the total sum of the edge weights in the path is negative. Consider the graph below –

bellman2

The path B → C → D is a negative cycle as the path’s total weight would be -2. So, the distance from A → B is 2, but if we circle the cycle once, we would get the distance as 0, if we circle once more, we would get -2. Like this we could keep on circling as much as we want to reduce the shortest distance. Hence the shortest distance to the vertex B, E becomes indeterminate.

So, we want Bellman Ford Algorithm to solve these two issues. We want it to compute the shortest path even for a graph with negative edges and negative cycles. The Bellman Ford will accurately compute the shortest path for a graph with negative edges but the algorithm fails for a graph with negative cycles. But, the algorithm can tell you if a negative cycle exists or not. If it exists the solution it puts up is incorrect, otherwise, the solution given by Bellman Ford Algorithm is perfect. This sounds fine because logically there will be no shortest paths for a graph with negative cycles.

Unlike the Dijkstra’s Algorithm where we had to use a priority queue, we will require no additional data structure to code Bellman Ford Algorithm. This makes writing the code much easier. And the algorithm is pretty straight-forward too. Take a look at the pseudo-code of the Bellman Ford Algorithm given below –

bellmanFord(G, s)
	for all edges in G(V)
		D(V) = INT_MAX
		parent[V] = -1

	D(s) = 0

	for i = 1 to |G(V)| - 1
		for each edge (u, v) in G(E)
			if edge can be Relaxed
				D(v) = D(u) + weight of edge (u, v)
				parent[v] = u

	for each edge in G(E)
		if edge can be Relaxed
			return false

	return true

You may not understand the pseudo-code at the first look, here’s a step-by-step representation of it –

  • Initialise the array which contains the shortest distances to infinity (a high integer value in the pseudo-code).
  • Initialise the parent array which contains the parent vertices in the shortest path to NULL (or -1 if it is an integer array).
  • Set the shortest distance of starting vertex to 0.
  • Explore all the edges, and see if you can relax them. If you can, relax the edge and proceed with the exploration.
  • Do the above operation |V| – 1 times.
  • After that, do another exploration on the graph checking all the edges if they can be relaxed. If they can be relaxed, you can a negative cycle in the graph. Hence, return false.
  • If the exploration gets finished successfully, the graph has no negative cycles and the data that you compute dis correct, so return true.

Now, what does exploring all the edges mean? If you are implementing the graph using an Adjacency List, it means to iterate over all the linked lists associated with all vertices. Now, what will be the sum of all the nodes in all Linked Lists in a given Adjacency List? Number of edges off course! So, we check all the edges from, edges of vertex 1 to vertex |V| in a linear manner. This whole operation takes O(|E|) time, which is repeated |V| – 1, so this part of the code takes O(|E||V|) time. Now, analyse the pseudo-code for a few minutes. Ask yourself how would you code this-ans-that. Now, when your mind is filled with the pseudo-code, look at the sketch below. The sketch below is sort of, “dry run” of the pseudo-code stated above –

bellman3

The above sketch is self-explanatory. I hope you understand how the iterations go. In a way it looks like a very ordinary algorithm, without any greedy steps or partitions or so. The Bellman Ford Algorithm is pretty easy to code too. If you can work hard for an hour or two I’m sure you can code this algorithm. It does not require any priority queue or other tools. All you need to code Bellman Ford Algorithm is the pseudo-code. The pseudo-code is very important. Keep looking at the pseudo-code again-and-again whenever you get a doubt. I have put my code below for a reference, it is a C++ code –

/*
 * Bellman-Ford Algorithm
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <cstdio>
#include <cstdlib>
#include <climits>

using namespace std;

// This is used to construct
// the Adjacency List
struct node {
	int vertex, weight;
	struct node * next;
};

// This is used to construct the Shortest Paths to all
// vertices, as we cannot return multiple values,
// we use a struct
struct pathInfo {
	int vertex, distance, parent;
};

// Adds a new edge into the Adjacency List
// Follows Head Insertion for O(1) Insertion
struct node * add(struct node * head, int vertex, int weight)
{
	struct node * p = (struct node *) malloc(sizeof(struct node));

	p->vertex = vertex;
	p->weight = weight;
	p->next = head;

	return p;
}

// Bellman-Ford Algorithm which takes the Graph (adjacencyList[]), starting vertex (startVertex),
// and an empty array shortestDistances[] as input. It applies the algorithm and keeps filling values
// into shortestDistances[]. It returns true if there are no negative edges, and vice-versa.
bool bellmanFord(struct node * adjacencyList[], int vertices, int startVertex, struct pathInfo shortestDistances[])
{
	struct node * traverse;
	int i, j, k;

	// Initialisation
	for (i = 0; i <= vertices; ++i) {
		shortestDistances[i].vertex = i;
		shortestDistances[i].distance = INT_MAX;
		shortestDistances[i].parent = -1;
	}

	// Setting distance to source = 0
	shortestDistances[startVertex].parent = 0;
	shortestDistances[startVertex].distance = 0;

	// The Algorithm that computes Shortest Distances
	for (i = 1; i <= vertices - 1; ++i) {		// Runs 'vertices - 1' times = O(|V|)
		for (j = 1; j <= vertices; ++j) {		// Runs as many times as the edges = O(|E|)
			// The code ahead basically explores the whole of Adjcency List,
			// covering one edge once, so the runtime of the code in this
			// block is O(|E|)

			traverse = adjacencyList[j];

			while (traverse != NULL) {
				if (shortestDistances[j].distance == INT_MAX) {
					// Important...!
					traverse = traverse->next;
					continue;
				}

				// Checking for Relaxation
				if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) {
					// Relaxation
					shortestDistances[traverse->vertex].distance = traverse->weight + shortestDistances[j].distance;
					shortestDistances[traverse->vertex].parent = j;
				}

				traverse = traverse->next;
			}
		}
	}

	// Checking for Negative Cycles
	for (j = 1; j <= vertices; ++j) {
		traverse = adjacencyList[j];

		while (traverse != NULL) {
			// Checking for further relaxation
			if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) {
				// Negative Cycle found as further realxation is possible
				return false;
			}

			traverse = traverse->next;
		}
	}

	return true;
}

int main()
{
	int vertices, edges, i, j, v1, v2, weight;

	printf("Enter the Number of Vertices -\n");
	scanf("%d", &vertices);

	printf("Enter the Number of Edges -\n");
	scanf("%d", &edges);

	struct node * adjacency_list[vertices + 1];
	//Size is made (vertices + 1) to use the
	//array as 1-indexed, for simplicity

	//Must initialize your array
	for (i = 0; i <= vertices; ++i) {
		adjacency_list[i] = NULL;
	}
	printf("Enter the edges -\n\n");

	for (i = 1; i <= edges; ++i) {
		scanf("%d%d%d", &v1, &v2, &weight);
		adjacency_list[v1] = add(adjacency_list[v1], v2, weight);
	}

 	//Printing Adjacency List
	printf("\nAdjacency List -\n\n");
	for (i = 1; i <= vertices; ++i) {
		printf("adjacency_list[%d] -> ", i);

		struct node * temp = adjacency_list[i];

		while (temp != NULL) {
			printf("(%d, %d) -> ", temp->vertex, temp->weight);
			temp = temp->next;
		}

		printf("NULL\n");
	}

	struct pathInfo shortestDistances[vertices + 1];
	int startVertex;

	printf("\nEnter a Start Vertex -\n");
	scanf("%d", &startVertex);

	if (bellmanFord(adjacency_list, vertices, startVertex, shortestDistances)) {
		printf("No Negative Cycles exist in the Graph -\n");
	} else {
		printf("Negative Cycles exists in the Graph -\n");
		// The Bellman-Ford Algorithm does not work with negative cycles,
		// all it can do is merely detect them, so when a negative cycle
		// is detected, the shortestDistances array has wrong values
		return 0;
	}

	printf("\n\nVertex    Shortest Distance to Vertex %d     Parent Vertex-\n", startVertex);
	for (i = 1; i <= vertices; ++i) {
		printf("%d         %d                                 %d\n", i, shortestDistances[i].distance, shortestDistances[i].parent);
	}

	return 0;
}

If you have any doubts regarding the algorithm feel free to drop a comment. I’ll surely reply to them. I hope my post helped you in learning the Bellman Ford Algorithm. If it did, let me know by commenting ! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 Keep practicing… Happy Coding…! 🙂

You may also like –

More in the Navigation Page ! →

Advertisements

Dijkstra’s Algorithm


Hello people…! In this post I will talk about one of the fastest single source shortest path algorithms, which is, the Dijkstra’s Algorithm. The Dijkstra’s Algorithm works on a weighted graph with non-negative edge weights and ultimately gives a Shortest Path Tree. It is a Greedy Algorithm, which sort of… mimics the working of Breadth First Search and Depth First Search. It is used in a number of day-to-day scenarios. It is used in network routing, to calculate the path from a network device A and B in a network which would have the maximum bandwidth. It could also be used by the GPS in a car to calculate the shortest path between two locations. The Dijkstra’s Algorithm can be modified to solve a lot of real world problems. So let’s get started…!

The Dijkstra’s Algorithm starts with a source vertex ‘s‘ and explores the whole graph. We will use the following elements to compute the shortest paths –

  • Priority Queue Q, implemented by a Min Binary Heap using C++ STL Vector.
  • Another set D, which keeps the record of the shortest paths from starting vertex s. Implemented using C++ STL Vector.

Just like the other graph search algorithms, Dijkstra’s Algorithm is best understood by listing out the algorithm in a step-by-step process –

  • The Initialisation –
  1. D(s), which is the shortest distance to s is set to 0. It is obvious as distance between source to itself is 0.
  2. For all the other vertices V, D(V) is set to infinity as we do not have a path yet to them, so we simply say that the distance to them is infinity.
  3. The Priority Queue Q, is constructed which is initially holds all the vertices of the Graph. Each vertex V will have the priority D(V).
  • The Algorithm –
  1. Now, pick up the first (or the minimum) element from the Priority Queue Q (which removes it from Q). For the first time, this operation would obviously give s.
  2. For all the vertices adjacent to s, i.e., for all vertices in adjacencyMatrix[s], check if the edge from s → v gives a shorter path. This is done by checking the following condition –

    if, D(s) + (weight of edge s → v) < D(v), we found a new shorter route, so update D(v)
    D(v) = D(s) + (weight of edge s → v)

  3. Now pick the next element from Q, and repeat the process until there are elements left in Q.

It might look like a long and cumbersome process, but this is actually a very smart technique. It’s okay if you don’t understand it in the first reading. Give another 3-4 readings and try to picture what is happening to the graph when you implement the algorithm, in your head. After you feel you have got a hang of the algorithm, look at the sketch below for complete understanding.

Dijkstra's Algorithm Step-by-Step

Dijkstra’s Algorithm Step-by-Step

 

The Dijkstra’s Algorithm is a little tricky. Many don’t understand it in the first attempt. In reference to the diagram above, I will give a step-by-step explanation for each graph marked with the number on top in purple.

  1. Firstly, initialize your components, the shortest distances array D, the priority queue Q, and starting vertex s. The distance from source to itself is zero. So, D(s) = 0, and the rest of the array is ∞ . The set of vertices V are inserted into the priority queue Q, with a priority D(V). Now, we start our algorithm by extracting (hence removing it from the priority queue) the minimum element from the priority queue. The minimum element in the priority queue will definitely be s (which is A here). Look at all the adjacent vertices of A. Vertices B, C, D are adjacent to A. We can go to B travelling the edge of weight 2, to C travelling an edge of weight 1, to D travelling an edge of weight 5. The values of D(B), D(C), D(D) are ∞ . We have found a new way of reaching them in 2, 1, 5 units respectively, which is less than ∞ , hence a shorter path. This is what the if-condition mentioned above does. So, we update the values of D(B), D(C), D(D) and the priorities of B, C, D, in the priority queue. With this we have finished processing the Vertex A.
  2. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element would be Vertex C which would be having a priority of 1. Now, look at all the adjacent vertices to C. There’s Vertex D. From C, the it would take 1 unit of distance to reach D. But to reach C in prior, you need 1 more unit of distance. So, if you go to D, via C, the total distance would be 2 units, which is less than the current value of shortest distance discovered to D, D(D) = 5. So, we reduce the value of D(D) to 2. This reduction is also called as “Relaxation”. With that we’re done with Vertex C.
  3. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. Now, there are two minimum elements, B and D. You can go for anyone, it doesn’t matter. For now, we will go for Vertex D. From Vertex D, you can go to Vertex E, and Vertex F, with a total distance of 2 + 2 {D(D) + (weight of D → E)}, and 2 + 3. Which is less than ∞ , so D(E) becomes 4 and D(F) becomes 5. We’re done with Vertex D.
  4. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex B. From vertex B, you can reach vertex F in 2 + 1 units of distance, which is less than the current value of D(F), 5. So, we relax D(F) to 3. From vertex B, you can reach vertex D in 2 + 2 units of distance, which is more than the current value of D(D), 2. This route is not considered as it is clearly proven to be a longer route. With that we’re done with vertex B.
  5. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex E. From vertex E, you can reach vertex C in 4 + 4 units of distance, which is more than the current value of D(C), 1. This route is not considered as it is clearly proven to be a longer route. With that we’re done with vertex E.
  6. Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex F. You cannot go to any other vertex from vertex F, so, we’re done with vertex F.
  7. With the removal of vertex F, our priority queue becomes empty. So, our algorithm is done…! You can simply return the array D to output the shortest paths.

Having got an idea about the overall working of the Dijkstra’s Algorithm, it’s time to look at the pseudo-code –

dijsktra(G, S)
	D(S) = 0
	Q = G(V)

	while (Q != NULL)
		u = extractMin(Q)
		for all V in adjacencyList[u]
			if (D(u) + weight of edge < D(V))
				D(V) = D(u) + weight of edge
				decreasePriority(Q, V)

In the pseudo-code, G is the input graph and S is the starting vertex. I hope you understand the pseudo-code. If you don’t, feel free to comment your doubts. Now, before we code Dijkstra’s Algorithm, we must first prepare a tool, which is the Priority Queue.

The Priority Queue

The Priority Queue is implemented by a number of data structures such as the Binary Heap, Binomial Heap, Fibonacci Heap, etc. The priority queue in my code is implemented by a Binary Heap. If you are not aware about the Binary Heap, you can refer to my post on Binary Heaps. But the implementation that we will do here is different from that in my post regarding the Binary Heap. The difference is that, here we will implement the Binary Heap using C++ STL Vector, not an array. This is because a heap is meant to grow, not remain of a fixed size, so we are using a data structure that can grow, a vector. Also, when we use a vector we can apply the same traversing techniques that we used in the case of an array. And, every element of our vector will be a Pair of two integers from the utility header file. The two integers represent vertex and weight, which is actually the shortest distances and this weight property will function as the priority to the elements. So, the vertices are placed in the priority queue based on their weight property. We will have to code the operations based on this weight property. Now the functionalities that we need from our priority queue are –

  • Insert – We will insert |V| elements into the Priority Queue.
  • Extract Min – We return the top-most element from the Binary Heap and delete it. Finally we make the neccessary
  • Decrease Priority – We decrease the priority of an element in the priority queue when we find a shorter path, as known as Relaxation.

If you know the working of the Binary Heap and have a little knowledge about the STL Library, you can code the Priority Queue in about 2-5 hours. You can keep referring to the internet of various functions and the syntaxes and any other doubts you have. Typing the code doesn’t take long, but debugging it and making it work takes the most time. That’s how you learn coding. Try your best, work on it for hours, if you don’t get it, take a break for 10-20 minutes… Come back and check my code below and try to figure out how close you were to getting it perfect…!

/*
 * Priority Queue implemented
 * by a Binary Heap using
 * C++ STL Vector, for
 * Dijkstra's Algorithm
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

// Inserts an element into the Queue
void enqueue(vector< pair<int, int> > * priorityQueue, pair<int, int> * entry)
{
	(*priorityQueue).push_back(*entry);

	int i = (*priorityQueue).size() - 1;
	pair<int, int> temp;

	while (i > 0) {
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;

			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Iterates over the Queue to return the index of the element
int findByKey(vector< pair<int, int> > * priorityQueue, pair<int, int> entry)
{
	int i;

	for (i = 0; i < (*priorityQueue).size(); ++i) {
		if ((*priorityQueue)[i].first == entry.first) {
			break;
		}
	}

	if (i != (*priorityQueue).size()) {
		return i;
	} else {
		return -1;
	}
}

// Decreases the priority of the element and makes neccessary adjustments
void decreasePriority(vector< pair<int, int> > * priorityQueue, int index, int newWeight)
{
	(*priorityQueue)[index].second = newWeight;

	int i = index;
	pair<int, int> temp;

	while (i > 0) {
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;

			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Returns the minimum element, deletes it and makes neccessary changes
pair<int, int> extractMin(vector< pair<int, int> > * priorityQueue)
{
	pair<int, int> min = (*priorityQueue)[0];
	pair<int, int> temp;

	// Swap first and last
	temp = (*priorityQueue)[0];
	(*priorityQueue)[0] = (*priorityQueue)[(*priorityQueue).size() - 1];
	(*priorityQueue)[(*priorityQueue).size() - 1] = temp;

	(*priorityQueue).pop_back();

	int i = 0;
	pair<int, int> parent;
	pair<int, int> rightChild;
	pair<int, int> leftChild;

	while (i < (*priorityQueue).size()) {
		parent = (*priorityQueue)[i];
		printf("Currently at - (%d, %d)\n", parent.first, parent.second);

		if (2 * (i + 1) < (*priorityQueue).size()) {
			// both children exist
			rightChild = (*priorityQueue)[2 * (i + 1)];
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];

			if (parent.second < leftChild.second && parent.second < rightChild.second) {
				break;
			} else {
				if (leftChild.second < rightChild.second) {
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;

					i = 2 * (i + 1) - 1;
				} else {
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;

					i = 2 * (i + 1);
				}
			}
		} else if ((2 * (i + 1)) >= (*priorityQueue).size() && (2 * (i + 1) - 1) < (*priorityQueue).size()) {
			// only left child exists
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];

			if (leftChild.second < parent.second) {
				temp = (*priorityQueue)[2 * (i + 1) - 1];
				(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
				(*priorityQueue)[i] = temp;
			}

			break;
		} else {
			// no more children exist
			break;
		}
	}

	return min;
}

int main()
{
	int n;

	printf("Enter the size -\n");
	scanf("%d", &n);

	int vertex, weight, i;
	vector< pair<int, int> > priorityQueue;
	pair<int, int> entry;

	for (i = 0; i < n; ++i) {
		scanf("%d%d", &vertex, &weight);
		entry = make_pair(vertex, weight);
		enqueue(&priorityQueue, &entry);
	}

	printf("\n\nThe Priority Queue (Interpret as Binary Heap) -\n");

	vector< pair<int, int> >::iterator itr = priorityQueue.begin();

	while (itr != priorityQueue.end()) {
		printf("(%d, %d) ", (*itr).first, (*itr).second);
		++itr;
	}
	printf("\n");

	pair<int, int> min = extractMin(&priorityQueue);
	printf("\n\nExtract Min returned = (%d, %d), The Queue -\n", min.first, min.second);
	itr = priorityQueue.begin();

	while (itr != priorityQueue.end()) {
		printf("(%d, %d) ", (*itr).first, (*itr).second);
		++itr;
	}
	printf("\n");

	decreasePriority(&priorityQueue, priorityQueue.size() - 1, 1);
	printf("\n\ndecreasePriority() used, The Queue -\n");
	itr = priorityQueue.begin();

	while (itr != priorityQueue.end()) {
		printf("(%d, %d) ", (*itr).first, (*itr).second);
		++itr;
	}
	printf("\n");

	return 0;
}

There are many other functionalities that a Priority Queue can give. But for now, we’ll need only these.

Joining the pieces

After you have your tool ready, you are all good to code Dijkstra’s Algorithm. Coding the Dijkstra’s Algorithm is easy but can go really weird. This is because you need to handle and co-ordinate many data structures at once. You’ll have to manage the adjacency list, the priority queue, the shortest distance array, and most importantly your loops…! You will surely end up spending more time in debugging the code, which is perfectly the right way of doing it. All throughout the coding, keep revising the step-by-step process explained above. If you don’t get it you, don’t fret, I put my code below. Before you look at my code, I would like to mention a few things –

  • We cannot have infinity in programming, so the shortest distances are initialised to the highest possible value in integer range, present in a macro, INT_MAX, in the header file climits.
  • The header file utility must be included to use pairs.
/* 
 * Dijkstra's Algorithm in C++
 * using Binary Heap as Priority
 * Queue implemented using 
 * C++ STL Vector
 *
 * Authored by,
 * Vamsi Sangam
 */

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <vector>
#include <utility>

using namespace std;

// Our Vertex for Graph
struct node {
	int vertex, weight;
	struct node * next;
};

// To construct our Adjacency List
// Follows Head Insertion to give O(1) insertion
struct node * addEdge(struct node * head, int vertex, int weight)
{	 
	struct node * p = (struct node *) calloc(1, sizeof(struct node));
	
	p->vertex = vertex;
	p->weight = weight;
	p->next = head;
	
	return p;
}

// Adds vertices to the Priority Queue, Vertices a represented
// as pairs of vertex number and its shortest distance.
// This is logically a Binary Heap Insertion
void enqueue(vector< pair<int, int> > * priorityQueue, pair<int, int> * entry)
{
	(*priorityQueue).push_back(*entry);
	
	int i = (*priorityQueue).size() - 1;
	pair<int, int> temp;
	
	while (i > 0) {
		// Checking the priority of the parent, if greater, swap, else, we are done
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;
			
			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Finds for a Vertex in the Priority Queue and 
// returns its index as in its vector implementation
int findByKey(vector< pair<int, int> > * priorityQueue, pair<int, int> entry)
{
	int i;
	
	// Linear Search
	for (i = 0; i < (*priorityQueue).size(); ++i) {
		if ((*priorityQueue)[i].first == entry.first) {
			break;
		}
	}
	
	if (i != (*priorityQueue).size()) {
		return i;
	} else {
		return -1;
	}
}

// Decreases the priority of a given entry in the
// Priority Queue who's location is given by 'index'
// to 'newWeight' and re-arranges the Binary Heap
void decreasePriority(vector< pair<int, int> > * priorityQueue, int index, int newWeight)
{
	// Decreasing Priority
	(*priorityQueue)[index].second = newWeight;
	
	int i = index;
	pair<int, int> temp;
	
	// Adjusting the Binary Heap, similar re-arrangement as done in enqueue()
	while (i > 0) {
		if ((*priorityQueue)[(i - 1) / 2].second > (*priorityQueue)[i].second) {
			temp = (*priorityQueue)[(i - 1) / 2];
			(*priorityQueue)[(i - 1) / 2] = (*priorityQueue)[i];
			(*priorityQueue)[i] = temp;
			
			i = (i - 1) / 2;
		} else {
			break;
		}
	}
}

// Picks up the minimum element of the Priority Queue and re-arranges
// the Binary Heap and finally returns the Minimum Element picked.
// Functionally resembles Delete operation in Binary Heap, but additionally
// returns the deleted element which is the minimum element.
pair<int, int> extractMin(vector< pair<int, int> > * priorityQueue)
{
	pair<int, int> min = (*priorityQueue)[0];		// Min Element Stored
	pair<int, int> temp;
	
	// Swap first and last elements
	temp = (*priorityQueue)[0];
	(*priorityQueue)[0] = (*priorityQueue)[(*priorityQueue).size() - 1];
	(*priorityQueue)[(*priorityQueue).size() - 1] = temp;
	
	(*priorityQueue).pop_back();					// Deleted Min Element
	
	int i = 0;
	pair<int, int> parent;			// These three variables
	pair<int, int> rightChild;		// are for readability of
	pair<int, int> leftChild;		// the if conditions ahead
	
	while (i < (*priorityQueue).size()) {
		parent = (*priorityQueue)[i];
		
		if (2 * (i + 1) < (*priorityQueue).size()) {
			// both children exist
			rightChild = (*priorityQueue)[2 * (i + 1)];
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];
			
			if (parent.second < leftChild.second && parent.second < rightChild.second) {
				// Parent has lesser priority than its children, so wer're done
				break;
			} else {
				if (leftChild.second < rightChild.second) {
					// Left-child has a lesser priority, so, swap
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;
				
					i = 2 * (i + 1) - 1;
				} else {
					// Right-child has a lesser priority, so, swap
					temp = (*priorityQueue)[2 * (i + 1) - 1];
					(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
					(*priorityQueue)[i] = temp;
				
					i = 2 * (i + 1);
				}
			}
		} else if ((2 * (i + 1)) >= (*priorityQueue).size() && (2 * (i + 1) - 1) < (*priorityQueue).size()) {
			// only left child exists
			leftChild = (*priorityQueue)[2 * (i + 1) - 1];
			
			if (leftChild.second < parent.second) {
				// Left-child has a lesser priority, so, swap
				temp = (*priorityQueue)[2 * (i + 1) - 1];
				(*priorityQueue)[2 * (i + 1) - 1] = (*priorityQueue)[i];
				(*priorityQueue)[i] = temp;
			}
			
			break;
		} else {
			// no more children exist
			break;
		}
	}
	
	return min;
}

// The Dijkstra's Algorithm sub-routine which takes the Graph as Adjcaency List,
// number of vertices, a starting vertex, and an empty shortestDistances array as
// input and computest the shortest paths and fills them up in the shortestDistances array
void dijkstra(struct node * adjacencyList[], int vertices, int startVertex, pair<int, int> shortestDistances[])
{
	int i;
	
	// Initially no routes to vertices are know, so all are infinity,
	// here, we initialize to a very high integer value
	for (i = 0; i <= vertices; ++i) {
		shortestDistances[i].first = INT_MAX;
		shortestDistances[i].second = -1;
	}
	
	// Setting distance to source to zero
	shortestDistances[startVertex].first = 0;
	shortestDistances[startVertex].second = 0;
		
	struct node * trav;
	vector< pair<int, int> > priorityQueue;
	pair<int, int> min;
	
	// Making a the vertex that corresponds to the
	// 'startVertex' which will have a priority of zero
	// and we begin to intialise the Priority Queue
	pair<int, int> entry = make_pair(startVertex, 0);
	enqueue(&priorityQueue, &entry);
	
	// Initialising Priority Queue
	for (i = 1; i <= vertices; ++i) {
		if (i == startVertex) {
			continue;
		} else {
			// Priorities are set to a high integer value
			entry = make_pair(i, INT_MAX);
			enqueue(&priorityQueue, &entry);
		}
	}

	// We have the tools ready..! Let's roll...!!
	while (priorityQueue.size() != 0) {		// Untill there are vertices to be processed in Queue
		min = extractMin(&priorityQueue);	// Greedily process the nearest vertex
		
		trav = adjacencyList[min.first];	// Checking all the vertices adjacent to 'min'
		while (trav != NULL) {
			if (shortestDistances[trav->vertex].first > shortestDistances[min.first].first + trav->weight) {
				// We have discovered a new shortest route
				// Make the neccesary adjustments in data
				entry = make_pair(trav->vertex, trav->weight);
				
				int index = findByKey(&priorityQueue, entry);
				
				decreasePriority(&priorityQueue, index, trav->weight);
				shortestDistances[trav->vertex].first = shortestDistances[min.first].first + trav->weight;
				shortestDistances[trav->vertex].second = min.first;
			}
			
			trav = trav->next;
		}
	}
}

void PrintShortestPath(pair<int, int> shortestDistances[], int vertex, int startVertex)
{
	if (vertex == startVertex) {
		printf("%d ", startVertex);
		return;
	} else {
		PrintShortestPath(shortestDistances, shortestDistances[vertex].second, startVertex);
		printf("%d ", vertex);
	}
}

int main()
{
	int vertices, edges, i, j, v1, v2, w;
	
	printf("Enter the Number of Vertices -\n");
	scanf("%d", &vertices);
	
	printf("Enter the Number of Edges -\n");
	scanf("%d", &edges);
	
	struct node * adjacencyList[vertices + 1];
	//Size is made (vertices + 1) to use the
	//array as 1-indexed, for simplicity
	
	//Must initialize your array
	for (i = 0; i <= vertices; ++i) {
		adjacencyList[i] = NULL;
	}
	
	printf("\n");
	
	for (i = 1; i <= edges; ++i) {
		scanf("%d%d%d", &v1, &v2, &w);
		adjacencyList[v1] = addEdge(adjacencyList[v1], v2, w);
	}
 
 	//Printing Adjacency List
	printf("\nAdjacency List -\n\n");
	for (i = 1; i <= vertices; ++i) {
		printf("adjacencyList[%d] -> ", i);
		
		struct node * temp = adjacencyList[i];
		
		while (temp != NULL) {
			printf("%d(%d) -> ", temp->vertex, temp->weight);
			temp = temp->next;
		}
		
		printf("NULL\n");
	}
	
	int startVertex;
	
	printf("Choose a Starting Vertex -\n");
	scanf("%d", &startVertex);
	
	pair<int, int> shortestDistances[vertices + 1];
	// shortestDistances.first = shortest distance calculated
	// shortestDistances.second = parent node
	
	dijkstra(adjacencyList, vertices, startVertex, shortestDistances);
	
	printf("\n\nDijkstra's Algorithm Used - Shortest Paths from Vertex %d -\n", startVertex);
	for (i = 1; i <= vertices; ++i) {
		printf("Vertex %d, Distance = %d, Parent = %d\n", i, shortestDistances[i].first, shortestDistances[i].second);
	}
	printf("\n");
	
	PrintShortestPath(shortestDistances, vertices /* The Last Vertex */, startVertex);
	
	return 0;
}

This is the Dijkstra’s Algorithm. The code is well commented with explanation. If you don’t understand anything or if you have any doubts. Feel free to comment them. Now talking about the complexity of Dijkstra’s Algorithm. We perform |V| enqueue operations into the priority queue, which take O(log N), here, N is |V|, so this takes O(|V| log |V|). And at most |E| decrease priority operations which will take O(|V|) time. The extract-min is also called |V| times which will take O(|V| log |V|) time. So, the overall complexity of Dijkstra’s Algorithm we wrote is O(|V| log |V| + |E||V|). Dijkstra’s Algorithm can be improved by using a Fibonacci Heap as a Priority Queue, where the complexity reduces to O(|V| log |V| + |E|). But the Fibonacci Heap is an incredibly advanced and difficult data structure to code. We’ll talk about that implementation later.

I really hope my post has helped you in understanding the Dijkstra’s Algorithm. If it did, let me know by commenting. I tried my best to keep it as simple as possible. If you have any doubts, you can comment them too and I will surely reply to them. This algorithm is a particularly tough one. So, good luck… Keep practicing and… Happy Coding…! 🙂

You may also like –

More in the Navigation Page ! →

Depth First Search (DFS) Algorithm


Hello people…! In this post I will talk about the other Graph Search Algorithm, the Depth First Search (DFS). Depth First Search is different by nature from Breadth First Search. As the name suggests, “Depth”, we pick up a vertex S and see all the other vertices that can possibly reached by that vertex and we do that to all vertices in V. Depth First Search can be used to search over all the vertices, even for a disconnected graph. Breadth First Search can also do this, but DFS is more often used to do that. Depth First Search is used to solve puzzles! You can solve a given maze or even create your own maze by DFS. DFS is also used in Topological Sorting, which is the sorting of things according to a hierarchy. It is also used to tell if a cycle exists in a given graph. There are many other applications of DFS and you can do a whole lot of cool things with it. So, lets get started…!

The way the Depth First Search goes is really like solving a maze. When you see a maze in a newspaper or a magazine or anywhere else, the way you solve it is you take a path and go through it. If you find any junction or a crossroad, where you have a choice of paths to choose, you mark that junction, take up a path and traverse the whole route in your brain. If you see a dead end, you realize that this leads you now where so you come back to the junction you marked before and take up another path of the junction. See if that is also a dead end, else you continue to explore the, puzzle as this route contributes in reaching your destination. Well, at least that’s how I solve a maze. But… I hope you get the idea. You pick up a path and you explore it as much as possible. When you can’t travel any further and you haven’t yet reached your destination, you come back to the starting point and pick another path.

In code, you do this by recursion. Because of the very nature of recursion. Your recursion stack grows-grows and eventually becomes an empty stack. If you think for a while you can notice that the way of traversing which I told you above is logically covering only the vertices accessible from a given vertex S. Such traversal can be implemented using a single function that is recursive. But we want to explore the whole graph. So, we will use another function to do this for us. So, DFS is a two-functions thing. We will come back to the coding part later. Now, DFS too can be listed out in a step-by-step process –

  • For a given set of vertices V = {V1, V2,V3…}, start with V1, and explore all the vertices that can possibly be reached from V1.
  • Then go to the next vertex V2, if it hasn’t been visited, explore all the nodes reachable from V2, if not, go for V3.
  • Similarly, go on picking up all the vertices one-by-one and explore as much as possible if it wasn’t visited at all.

Now, how do you tell if a vertex wasn’t visited earlier…? If it has no parent vertex assigned. So what you have to do when you visit a node is –

  • Set the parent vertex of the current vertex to be the vertex from where you reached that vertex. We will use an array to assign parent vertices, which is initialised to -1, telling that the vertices were never visited.
  • When you are starting your exploration from a vertex, say, V1, we assign parent[V1] = 0, because it has no parent. If there is an edge from V1 to V2, we say, parent[V2] = V1.

Let’s look at an example and see how DFS really works –

dfs1

The working of DFS is pretty clear from the picture. Notice how we would assign the parent vertices to each vertex. Once we have visited all the vertices from a given initial vertex V1, we backtrack to V1. What do we really mean by this “backtrack” here is that the recursion control will gradually come back to the function that started explopring from V1. We will understand this once we put DFS in code. And one more thing, whenever we got a choice of going to two vertices from one vertex, we preferred going to the vertex with the greater number. Why is this…? This is because we will be following Head Insertion in our Adjacency Lists to have O(1) Insertion operation. Now, assuming that we insert the vertices from Vertex 1 to Vertex 10, the greater number vertices will end up being in front of the Linked Lists. Take a moment to understand this. Even if you don’t understand, it’s ok…! You will get the hang of it later. Why I really did that was to explain you the concept of Edge Classification.

dfs2

As you can see there are three types of edges, in fact, there are 4 actually. They are –

  • Tree Edge – These are the edges through which we have traversed all the vertices of the graph by DFS. More clearly, these are the edges that represent the parent-child relationship. That is, the tree edge Vertex 1 → Vertex 3 says that, Vertex 1 is the parent of Vertex 3. Just like the parent-child relationship in a tree. Why this is called a “tree” edge is that it happens so that these edges together form a “tree”, or rather a “forest”.
  • Forward Edge – This is an edge which points from one vertex which is higher in the hierarchy of parent-child relationship to a vertex which is a descendant. Observe that Vertex 2 is a descendant of Vertex 1, so the edge Vertex 1 → Vertex 3, is a forward edge.
  • Backward Edge – This is the opposite of forward edge. It points from a descendant Vertex to an ancestor Vertex. In the above diagram, the edge, Vertex 4 → Vertex 3 is a backward edge.
  • Cross Edge – Every other edge is a cross edge. We don’t have a cross edge in the above diagram, but, a cross edge can arise when there is a edge between siblings, two vertices that have the same parent.

Cycle Detection – Using DFS, we can detect if there are any cycles in the given graph. How…? This is very simple. If there exists at least one backward edge, then the given graph will have cycles. Well, telling how many cycles would be there for given number of backward edges is a challenge. But the point is if there is a backward edge, there is a cycle. This is by the very definition of the Backward Edge. It is an edge from a descendant to an ancestor. If we have a backward edge, then there will surely be another path of tree edges from the ancestor to descendant, forming a cycle. The picture below should make things clear.

dfs3

But, how do we compute backward edges in code…? This is a little tricky. We could have a boolean array of size |V| which would hold the status of the vertex, whether it is in the recursion stack or not. If the vertex is in the recursion stack, it means that the vertex is indeed an ancestor. So, the edge will be a backward edge.

Now try to code the DFS, it is basically a recursion process. If you are good with recursion, I’m sure you can get this. Nonetheless, I have put my code below –

/* Depth First Search Algorithm
 * using Adjacency Lists
 *
 * Authored by,
 * Vamsi Sangam.
 */

#include <stdio.h>
#include <stdlib.h>

struct node {
	int val;
	struct node * next;
};

struct node * add(struct node * head, int num)
{
	/* We use Head Insertion for inserting vertices
	 * into Linked List for O(1) Insertion.
	 */

	struct node * p = (struct node *) malloc(sizeof(struct node));

	p->val = num;
	p->next = head;

	return p;
}

void depth_first_search_explore(struct node * list[], int parent[], int vertex, int status[])
{
	if (parent[vertex] != -1) {
		//un-visited vertex
		struct node * temp = list[vertex];
		status[vertex] = 1;

		//recursively visit all vertices accessible from this Vertex
		while (temp != NULL) {

			if (parent[temp->val] == -1) {
				parent[temp->val] = vertex;
				//We started exploring from Vertex -'vertex',
				//so the Vertex - temp->val, it's
				//parent should be our initial vertex

				depth_first_search_explore(list, parent, temp->val, status);
				//Then we recursively visit everything from the child vertex
			} else {
				//Checking if the edge is a Backward Edge
				if (status[temp->val] == 1) {
					printf("\n%d ---> %d is a Backward Edge\n", vertex, temp->val);
				}
			}

			temp = temp->next;
			//After finishing, move on to next Vertex adjacent to
			//Vertex - 'vertex'
		}

		status[vertex] = 0;
	}
}

void depth_first_search(struct node * list[], int length, int parent[], int status[])
{
	int i;

	for (i = 1; i <= length; ++i) {

		if (parent[i] == -1) {
			parent[i] = 0;
			//It is a completely un-visited vertex and we start
			//our DFS from here, so it has no parent, but just
			//to mark it that we visited this node, we assign 0

			depth_first_search_explore(list, parent, i, status);
			//By this we begin to explore all the vertices reachable
			//from Vertex i
		}
	}
}

int main()
{
	int vertices, edges, i, j, v1, v2;

	printf("Enter the Number of Vertices -\n");
	scanf("%d", &vertices);

	printf("Enter the Number of Edges -\n");
	scanf("%d", &edges);

	struct node * adjacency_list[vertices + 1];
	int parent[vertices + 1];
	int status[vertices + 1];
	//Size is made (vertices + 1) to use the
	//array as 1-indexed, for simplicity

	//Must initialize your array
	for (i = 0; i <= vertices; ++i) {
		adjacency_list[i] = NULL;
		parent[i] = -1;
		status[i] = 0;
	}

	printf("\n");

	for (i = 1; i <= edges; ++i) {
		scanf("%d%d", &v1, &v2);
		adjacency_list[v1] = add(adjacency_list[v1], v2);		//Adding edge v1 ------> v2
	}

 	//Printing Adjacency List
	printf("\nAdjacency List -\n\n");
	for (i = 1; i <= vertices; ++i) {
		printf("adjacency_list[%d] -> ", i);

		struct node * temp = adjacency_list[i];

		while (temp != NULL) {
			printf("%d -> ", temp->val);
			temp = temp->next;
		}

		printf("NULL\n");
	}

	depth_first_search(adjacency_list, vertices, parent, status);

	printf("\nParent Array -\n");
	for (i = 1; i <= vertices; ++i) {
		printf("Parent of Vertex %d = %d\n", i, parent[i]);
	}

	return 0;
}

The code above has an additional feature. It prints out the Backward Edges. This is done by the technique explained above, implemented using an integer array. I know it is a dirty way to use an integer array for this, it consumes way too much space. It really needs to be a Boolean array, because we use on two values, 0 and 1. But I wanted to keep my code strictly in C, so I used an integer array. This is the Depth First Search Algorithm. It has a time complexity of O(|V| + |E|), just like the Breadth First Search. This is because, we visit every vertex once, or you could say, twice, and we cover all the edges that AdjacencyList[Vi] has, for all ViV which takes O(|E|) time, which is actually the for loop in our depth_first_search_explore() function. DFS is not very difficult, you just need to have experienced hands in recursion. You might end up getting stuck with some bug. But it is worth spending time with the bugs because they make you think in the perfect direction. So if you are not getting the code, you just have to try harder. But if you are having any doubts, feel free to comment them…! Keep practicing… Happy Coding…! 🙂

You may also like –

More in the Navigation Page ! →

Breadth First Search (BFS) Algorithm


Hello people…! In this post I will explain one of the most widely used Graph Search Algorithms, the Breadth First Search (BFS) Algorithm. Once you have learned this, you would have gained a new weapon in your arsenal, and you can start solving good number of Graph Theory related competitive programming questions.

What we do in a BFS is a simple step-by-step process, which is –

  1. Start from a vertex S. Let this vertex be at, what is called…. “Level 0”.
  2. Find all the other vertices that are immediately accessible from this starting vertex S, i.e., they are only a single edge away (the adjacent vertices).
  3. Mark these adjacent vertices to be at “Level 1”.
  4. There will be a challenge that you might be coming back to the same vertex due to a loop or a ring in the graph. If this happens your BFS will take time. So, you will go only to those vertices who do not have their “Level” set to some value.
  5. Mark which is the parent vertex of the current vertex you’re at, i.e., the vertex from which you accessed the current vertex. Do this for all the vertices at Level 1.
  6. Now, find all those vertices that are a single edge away from all the vertices which are at “Level 1”. These new set of vertices will be at “Level 2”.
  7. Repeat this process until you run out of graph.

This might sound heavy… Well atleast it would sound heavy to me if I heard it for the first time…! Many questions may pop-up in your mind, like, “How are we gonna do all that…?!”. Well, for now, focus on the concept, we will talk about the code later. And remember, we are talking about an Undirected Graph here. We will talk about Directed Graphs later. To understand the above stated steps, examine the picture below –

Breadth First Search Algorithm - Step-by-Step

Breadth First Search Algorithm – Step-by-Step

The sketch clearly shows you how we explore the vertices adjacent to a vertex and mark their levels. If you have noticed, whenever there were two ways of accessing the same vertex from multiple vertices of the same Level, i.e., in the diagram, Vertex 3 was accessible from Vertex 2 and Vertex 8, we preferred its parent to be Vertex 8, the larger number. Why is that so…? We will learn that in a short moment.

The concepts that I wish to emphasize from the above picture are, how BFS can tell you the shortest path from a given vertex (the start vertex) to all the other vertices and the number of edges or, the “length of the path”, would be the Level of that Vertex itself. This is a very important feature of the BFS, you will understand this more clearly when I explain it with the help of an example in a different post.

Now, having got some knowledge about the BFS, it is a good thing to do an exercise on this topic to really get the flow going. Try applying BFS on the Graph given. All you have to do is to implement the step-by-step process and get that final figure which I got above. And make sure you label the Levels and Parents for each vertex in the end.

bfs2

Now, we come to the code part of the Breadth First Search, in C. We use the same Adjacency List that we used in our discussion of Graph Theory Basics. Coming back to our BFS discussion, the level of each vertex is stored in a separate array and so is the case for parent of each vertex. The three arrays are initialized to appropriate values. Now recall our step-by-step process that was stated earlier. Try to put that in terms of pseudocode and then proper code. Take a while to think how you would do that. If you could code it, you are marvelous…! 😀 … If not, don’t fret, I put my code below…!

/* ==========  ========== ========== ========= */
//         Breadth First Search (BFS)          //
//               Algorithm in C                //
//                                             //
//         Functions follow Pascal Case        //
//           Convention and Variables      	   //
//         follow Camel Case Convention        //
//                                             //
//            Author - Vamsi Sangam            //
//            Theory of Programming            //
/* ========== ========== ========== ========== */

#include <stdio.h>
#include <stdlib.h>

struct Edge {
    int vertex;
    struct Edge * next;
};

// Inserts Node to the Linked List by Head Insertion - O(1)
// Returns address of head which is the newly created node.
struct Edge * AddEdge(struct Edge * currentHead, int newVertex)
{
    struct Edge * newHead
				 = (struct Edge *) malloc(sizeof(struct Edge));

    newHead->vertex = newVertex;
    newHead->next = currentHead;

    return newHead;
}

void BreadthFirstSearch(
						struct Edge * adjacencyList[],
						int vertices,
						int parent[],
						int level[],
						int startVertex
					   )
{
    struct Edge * traverse;
    int i, par, lev, flag = 1;
    // 'lev' represents the level to be assigned
    // 'par' represents the parent to be assigned
    // 'flag' used to indicate if graph is exhausted

    lev = 0;
    level[startVertex] = lev;
    // We start at startVertex

    while (flag) {
        flag = 0;
        for (i = 1; i <= vertices; ++i) {
            if (level[i] == lev) {
                flag = 1;
                traverse = adjacencyList[i];
                par = i;

                while (traverse != NULL) {
                    if (level[traverse->vertex] != -1) {
                        traverse = traverse->next;
                        continue;
                    }

                    level[traverse->vertex] = lev + 1;
                    parent[traverse->vertex] = par;
                    traverse = traverse->next;
                }
            }
        }

        ++lev;
    }
}

int main()
{
    int vertices, edges, i, v1, v2;

    printf("Enter the Number of Vertices -\n");
    scanf("%d", &vertices);

    printf("\nEnter the Number of Edges -\n");
    scanf("%d", &edges);

    struct Edge * adjacencyList[vertices + 1];
    // Size is made (vertices + 1) to use the
    // array as 1-indexed, for simplicity

    int parent[vertices + 1];
    // Each element holds the Node value of its parent
    int level[vertices + 1];
    // Each element holds the Level value of that node

    // Must initialize your array
    for (i = 0; i <= vertices; ++i) {
        adjacencyList[i] = NULL;
        parent[i] = 0;
        level[i] = -1;
    }

    for (i = 1; i <= edges; ++i) {
        scanf("%d%d", &v1, &v2);

        // Adding edge v1 --> v2
        adjacencyList[v1] = AddEdge(adjacencyList[v1], v2);

		// Adding edge v2 --> v1
		// Remove this if you want a Directed Graph
        adjacencyList[v2] = AddEdge(adjacencyList[v2], v1);
    }

    // Printing Adjacency List
    printf("\nAdjacency List -\n\n");
    for (i = 1; i <= vertices; ++i) {
        printf("adjacencyList[%d] -> ", i);

        struct Edge * traverse = adjacencyList[i];

        while (traverse != NULL) {
            printf("%d -> ", traverse->vertex);
            traverse = traverse->next;
        }

        printf("NULL\n");
    }

    printf("\nEnter a Start Vertex - ");
    scanf("%d", &v1);

    BreadthFirstSearch(adjacencyList, vertices, parent, level, v1);

    // Printing Level and Parent Arrays
    printf("\nLevel and Parent Arrays -\n");
    for (i = 1; i <= vertices; ++i) {
        printf("Level of Vertex %d is %d, Parent is %d\n",
								  i, level[i], parent[i]);
    }

    return 0;
}

Try using the above example given as practice as the sample input to your code, so that you can easily compare the results. Now, the important point here is when we insert a vertex into the Adjacency List, we follow Head Insertion to get O(1) Insertion. What happens due to this is that, the Linked List will have numbers in the descending order.

So, when we are applying BFS for adjacent vertices of a given node, the Vertex with the higher number is met first. And then we explore starting by that higher numbered Vertex. This is why whenever we had a choice in approaching a vertex, we preferred approaching from the vertex which had the bigger number, why…? Due to Head Insertion…! If you had used Tail Insertion, this would be reversed.

Other Implementations of BFS

This is the overview of Breadth First Search Algorithm. It has a computational complexity of O(|V| + |E|), which is pretty fast. But why O(|V| + |E|)…? If you think about the algorithm a little bit, we cover all the |V| vertices level-by-level, checking all the |E| edges twice (for an Undirected Graph). Once the level is set for a subset of vertices we don’t visit them again. Put an itty-bitty thought into it and I’m sure you’ll get the idea…! 😉 … But, the code above runs slower than O(|V| + |E|)… To achieve the proper complexity we must use a Queue.

We can use BFS in the following scenarios –

  • Shortest Path or Quickest Path (if all edges have equal weight).
  • Finding the Length of Shortest Path between two Vertices.

With the knowledge of BFS you can start solving Graph Theory related problems. It really depends on your logic how you will apply the BFS to the given problem. And there is only one way to develop it… Practice…! So, keep practicing… Feel free to comment your doubts..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Happy Coding…! 🙂

Go to the Homepage →