4.4 拓扑排序问题

拓扑排序-减治法

问题描述

考虑五门必修课的一个集合{C1, C2, C3, C4, C5},一个在职的学生必须在某个阶段修完这几门课程。可以按照任何次序学习这些课程，只要满足下面这些条件：

• C1和C2没有任何先决条件；
• 修完C1 和C2才能修C3；
• 修完C3 才能修C4；
• 修完C3、C4才能修C5；
• 这个学生每个学期只能修一门课程。

若用一个图来建模，它的顶点代表课程，有向边表示先决条件，该问题为：是否可以按照这种次序列出它的顶点，使得对于图中每一条边来说，边的起始顶点总是排在边的结束顶点之前。

这个问题称为拓扑排序。

如果有向图具有一个有向的回路，该问题是无解的。因此，为了使得拓扑排序成为可能，问题中的图必须是一个无环有向图。

拓扑排序-减治原理

基于减（减一）治技术的一个直接实现：重复以下过程：

1. 在余下的有向图中求出一个源，它是一个没有输入边的顶点；
2. 然后把该源和所有从它出发的边都删除。（如果有多个这样的源，可以任意选择一个；如果这样的源不存在，算法停止，因为该问题是无解的）
3. 顶点被删除的次序就是拓扑排序的一个解。

// 拓扑排序——循环入度为零
vector<int> tuopu1(vector<vector<int>> vec){
    vector<int> res;
    vector<int> in(vec.size(),0);
    vector<int> flag(vec.size(),0);
    for(int i=0;i<vec.size();i++){
        for(int j=0;j<vec[i].size();j++){
            in[vec[i][j]]++;
        }
    }
    
    for(int i=0;i<vec.size();i++){
        int j;
        // 查找入度为零的节点，添加到结果中，并标记
        for(j=0;j<vec.size();j++){
            if(in[j]==0 && flag[j]==0){
                flag[j]=1;
                res.push_back(j);
                break;
            }
            
        }
        // 将该节点的下一个节点的入度减1
        for(auto a:vec[j]){
            in[a]--;
        }
    }
    return res;
}

拓扑排序-深度搜索

基于深度优先搜索的方法实现

深度优先搜索（或广度优先搜索）整个图，将出度为0的顶点入栈，中途要判断是否会形成环，最后输出栈得到的序列就是该图的一种拓扑排序。

// 拓扑排序——深度递归+栈
void tuopu2(vector<vector<int>> &vec,stack<int> &st,vector<int> &flag,int node){
      for(int i=0;i<vec[node].size();i++){
            if(flag[vec[node][i]]==0){
                tuopu2(vec,st,flag,vec[node][i]);
            }
      }
      if(flag[node]==0){
            st.push(node);
            flag[node]=1;
      }
}

2 深度学习算子

问题描述

一般深度学习网络有若干算子组成，假设一个深度学习网络模型是一个有向无环图。若算子A依赖算子B的输出，则晋档算子B执行完成后才能执行算子A,没有依赖关系的算子可以并行执行。已知每个算子的执行时间，请计算运行整个网络所需要的的最小执行时间。

1. 不考虑算子之间的传输时间
2. 第一个算子为输入算子且仅有一个输入算子
3. 算子的索引从0开始

输入描述

N+1行。N为算子的总个数，第一行输入N,N<100.第j行输入代表索引为j-2的算子的属性。包括算子的时间和算子的后继算子。

实例

4
10 1 2
5
1 3
2

问题分析

1. 图问题
2. 拓扑排序
3. 深度搜索

策略选择

1. 深度优先搜索
2. 记录最长的路径

算法设计

算法分析

时间复杂度 O(n*v)
空间复杂度 O(n)

算法实现

// 使用深度优先搜索计算
int dfs(vector<vector<int>> &vec,vector<int> &cost,int node,int c){
    int max_cost=c+cost[node];
    // cout<<max_cost<<endl;
    for(int i=0;i<vec[node].size();i++){
        max_cost = max(max_cost,dfs(vec,cost,vec[node][i],c+cost[node]));
    }
    return max_cost;
}
int main(){
    string input="4\nsoftmax 10 1 2\nrelu 5\nconv1 1 3 1\nsoftmax 2";
    istringstream cin(input);
    int N ;
    cin>>N;
    cout<<N<<endl;
    // 表示每个边花费的时间
    vector<int> cost(N,0);
    // 使用邻接链表表示关系吧。单点触发的所有边
    vector<vector<int>> vec(N,vector<int>());
    cin.ignore();
    // string input2;
    // getline(cin,input2);
    for(int i=0;i<N;i++){
        string line;
        getline(cin,line,'\n');
        // cout<<line<<endl;
        istringstream is(line);
        string name;
        is>>name;
        is>>cost[i];
        int next;
        while(is>>next){
            vec[i].push_back(next);
        }
        cout<<name<<":"<<cost[i]<<endl;
    }
    // for(auto a:vec){
    //     for(auto b:a){
    //         cout<<b<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<"result:"<<dfs(vec,cost,0,0)<<endl;

    // 进行拓扑排序并查看结果

    vector<int> res = tuopu1(vec);
    for(auto a:res){
        cout<<a<<" ";
    }
    cout<<endl;

    vector<int> flag(vec.size(),0);
    stack<int> st;
    tuopu2(vec,st,flag,0);
    vector<int> res2;
    while(!st.empty()){
        cout<<st.top()<<" ";
        res2.push_back(st.top());
        st.pop();
        
    }
    cout<<endl;
    // 然后根据拓扑排序计算最长时间。没哟必要

}