Find it on GitHub
Tag Archives: Tree
Computer Algorithms: Prim’s Minimum Spanning Tree
Introduction
Along with the Kruskal’s minimum spanning tree algorithm, there’s another general algorithm that solves the problem. The algorithm of Prim.
As we already know the algorithm of Kruskal works in a pretty natural and logical way. Since we’re trying to build a MST, which is naturally build by the minimal edges of the graph (G), we sort them in a non-descending order and we start building the tree.
During the whole process of building the final minimum spanning tree Kruskal’s algorithm keeps a forest of trees. The number of trees in that forest decreases on each step and finally we get the minimum weight spanning tree.
A key point in the Kruskal’s approach is the way we get the “next” edge from G that should be added to one of the trees of the forest (or to connect two trees from the forest). The only thing we should be aware of is to choose an edge that’s connecting two vertices – u and v and these two shouldn’t be in the same tree. That’s all.
An important feature of the Kruskal’s algorithm is that it builds the MST just by sorting the edges by their weight and doesn’t care about a particular starting vertex.
In the same time there’s another algorithm that builds a MST – the algorithm of Prim designed by Robert Prim in 1957. Continue reading Computer Algorithms: Prim’s Minimum Spanning Tree
Computer Algorithms: Kruskal’s Minimum Spanning Tree
Introduction
One of the two main algorithms in finding the minimum spanning tree algorithms is the algorithm of Kruskal. Before getting into the details, let’s get back to the principles of the minimum spanning tree.
We have a weighted graph and of all spanning trees we’d like to find the one with minimal weight. As an example on the picture above you see a spanning tree (T) on the graph (G), but that isn’t the minimum weight spanning tree!
Computer Algorithms: Shortest Path in a Graph
Introduction
Since with graphs we can represent real-life problems it’s almost clear why we would need an efficient algorithm that calculates the shortest path between two vertices. Getting back to our example of a road map we can use such an algorithm in order to find the shortest path between two cities. This example, of course, is very basic indeed, but it can give us a clear example of where shortest path can be applied.
In the other hand, we can model an enormous field of real-life problems using graphs – not only road maps. As we already know, whenever we have relations between different abstract objects we can refer an efficient graph algorithm.
OK, so we need a shortest path algorithm, but before we proceed with the exact algorithm first we’ll need to answer some questions and give some definitions.
Overview
First we need a definition of the terms distance and path between two nodes. A path is considered to be the sequence of vertices (or edges if you wish) between two vertices i and j. Of course we assume that there might be no path between any to vertices in the graph! Also we assume that this definition relates both for directed and undirected graphs. After we have the definition of a path we can proceed by defining a “distance”, which is said to be the number of edges in the path between i and j.
Computer Algorithms: Topological Sort of a Graph
Introduction
Let’s assume we have a list of tasks to accomplish. Some of the tasks depend on others, so we must be very careful with the order of their execution. If the relationship between these tasks were simple enough we could represent them as a linked list, which would be great, and we would know the exact order of their execution. The problem is that sometimes the relations between the different tasks are more complex and some tasks depend on two or more other tasks, which in their turn depend on one or more tasks, etc.
Thus we can’t model this problem using linked lists or trees. The only rational solution is to model the problem using a graph. What kind of graph do we need? Well, we definitely need a directed graph, to desribe the relations, and this graph shouldn’t have cycles. So we need the so called directed acyclic graph (DAG).
Why we don’t what a cycle in the graph? The answer of this question is simple and obvious. In case of cyclic graph, we wouldn’t be able to determine the priority of task execution, thus we won’t be able to sort the tasks properly.
Now the solution we want is to sort the vertices of the graph in some order so for each edge (u, v) u will precede v. Then we’ll have a linear order of all tasks and by starting their execution we’ll know that everything will be OK.
This kind of sort is also known as “topological” sort (or topsort) and it is one of the very basic graph algorithms. Continue reading Computer Algorithms: Topological Sort of a Graph