Topology Sorting 拓扑排序

Data Structure 作业

已知一个文件: the first character of the file is the number of elements

Then there will be pairs of numbers

such as: 3 1

1 4

For the first pair, it means 1 is after 3. In the topology, 3 precedes to 1.

One example of the file is:

5

3 1

1 4

2 0

0 1

0 4

3 4

I should sort them according to this information.

The method I used is called successor list.

First I will build a successor list:

0-->1,4

1-->4

2-->0

3-->4

The implementation of this is simple, go over the file word by word, after reading the element number 5.

If it's the first, third, 5th ... of the word then save the number to temporary variable, if it's 2nd 4th 6th or .... Save it to the cache[temp], also increment count[2nd 4th 6th or ...] vector by 1.

After that I will check if there is an element in count vector with value 0(the element in the vector is initialed to all 0)

If there is push it to the no_predecessor list. The procedure is the first round of checking

After that, pop element from no_predecessor for the number of times( in this case the number is 5), push the popped element to predecessor list;if no_predecessor.empty() is true before 5 times. Then return the function with empty list.

Use the index of popped element and go to cache[index] list, push the element there to no_predecessor list.

After the loop check if there is element in count[] list with value greater than 0

If there is return empty predecessor list.