问题陈述的重要性
不清楚正在计算什么。
- 起始节点集是所有至少有一个出边的节点，还是有特定的起始节点标准？
- 结束节点集是所有出边为零的节点集，还是任何有至少一个入边的节点都可能成为结束节点？
定义问题，以消除歧义。
估算
当设计用于随机构建的有向图并且图在其构造中非常统计偏斜或系统化时，估算可能会失误数个数量级。这是所有估算过程的典型情况，但在图形中尤为明显，因为它们具有指数级的复杂度潜力。
两个优化点
对于大多数处理器架构而言，std::bitset模型比bool值慢，因为测试特定位偏移处的位的指令集机制。当内存占用量而不是速度是关键因素时，位集更有用。
消除情况或通过推导来减少是很重要的。例如，如果有节点只有一个出边，可以计算没有它的路径数，并将其添加到子图中路径数和从指向它的节点的路径数中。
利用集群
可以通过按起始节点分发来在集群上执行该问题。有些问题仅需要超级计算。如果您有1,000,000个起始节点和10个处理器，则可以将每个处理器上放置100,000个起始节点案例。应在分发案例之前完成上述情况的消除和减少。
典型的深度优先递归及其优化方法
这是一个小程序，提供了从任何节点到任何节点的基本深度优先无环遍历，可以进行修改、放入循环或分布。如果已知最大数据集大小，则可以使用带有大小作为一个参数的模板将列表放入静态本地数组中，从而减少迭代和索引时间。
#include <iostream>
#include <list>
class DirectedGraph {
private:
int miNodes;
std::list<int> * mnpEdges;
bool * mpVisitedFlags;
private:
void initAlreadyVisited() {
for (int i = 0; i < miNodes; ++ i)
mpVisitedFlags[i] = false;
}
void recurse(int iCurrent, int iDestination,
int path[], int index,
std::list<std::list<int> *> * pnai) {
mpVisitedFlags[iCurrent] = true;
path[index ++] = iCurrent;
if (iCurrent == iDestination) {
auto pni = new std::list<int>;
for (int i = 0; i < index; ++ i)
pni->push_back(path[i]);
pnai->push_back(pni);
} else {
auto it = mnpEdges[iCurrent].begin();
auto itBeyond = mnpEdges[iCurrent].end();
while (it != itBeyond) {
if (! mpVisitedFlags[* it])
recurse(* it, iDestination,
path, index, pnai);
++ it;
}
}
-- index;
mpVisitedFlags[iCurrent] = false;
}
public:
DirectedGraph(int iNodes) {
miNodes = iNodes;
mnpEdges = new std::list<int>[iNodes];
mpVisitedFlags = new bool[iNodes];
}
~DirectedGraph() {
delete mpVisitedFlags;
}
void addEdge(int u, int v) {
mnpEdges[u].push_back(v);
}
std::list<std::list<int> *> * findPaths(int iStart,
int iDestination) {
initAlreadyVisited();
auto path = new int[miNodes];
auto pnpi = new std::list<std::list<int> *>();
recurse(iStart, iDestination, path, 0, pnpi);
delete path;
return pnpi;
}
};
int main() {
DirectedGraph dg(5);
dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(0, 3);
dg.addEdge(1, 3);
dg.addEdge(1, 4);
dg.addEdge(2, 0);
dg.addEdge(2, 1);
dg.addEdge(4, 1);
dg.addEdge(4, 3);
int startingNode = 0;
int destinationNode = 1;
auto pnai = dg.findPaths(startingNode, destinationNode);
std::cout
<< "Unique paths from "
<< startingNode
<< " to "
<< destinationNode
<< std::endl
<< std::endl;
bool bFirst;
std::list<int> * pi;
auto it = pnai->begin();
auto itBeyond = pnai->end();
std::list<int>::iterator itInner;
std::list<int>::iterator itInnerBeyond;
while (it != itBeyond) {
bFirst = true;
pi = * it ++;
itInner = pi->begin();
itInnerBeyond = pi->end();
while (itInner != itInnerBeyond) {
if (bFirst)
bFirst = false;
else
std::cout << ' ';
std::cout << (* itInner ++);
}
std::cout << std::endl;
delete pi;
}
delete pnai;
return 0;
}
