依赖链问题的解决方案
几个月前,看到这样一道题:有若干个任务,都是以数字来表示任务ID,任务之间有依赖关系,比如:1 <- 2,表示任务2依赖于任务1,即,必须先完成任务1,才能完成任务2.那么现在给定多个这样的任务依赖关系,请设计并实现算法,其输出是一个任务序列,使得所有任务都可以被依次完成(即满足所有依赖关系)。 而几个月后的前不久,工作中又遇到这样一个问题,有若干个library,互相之间有依赖关系,请设计并实现一个算法,以输出一个library的序列,使得它们可以被按此序列顺利加载。 所以你看,其实这2个问题是同一个问题。那么怎么做呢?其实并不难,但其中有一个很关键的点。只要想透了这个点,一切就迎刃而解了。这个点,一句话说破了也很简单,如果不说破,可能也会困扰不少人。一句话,每一次都找出所有的无依赖任务。这就很容易理解了: 维护若干个依赖链,第一次,先找出所有的无依赖任务,然后将这些任务从依赖链中删除并添加到结果列表; 然后再找出所有的无依赖任务,再将它们从依赖链中删除并添加到结果列表; 如此循环往复,直到以下2种情况的任意一种发生为止: 1. 正常情况:所有的依赖链为空,即所有任务都被移到了结果列表; 2. 异常情况:仍有若干条依赖链不为空,但已经找不出无依赖任务了。这是为什么呢?聪明的读者想一想吧,不解释了。 最后,实现代码如下(115行的C++代码搞定,其实还能更短一点):
#include <vector> #include <set> #include <iostream> using namespace std; // The original dependency sequences. const vector<vector<int>> dependencyVec = { {1,2 },{3,4,5},{2,6},3 } }; // A copy of dependencyVec,but it will be changed during calculation vector<vector<int>> calcVec = dependencyVec; // This function is just print the dependency sequencies in run time for debug purpose. void printCalcVec() { cout << "caclVec is as below: " << endl; for (auto vec : calcVec) { for (int i : vec) { cout << i << ","; } cout << endl; } cout << "----------------" << endl; } set<int> collectNoDependencyItems() { set<int> noDependItems = {}; // Store the headers of each dependency sequence. set<int> headers = {}; for (auto vec : calcVec) { if (vec.size() > 0) headers.insert(vec[0]); } for (int h : headers) { bool noDepend = true; for (auto vec : calcVec) { for (unsigned int count = 1; count < vec.size(); ++count) { if (h == vec[count]) { noDepend = false; break; } } if (!noDepend) break; } if (noDepend) noDependItems.insert(h); } cout << "No Dependencies: "; for (int t : noDependItems) { cout << t << ","; } cout << endl << "----------------" << endl; return noDependItems; } void generateOrderList() { // This is the final order list. vector<int> finalList{}; // Check if calcVec is empty. If yes,Done. while (calcVec.size() > 0) { printCalcVec(); // Figure out no dependency items and push them to finalList set<int> noDependItems = collectNoDependencyItems(); if (noDependItems.size() == 0) { cout << "NoDependItems = 0" << endl; // There is no item which is no dependent. This means there is loop dependency. break; } // Push no dependent items to finalList for (unsigned int i : noDependItems) { finalList.push_back(i); } // Remove the headers of each dependency sequence which are no dependent items for (int i = 0; i < calcVec.size(); ) { if (noDependItems.find(calcVec[i][0]) != noDependItems.end()) { calcVec[i].erase(calcVec[i].begin()); } if (calcVec[i].size() == 0) { calcVec.erase(calcVec.begin() + i); } else { ++i; } } } cout << "FinalList: "; for (int i : finalList) { cout << i << ","; } cout << endl; } int main() { generateOrderList(); return 0; }
caclVec is as below: 1,2,3,5,6,---------------- No Dependencies: 1,---------------- caclVec is as below: 2,---------------- No Dependencies: 2,---------------- caclVec is as below: 3,---------------- No Dependencies: 3,---------------- caclVec is as below: 4,---------------- No Dependencies: 4,---------------- caclVec is as below: 5,---------------- No Dependencies: 5,---------------- FinalList: 1,Press any key to continue . . . (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |