拓扑排序 + make + UVa10305(Ordering Tasks)

  拓扑排序在实践中应用广泛。先来看一个实例,开源软件常使用GNU make工具来管理项目的构建。这里的项目是由若干个对象构成的,Makefile文件则描述了这些对象的构建规则,这些规则具体来说是一系列对象间的依赖关系:若对象A依赖于对象B,则说明对象B必须先于对象A构建,否则构建将无法进行。make的任务就是合理安排各个对象构建的先后顺序,使得过程能顺利地完成。

  作为例子,一个Makefile文件的内容如下:

target: foo.o bar.o

foo.o: foo.c foo.h
bar.o: bar.c bar.h

  为了解决这一问题,我们先对问题进行数学转化。使用DAG来表示每个对象间的依赖关系,图的每一个顶点表示一个对象、有向线段表示起点必须先于终点被构建,即终点依赖起点。

拓扑排序 + make + UVa10305(Ordering Tasks)

  如何合理布局各个对象的构建顺序,使得构建过程可以顺利地进行下去呢?直观的想法是,选择不被其它对象依赖的作为第1个对象;再考虑第2个对象,它除了已选的第1个对象外,不应该被其它对象依赖;第n个对象,它除了前面已选的第1~n-1对象外,不能再被其它对象依赖。按照这个规则依次选出对象,即可保证构建过程顺利结束。

拓扑排序 + make + UVa10305(Ordering Tasks)

  在图论中,这种类似的策略称为拓补排序算法。拓扑排序是所有顶点的线性排序,拓扑排序中没有一个节点指向它前面的节点,形式化地描述:对于图中的任意两个结点u和v,若存在一条有向边从u指向v,则在拓扑排序中u一定出现在v前面。

  有向图拓扑排序存在的充分必要条件是图为DAG(有向无环图),这个结论用于判断问题是否有解,也用于判断一个有向图是否有环。

 

  算法的求解过程如下:首先统计所有顶点的入度。然后:

a. 寻找所有入度为0的顶点,加入排序结果中并将其从图中移除,同时将其指向的所有顶点(邻接顶点)的入度减一。
b. 重复a,直到所有顶点都从图中移除。


  对于任意一个可能带环的有向图,在寻找入度为0的顶点时,如果找不到,说明图的拓扑排序是不存在的,即问题无解。

 

  上述的“移除”是逻辑层面的概念,具体实现中,我们不需要真正地将顶点从图中移除,因为某次a.中找到的入度为0的顶点只可能出现在上一次a.中入度被减一的顶点中。当a找到入度为0的顶点时,就会把它的邻接顶点的入度减一,这时便可以顺便统计入度减为0的顶点,下次a直接从这些入度为0的顶点开始,无需再从整个图中寻找入度为0的顶点。

 

  最后通过一道UVa的题目来说明算法的具体实现:

UVa10305(Ordering Tasks)

题目大意

  给出一堆任务,其中一个任务必须在它依赖的所有任务都完成后才能执行。已知任务之间的关系,求可能的执行顺序。

分析

  思路与make的例子一致。这里使用vector存储邻接表,数组deg_in维护每个顶点的入度,队列que维护每趟中入度被减为0的顶点。

参考代码

#include <iostream>
#include <queue>
#define N 100+2

using namespace std;

static vector<int> con[N];
static int deg_in[N];

int main(void) {
    ios::sync_with_stdio(false);
    
    int n,m;
    while((cin >> n >> m) && n) {
        for(int i=1;i<=n;++i) {
            con[i].clear();
            deg_in[i] = 0;
        }
        
        for(int i=0; i<m; ++i) {
            int a,j;
            cin >> a >> j;
            con[a].push_back(j);
            ++deg_in[j];
        }
        
        //
        // 找出第一个度为0的顶点
        //
        queue<int> que;
        vector<int> ans;
        for(int i=1; i<=n; ++i) {
            if (!deg_in[i]) {
                que.push(i);
            }
        }
        
        //
        // 求排序中其它n-1个顶点
        //
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            
            ans.push_back(u);
            
            for(size_t i=0; i<con[u].size(); ++i) {
                int t = con[u][i];
                if (--deg_in[t] == 0) {
                    que.push(t);
                }
            }
        }
        
        for(size_t i=0; i<ans.size(); ++i) {
            cout << ans[i] << (i==ans.size()-1 ? "" : " ");
        }
        cout << endl;
    }
    
    return 0;
}

 

上一篇:Python - pydantic(3)错误处理


下一篇:图片上传