在电信网络中，节点和连接的链路可以被建模为一个具有顶点和边的图。一个经常出现的问题是发现任意一对通信端节点之间所有可能的路径组合（不包含循环）。这不仅仅是寻找一对节点之间的最短路径，对于这个问题，Dijkstra算法可以很容易地使用。
此外，算法应该能够处理具有单向（单向）边的图和假定边是双向的图。
源代码和类似的C++算法实现可以在找到。
美国国家标准与技术研究院（NIST）在线算法和数据结构词典将这个问题描述为“所有简单路径”，并推荐使用深度优先搜索来找到任意一对节点之间的所有非循环路径。
使用以下Link类来识别个别链路的端节点：
class Link {
public:
Link(int source, int target) {
sourceNode = source;
targetNode = target;
}
void GetSourceTargetNodes(int& source, int& target) {
source = sourceNode;
target = targetNode;
}
protected:
int sourceNode;
int targetNode;
};
这里有一个Network类，用于存储拓扑信息并执行基本操作，如添加新链路、检查链路的存在以及设置网络的双向状态：
class Network {
private:
std::map, Link*> link_map;
bool bi_direction;
public:
Network();
~Network();
void Reset();
void SetBiDirection(bool bi);
void AddLink(Link* l);
void AddLink(int s, int d);
bool LinkExists(int sourceID, int targetID);
bool BiDirectional();
std::vector GetAdjNodeIDs(int n);
};
使用标准STL map来存储所有网络链路：键值由std::pair唯一标识每个链路元素，并映射到Link对象的指针：
std::map, Link*> link_map;
与序列容器（如std::vector）不同，像std::map这样的关联容器在通过键访问其元素时特别有效。也许对于非常大的网络，某种哈希表可能会进一步提高效率，但目前坚持使用std::map。
如果双向状态值设置为true，则端节点[a,b]之间的链路将被视为与链路端节点[b,a]相同。因此，在双向模式下添加新链路时，如果已经通过指定端节点[2,5]创建并添加了链路，那么尝试添加端节点[5,2]之间的另一个链路将失败，因为它将被视为已经存在。对于有向（单向）图，即双向状态设置为false，添加端节点[5,2]之间的另一个链路将成功，因为它们被视为两个单独的链路。
从代码示例中可以看出，从起始节点开始，算法检查所有出链路，并通过扩展搜索树中出现的第一个子节点进行扩展，搜索越来越深，直到找到目标节点，或者直到遇到没有子节点的节点。然后搜索回溯，返回到它尚未完成探索的最近节点：
void DepthFirst(Network* network, std::vector& visited, int end) {
int back = visited.back();
std::vector adjNode = network->GetAdjNodeIDs(back);
// Examine adjacent nodes
for (std::vector::iterator node_it = adjNode.begin(); node_it != adjNode.end(); node_it++) {
int node = (*node_it);
if (ContainsNode(visited, node)) continue;
if (node == end) {
visited.push_back(*node_it);
int hops = (int) visited.size();
for (int i = 0; i < hops; i++) {
std::cout << visited[i] << " ";
}
std::cout << std::endl;
int n = (int) visited.size() - 1;
visited.erase(visited.begin() + n);
break;
}
// in breadth-first, recursion needs to come after visiting adjacent nodes
for (std::vector::iterator node_it = adjNode.begin(); node_it != adjNode.end(); node_it++) {
int node = (*node_it);
if (ContainsNode(visited, node) || node == end) continue;
visited.push_back(node);
DepthFirst(network, visited, end);
int n = (int) visited.size() - 1;
visited.erase(visited.begin() + n);
}
}
}
这是一个5节点有向图的图形表示。例如，节点[1,3]之间存在有向边，但节点[3,1]之间不存在，因此节点[1,3]对之间有一个单箭头：
在主程序循环中，网络被设置为具有有向边，即双向状态设置为false。通过调用Network对象的AddLink方法插入个别链路：
nw.SetBiDirection(false);
nw.AddLink(1, 2);
nw.AddLink(1, 3);
nw.AddLink(1, 4);
nw.AddLink(2, 1);
nw.AddLink(2, 4);
nw.AddLink(2, 3);
nw.AddLink(3, 5);
nw.AddLink(4, 5);
nw.AddLink(5, 3);
要找到节点[2,5]之间的所有可能路径组合，例如，只需指定起始和目标节点，并将它们输入DepthFirst方法：
int start = 2;
int target = 5;
std::vector visited;
visited.push_back(start);
DepthFirst(&nw, visited, target);
输出显示节点2和5之间的所有路径组合：
这是一个包含非定向（双向）链路的8节点网络的图形表示。对于双向链路，为了清晰起见，放弃了使用带箭头的链路，因为双向交通是允许的：
nw.SetBiDirection(true);
nw.AddLink(1, 2);
nw.AddLink(2, 1);
// Makes no difference
nw.AddLink(1, 4);
nw.AddLink(1, 7);
nw.AddLink(2, 4);
nw.AddLink(2, 3);
nw.AddLink(3, 5);
nw.AddLink(3, 8);
nw.AddLink(4, 5);
nw.AddLink(5, 6);
nw.AddLink(5, 7);
nw.AddLink(6, 8);
nw.AddLink(7, 8);