August 4, 2010 at 16:40Topological sorting
Topological sort (Topological sort) - one of the main algorithms on graphs, which is used to solve many more complex problems.
The task of topological sorting of the graph is as follows: indicate a linear order at its vertices such that any edge leads from a vertex with a lower number to a vertex with a higher number. Obviously, if the graph has cycles, then this order does not exist.
An oriented network (or just a network) is called an outline-free oriented graph. In tasks of this kind, only finite networks are considered.
It can be seen from the figure that the graph is not sorted, since the edge from the vertex with number 4 leads to the vertex with a lower number ( 2 ).
There are several ways of topological sorting - from the most famous:
Dfs or bypass in depth (Eng. The Depth-first search , abbreviated as the DFS ) - a method of graph traversal. The search algorithm is described as follows: for each vertex that has not been passed, it is necessary to find all the adjacent vertices that have not passed and repeat the search for them.
You can read more about the search in depth in an article on Habré .
We start the traversal in depth, and when the vertex is processed, we push it onto the stack. At the end of the tour, the peaks are taken out of the stack in depth. New numbers are assigned in the order of pulling from the stack.
Color:During the walk in depth, 3 colors are used. Initially, all the peaks are white. When the top is discovered, paint it gray. When the list of all peaks adjacent to it is viewed, we paint it black.
I think it will be easier to consider this algorithm as an example:
↑ We have a contour-oriented graph. Initially, all the vertices are white, and the stack is empty. Let's start the walk in depth from the top number 1.
↑ Go to the top number 1. Paint it gray.
↑ There is an edge from vertex number 1 to vertex number 4. Go to vertex number 4 and paint it gray.
↑ There is an edge from vertex number 4 to vertex number 2. Go to vertex number 2 and paint it gray.
↑ From vertex number 2 there are no edges that do not go to black vertices. Go back to vertex number 4. Paint vertex number 2 in black and put it on the stack.
↑ There is an edge from vertex number 4 to vertex number 3. Go to vertex number 3 and paint it gray.
↑ From vertex number 3 there are no edges that do not go to black vertices. Go back to vertex number 4. Paint vertex number 3 black and put it on the stack.
↑ From vertex number 4 there are no edges that do not go to black peaks. Go back to vertex number 1. Paint vertex number 4 black and put it on the stack.
↑ From vertex number 1 there are no edges that do not go to black vertices. We paint it black and put it on the stack. Dot bypass is over.
↑ In turn, we get all the vertices from the stack and assign them numbers 1, 2, 3, 4, respectively. The topological sorting algorithm is complete. Count is sorted.
Topological sorting is used in a variety of situations, for example, in parallelizing algorithms, when according to some description of the algorithm it is necessary to compose a dependency graph of its operations and, sorting it topologically, determine which of the operations are independent and can be executed in parallel (simultaneously). An example of the use of topological sorting is the creation of a site map where a tree-like partition system takes place. (if interested - to google)
As for the implementation - here you can find 22 lines of code that implement this algorithm (everything is carefully commented out)
The task of topological sorting of the graph is as follows: indicate a linear order at its vertices such that any edge leads from a vertex with a lower number to a vertex with a higher number. Obviously, if the graph has cycles, then this order does not exist.
An oriented network (or just a network) is called an outline-free oriented graph. In tasks of this kind, only finite networks are considered.
↑ An example of a directed unsorted graph to which topological sorting is applicable
It can be seen from the figure that the graph is not sorted, since the edge from the vertex with number 4 leads to the vertex with a lower number ( 2 ).
There are several ways of topological sorting - from the most famous:
- Demucron Algorithm
- Sorting method for representing the graph as multiple levels
- Topological sorting method using depth traversal
The essence of the algorithm
Dfs or bypass in depth (Eng. The Depth-first search , abbreviated as the DFS ) - a method of graph traversal. The search algorithm is described as follows: for each vertex that has not been passed, it is necessary to find all the adjacent vertices that have not passed and repeat the search for them.
You can read more about the search in depth in an article on Habré .
We start the traversal in depth, and when the vertex is processed, we push it onto the stack. At the end of the tour, the peaks are taken out of the stack in depth. New numbers are assigned in the order of pulling from the stack.
Color:During the walk in depth, 3 colors are used. Initially, all the peaks are white. When the top is discovered, paint it gray. When the list of all peaks adjacent to it is viewed, we paint it black.
I think it will be easier to consider this algorithm as an example:
↑ We have a contour-oriented graph. Initially, all the vertices are white, and the stack is empty. Let's start the walk in depth from the top number 1.
↑ Go to the top number 1. Paint it gray.
↑ There is an edge from vertex number 1 to vertex number 4. Go to vertex number 4 and paint it gray.
↑ There is an edge from vertex number 4 to vertex number 2. Go to vertex number 2 and paint it gray.
↑ From vertex number 2 there are no edges that do not go to black vertices. Go back to vertex number 4. Paint vertex number 2 in black and put it on the stack.
↑ There is an edge from vertex number 4 to vertex number 3. Go to vertex number 3 and paint it gray.
↑ From vertex number 3 there are no edges that do not go to black vertices. Go back to vertex number 4. Paint vertex number 3 black and put it on the stack.
↑ From vertex number 4 there are no edges that do not go to black peaks. Go back to vertex number 1. Paint vertex number 4 black and put it on the stack.
↑ From vertex number 1 there are no edges that do not go to black vertices. We paint it black and put it on the stack. Dot bypass is over.
↑ In turn, we get all the vertices from the stack and assign them numbers 1, 2, 3, 4, respectively. The topological sorting algorithm is complete. Count is sorted.
Application
Topological sorting is used in a variety of situations, for example, in parallelizing algorithms, when according to some description of the algorithm it is necessary to compose a dependency graph of its operations and, sorting it topologically, determine which of the operations are independent and can be executed in parallel (simultaneously). An example of the use of topological sorting is the creation of a site map where a tree-like partition system takes place. (if interested - to google)
As for the implementation - here you can find 22 lines of code that implement this algorithm (everything is carefully commented out)
