We already know what’s topological sort of a directed acyclic graph. So why do we need a revision of this algorithm? First of all I never mentioned its complexity, thus to understand why we do need a revision let’s get again on the algorithm.
We have a directed acyclic graph (DAG). There are no cycles so we must go for some kind of order putting all the vertices of the graph in such an order, that if there’s a directed edge (u, v), u must precede v in that order.
The process of putting all the vertices of the DAG in such an order is called topological sorting. It’s commonly used in task scheduling or while finding the shortest paths in a DAG.
The algorithm itself is pretty simple to understand and code. We must start from the vertex (vertices) that don’t have predecessors.
As we saw in the previous post, the algorithm of Dijkstra is very useful when it comes to find all the shortest paths in a weighted graph. However it has one major problem! Obviously it doesn’t work correctly when dealing with negative lengths of the edges.
We know that the algorithm works perfectly when it comes to positive edges, and that is absolutely normal because we try to optimize the inequality of the triangle.
Since Dijkstra’s algorithm make use of a priority queue normally we get first the shortest adjacent edge to the starting point. In our very basic example we’ll get first the edge with the length of 3 -> (S, A).
So far we know how to implement graph depth-first and breadth-first search. These two approaches are crucial in order to understand graph traversal algorithms. However they are just explaining how we can walk through in breadth or depth and sometimes this isn’t enough for an efficient solution of graph traversal.
In the examples so far we had an undirected, unweighted graph and we were using adjacency matrices to represent the graphs. By using adjacency matrices we store 1 in the A[i][j] if there’s an edge between vertex i and vertex j. Otherwise we put a 0. However the value of 1 gives us only the information that we have an edge between two vertices, which is not always enough when designing graphs.
Indeed graphs can be weighted. Sometimes the path between two vertices can have a value. Thinking of a road map we know that distances between cities are represented in miles or kilometers. Thus often representing a road map as a graph, we don’t put just 1 between city A and city B, to say that there is a path between them, but also we put some meaningful information – let’s say the distance in miles between A and B.
Note that this value can be the distance in miles, but it can be something else, like the time in hours we’ve to walk between those two cities. In general this value is a function of A and B. So if we keep the distance between A and B we can say this function is F(A, B) = X, or distance(A, B) = X miles.
Of course in this particular example F(A, B) = F(B, A), but this isn’t always true in practice. We can have a directed graph where F(A, B) != F(B, A).
Here I talk about distance between two cities and it is the edge that brings some additional information. However sometimes we have to store the value of the vertices. Let’s say I’m playing a game (like chess) and each move brings me some additional benefit. So each move (vertex) can be evaluated with some particular value. Thus sometimes we don’t have a function of and edge like F(A, B), but function of the vertices, like F(A) and F(B).
In breadth-first search and depth-first search we just pick up a vertex and we consecutively walk through all its successors that haven’t been visited yet.
So in DFS in particular we started from left to right in the array above. So the first node that has to be explored is vertex “1”.
However sometimes, as I said above, we have weighted graphs, so the question is – is there any problem, regarding to the algorithm speed, if we go consecutively through all successors. The answer in general is yes, so we must modify a bit our code in order to continue not with the first but with the best matching successor. By best-matching we mean that the successor should match some criteria like – minimal or maximal value. Continue reading Computer Algorithms: Graph Best-First Search→
Although this post is supposed to be about algorithms I’ll cover more on graphs and their computer representation. I consider this very important, because there are lots of problems solved by using graphs and it is important to understand different types of representation.
First of all let’s try to explain what is a graph?
A graph is a specific data structure known in the computer science, that is often used to give a model of different kind of problems where a set of objects relate to each other in some way . For instance, trees are mainly used in order to represent a well-structured hierarchy, but that isn’t enough when modeling objects of the same type. Their relation isn’t always hierarchical! A typical example of graph is a geo map, where we have cities and the roads connecting them. In fact most of the problems solved with graphs relate to finding the shortest or longest path.
Although this is one very typical example actually a huge set of problems is can be solved by using graphs.