问题陈述的重要性
目前尚不清楚计算的是什么。
- 起始节点是否设置了至少有一个出边的所有节点,或者是否有特定的起始节点标准?
- 结束节点是否设置了所有出边为零的节点的集合,或者任何至少有一条入边的节点都可以成为可能的结束节点?
定义你的问题,这样就不会有歧义。
估计
当为随机构造的有向图设计时,估计值可能会相差几个数量级,并且该图在其构造中在统计上非常偏斜或系统化。这是所有估计过程的典型特征,但在图形中尤其明显,因为它们具有指数模式复杂性潜力。
两个优化点
对于大多数处理器体系结构,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;
}