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.
We already know how we can find the shortest paths in a graph starting from a given vertex. Practically we modified breadth-first search in order to calculate the distances from s to all other nodes reachable from s. We know that this works because BFS walks through the graph level by level.
BFS is often used to find shortest paths between a starting node (s) and all other reachable nodes in a graph!
Some sources give a very simple explanation of how BFS finds the shortest paths in a graph. We must just think of the graph as a set of balls connected through strings.
We can think of a graph as a set of balls connected through strings!
As we can see by lifting the ball called “S” all other balls fall down. The closest balls are directly connected to “s” and this is the first level, while the outermost balls are those with longest paths.
Breadth-first search works much like the image above – it explores the graph level by level, thus we’re sure that all the paths are the shortest!
Clearly edges like those between A and B doesn’t matter for our BFS algorithm because they don’t make the path from S to C through B shorter. This is also known as the triangle inequality, where the sum of the lengths of two of the sides of the triangle is always greater than the length of the third side.
What the triangle inequality says us is that if we have a direct edge between two nodes – that must be the shortest path between them!
We must only answer the question is BFS the best algorithm that finds the shortest path between any two nodes of the graph? This is a reasonable question because as we know by using BFS we don’t find only the shortest path between given vertices i and j, but we also get the shortest paths between i and all other vertices of G. This is an information that we actually don’t need, but can we find the shortest path between i and j without that info? Continue reading Computer Algorithms: Dijkstra Shortest Path in a Graph→
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).
In order to sort a graph using topological sort we need this graph to be acyclic and directed!
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.
The output of topological sort should be a list of vertices!
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.
In order to walk through an unweithed graph using DFS, we chose consecutively each successor of node i!
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”.
0:[0,1,0,0,1,1]
0: [0, 1, 0, 0, 1, 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→
Since we already know how to represent graphs, we can go further for some very simple approaches of walking through them. Passing by all the vertices of a graph is a fundamental technique for most of the graph algorithms, such as finding shortest/longest paths, etc.
First thing to note is that graphs are not trees, in most of the cases, so walking through them can’t start from a root, as we do with trees. What we must do first is to decide from where to start – in other words – choosing a starting vertex.
It’s clear that depending on the starting point we can get different passes through the graph. Thus choosing a starting point can be very important for our algorithm!
After that we need to know how to proceed. There are two approaches mostly known as “breadth first” and “depth first” search. While depth first search start from a vertex and goes as far as possible, then walks back and passes through vertices that haven’t been visited yet, breath first search is an approach of passing through all the neighbors of the node first, and then go to the next level. Continue reading Computer Algorithms: Graph Breadth First Search→
