Topological sorting

principle

• An acyclic directed graph is called a directed acyclic graph.
• Directed acyclic graph is an effective tool to describe the process of engineering, planning, production and system. There are usually certain constraints between activities. For example, sequence.
• A directed graph that uses nodes to represent activities and arcs to represent the priority relationship between activities is called AOV network.
• In AOV network, if < i, J > is the arc in the graph, then node i is the direct precursor of node j and node j is the direct successor of node i.
• The arc in AOV network represents the restrictive relationship between activities.
• Topological sorting refers to arranging the nodes in the AOV network into a linear sequence, which must meet the following requirements: if there is a path from node i to node j, node i must precede node j in this sequence.
• The basic idea of topological sorting: ① select a node without precursor and output it; ② Delete the node and all outgoing edges of the node from the graph; ③ Repeat steps 1 and 2 until there are no nodes without precursors; ④ If the number of output nodes is less than the number of nodes in the AOV network, it indicates that there are rings in the network. Otherwise, the output sequence is the topological sequence.
• Topological sorting is not unique.

Algorithm design

1. Calculate the in degree of each node, store it in the array indegree [], and put the node with in degree of 0 into stack S.
2. If the stack is not empty, repeat the following operations: ① get the top element I out of the stack and save it to the topology sequence array topo []; ② Reduce the input of all adjacent points of node i by 1. If the input is 0 after subtracting 1, it will be immediately stacked in S.
3. If the number of output nodes is less than the number of nodes in the AOV network, it indicates that there are rings in the network, otherwise the topology sequence is output.

Algorithm implementation

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=105;
int map[maxn][maxn],indegree[maxn],topo[maxn];
int n,m;
stack<int>s;
bool TopoSort(); //Topological sorting
int main(){
    cin>>n>>m;
    memset(map,0,sizeof(map));
    memset(indegree,0,sizeof(indegree));
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        map[u][v]=1;
        indegree[v]++;
    }
    TopoSort();
    for(int i=0;i<n-1;i++)
        cout<<topo[i]<<" ";
    cout<<topo[n-1]<<endl;
    return 0;
}

bool TopoSort(){ //Topological sorting
    int cnt=0;
    for(int i=0;i<n;i++)
        if(indegree[i]==0) //Stack nodes with a degree of 0
            s.push(i);
    while(!s.empty()){ //Stack is not empty
        int u=s.top(); //Stack top element out of stack
        s.pop();
        topo[cnt++]=u;
        for(int j=0;j<n;j++)
            if(map[u][j])
                if(--indegree[j]==0) //If the input degree is 0 after subtracting 1, it will be stacked for s
                    s.push(j);
    }
    if(cnt<n) return 0;
    return 1;
}

Input:

6 8
0 1
0 2
0 3
2 1
2 4
3 4
5 3
5 4

Output:

5 0 3 2 4 1

Training 1: family tree

Title Description

The Martian kinship system is confusing. At the Mars planetary Council, the confusing genealogy system led to some embarrassment; In order not to offend anyone in all discussions, the old Martians speak first, not the young or the youngest childless. However, maintaining this order is not a trivial task. Martians do not always know who their parents and grandparents are. If a grandson speaks first instead of his young great grandfather, there will be a mistake. Prepare procedures to ensure that each member of the Council speaks before each of its descendants.

Input: Line 1 contains the integer N(1 \leq N \leq 100), which indicates the number of members of the Mars planetary Council. Member numbers are 1 ~ N. The next N lines, line I, contain the list of children of the i-th member. The list of children may be empty, and the list ends with 0.

Output: output a series of speaker numbers in a single line, separated by spaces. If several sequences meet the conditions, output any one, and there is at least one such sequence.

Algorithm implementation

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=105;
int map[maxn][maxn],indegree[maxn],topo[maxn];
int n;
stack<int>s;
void TopoSort(); //Topological sorting
int main(){
    cin>>n;
    memset(map,0,sizeof(map));
    memset(indegree,0,sizeof(indegree));
    for(int i=1;i<=n;i++){
        int v;
        while(cin>>v&&v){
            map[i][v]=1;
            indegree[v]++;
        }
    }
    TopoSort();
    for(int i=1;i<n;i++)
        cout<<topo[i]<<" ";
    cout<<topo[n]<<endl;
    return 0;
}
void TopoSort(){ //Topological sorting
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(indegree[i]==0)
            s.push(i);
    while(!s.empty()){
        int u=s.top();
        s.pop();
        topo[++cnt]=u;
        for(int j=1;j<=n;j++)
            if(map[u][j])
                if(--indegree[j]==0)
                    s.push(j);
    }
}

Input:

5
0
4 5 1 0
1 0
5 3 0
3 0

Output:

2 4 5 3 1

Training 2: full sorting

Title Description

The ascending sort sequence of different values is a sequence of elements sorted from small to large using some form of less than operator.