任务调度的合理性【拓扑排序】

太过爱你忘了你带给我的痛 2023-10-03 17:44 5阅读 0赞

### 拓扑排序：拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。 且该序列必须满足下面两个条件： 每个顶点出现且只出现一次。 若存在一条从顶点A 到顶点B 的路径，那么在序列中顶点A 出现在顶点B 的前面 ###

拓扑排序适用于求工程的合理性。  
**拓扑排序的思路：**

1.  将所有入度为0的点入栈。
2.  依次遍历输出栈中的点，并经其所在的边都删除，更新其他点的入度。
3.  再 将所有入度为0的点入栈（重复以上过程）

下面以一道经典例题为例：  
**任务调度的合理性**  
*假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。  
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。  
但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。*

**输入格式:**  
输入说明：输入第一行给出子任务数N（≤100），子任务按1~N编号。随后N行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数K，随后给出K个子任务编号，整数之间都用空格分隔。

**输出格式:**  
如果方案可行，则输出1，否则输出0。

**输入样例1:**

12
    0
    0
    2 1 2
    0
    1 4
    1 5
    2 3 6
    1 3
    2 7 8
    1 7
    1 10
    1 7

**输出样例1：**

**输入样例2：**

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

**输出样例2：**

**附带代码（分析过程见代码注释）**

#include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    
    const int N = 110;
    int n;
    int in[N]; //入度
    vector <int> ctask[N]; //存储某个任务的依赖集合里有哪些子任务
    queue <int> topsort;    //拓扑排序
    
    int main()
    {
        
        cin >> n;
    
        int k;
        int x;
        for(int i = 1; i <= n; i ++)
        {
        
            cin >> k;
            while(k--)
            {
        
                cin >> x;
                ctask[i].push_back(x); //这些点相当于任务i的子任务
                in[x] ++;              //将这些点的入度+1
            }
        }
    
        for(int i = 1; i <= n; i ++)
        {
        
            if(in[i] == 0)topsort.push(i);//进行第一步：将所有入度为0的点入队
        }
    
        int cnt = 0;    //输出点的个数
        while(!topsort.empty())
        {
        
            x = topsort.front();    //队首
            topsort.pop();          //弹出队首
            for(int i = 0; i < ctask[x].size(); i ++)//遍历x的子任务
            {
        
                int temp = ctask[x][i];
                in[temp] --;                //将x所有子任务的入度-1
                if(in[temp] == 0)topsort.push(temp);//若入度-1后为0，则入队。
            }
            cnt ++;     //x成功输出，cnt+1
        }
        if(cnt == n)cout << 1;//若所有任务全部输出，工程合理
        else cout << 0;     //有任务无法进行，工程不合理
    
        return 0;
    }