graph traversals

Topological Ordering for Graphs

Introduction The topological ordering for graphs get many applications where the nature of the problem is ordered sequential processing. Few of the problems in this category are as follows: Dynamic Linking/Loading of programs while building and execution. Deciding the pre-requisites in a course structure. Job Scheduling in Processors or Assembly Line Processing. Building an Alien Dictionary from given words. There are many more but I am sure you got the idea. When we say topological ordering of graph, we are necessarily talking about the ordering of the vertices of the graph. Un...
Read More

Shortest Path Using Bellman Ford Algorithm

Introduction This post about Bellman Ford Algorithm is a continuation of the post Shortest Path Using Dijkstra's Algorithm. While learning about the Dijkstra's way, we learnt that it is really efficient an algorithm to find the single source shortest path in any graph provided it has no negative weight edges and no negative weight cycles. The running time of the Dijkstra's Algorithm is also promising, O(E +VlogV) depending on our choice of data structure to implement the required Priority Queue. Why Bellman Ford Algorithm? There can be scenarios where a graph may contain negative weight cycle...
Read More

Further Reading for Minimum Spanning Tree

Introduction This is a supplement to the posts for Minimum Spanning Tree and their Analysis. Check out the other related articles in the following section. Further Reading for Minimum Spanning Tree This section is meant to be read in conjunction to the post Minimum Spanning Tree - Prim's Algorithm The minimum spanning tree of a Graph is the union of minimum spanning trees of its connected components. This is a very important observation and it must be discussed in length and breadth because this will help us design our algorithm for MST in a better way. Why is it so important to underst...
Read More