Shulou(Shulou.com)06/02 Report--

This article introduces you how to achieve topological sorting in C#, the content is very detailed, interested friends can refer to, hope to be helpful to you.

. Principle

Let's start with a basic definition:

In graph theory, topological sorting (Topological Sorting) is a linear sequence of all vertices of a directed acyclic graph (DAG, Directed Acyclic Graph). And the sequence must meet the following two conditions:

Each vertex appears only once.

If there is a path from vertex A to vertex B, then vertex An appears in front of vertex B in the sequence.

Directed acyclic graphs (DAG) have topological sorting, while non-DAG graphs have no topological sorting.

For example, there is a collection whose dependency is shown in the following figure:

You can see that he has a dependency:

Module D depends on Module E and Module B.

Module E depends on Module B and Module C.

Module B depends on Module An and Module C.

Module C depends on Module A.

Module A has no dependence.

This is a DAG diagram, and to get its topological sort, a simple step is as follows:

Select a vertex without a precursor from the DAG diagram and output it.

Removes the vertex from the DAG graph and the directed edge that starts with it.

Repeat steps 1 and 2 until the current DAG graph is empty or there are no precursory vertices in the current graph.

Following the above steps, let's try a sort.

The final sort result is:

Module D-> Module E-> Module B-> Module C-> Module A

Emmmm, in fact, a directed acyclic graph can have one or more topological sequences, because sometimes there is a situation, that is, the following cases:

At this time, you may have these two results.

D-> E-> B-> C-> F-> A

D-> E-> B-> F-> C-> A

Because F and C are level, it doesn't matter if their initialization order is different, because their dependency levels are the same, but careful friends may find that this order seems to be reversed, and we need to reverse it again.

3. Realize

The above method is only applicable when the degree of penetration is known, that is to say, the content itself exists in a directed acyclic graph. If you sort the topology according to the above method, you need to maintain a queue with a degree of 0. then remove the vertex penetration that points to the vertex with the degree of zero in each iteration.

For example, there is the following figure:

According to our previous algorithm,

First initialize the queue, adding vertices 5 and 4 with a degree of 0 to the queue.

Executes a While loop, provided that the queue is not empty.

Then take out 4 first.

Then subtract 1 from the degree of entry of vertex 0 and vertex 1 it points to.

When subtracting the entry degree of pointing to the vertex, it is also determined whether the value of the subtracted vertex is 0.

Here the degree of 1 is subtracted from 1 to 0, which is added to the queue.

The vertex entry degree of 0 minus 1 is 1.

The queue now has two vertices, 5 and 1, and loop determines that the queue is not empty.

5 points to the vertex 0 entry degree minus 1, vertex 0 entry degree is 0, insert queue.

In this repeated loop, the final queue is all empty, exit the loop, and get the results of topological sorting 4, 5, 2, 0, 3, 1.

4. Depth-first search implementation

The depth-first algorithm is used in the code in reference 1, which applies to directed acyclic graphs.

There are the following directed ring graphs G2:

Do a depth-first traversal of the above figure G2, starting with vertex A with a degree of 0:

Its steps are as follows:

Visit A.

Visit B.

Visit C.

After visiting B, you should visit another vertex of B, which can be random or ordered, depending on the sequence order you store. Visit C first.

Visit E.

Visit D.

Access D here because B has already been accessed, so access vertex D.

Visit F.

Because vertex C has already been accessed, you should backtrack another vertex F that accesses vertex B, pointing to the directed edge.

Visit G.

So the final access order is A-> B-> C-> E-> D-> F-> G, and note that the order is not quite right.

It looks similar to the previous method. In the implementation, the Sort () method contains a visited dictionary inside to mark the vertices that have been visited, and sorted is a sorted list of collections.

In the dictionary, Key is the value of the vertex, and its value value is used to indicate whether all paths have been accessed, true indicates that the vertex is being processed, and false indicates that the processing has been completed.

Now let's write about implementation:

Results:

On how to achieve topological sorting in C# to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.