查找任意节点对之间的非循环路径

引言

这个问题我曾经在为电信网络设计和实现路由优化算法时遇到过。考虑到一个具有节点和互连链路的广域网可以被建模为一个具有顶点和边的图，一个经常出现的问题是发现任何一对通信端节点之间所有可能的路径组合（不包含循环）。请注意，这不仅仅是寻找一对节点之间的最短路径的问题，对于这个问题，可以使用 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< std::pair<int,int>, 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< int > GetAdjNodeIDs( int n );                 
};

标准 STL map 用于容纳所有网络链路：键值由 std::pair 组成，唯一标识每个链路元素，并映射到 Link 对象的指针

std::map< std::pair<int,int>, Link*> link_map;

与序列容器（例如 std::vector）不同，关联容器（例如 std::map）在通过其键访问其元素方面特别高效。也许对于非常大的网络，某种哈希表可能会带来效率的进一步提高，但目前我仍然坚持使用 std::map。

链路双向状态

如果双向状态值设置为 true，则端节点 [a,b] 之间的链路将被视为与链路的端节点为 [b,a] 相同。

因此，在双向模式下添加新链路时，如果已经通过指定端节点 [2,5] 创建并添加了一条链路，则尝试在端节点 [5,2] 之间添加另一条链路将失败，因为它将被视为已经存在。对于有向（单向）图，即双向状态设置为 false，在端节点 [5,2] 之间添加另一条链路将会成功，因为它们被视为两个独立的链路。

深度优先搜索算法

从代码示例中可以看出，从起始节点开始，该算法检查所有传出链路，并通过扩展出现的搜索树的第一个子节点进行推进，逐渐深入搜索，直到找到目标节点，或者直到遇到没有子节点的节点。然后搜索回溯，返回到它尚未完成探索的最新节点

// Algorithm to recursively search network for paths
void DepthFirst( Network* network, 
                 std::vector<int>& visited, 
                 int end )
{
    int back = visited.back();

    std::vector< int > adjNode = network->GetAdjNodeIDs( back );

    // Examine adjacent nodes
    for ( std::vector<int>::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<int>::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 );
    }       
}

示例 1：有向图

这是 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<int> visited;    
visited.push_back( start );
DepthFirst( &nw, visited, target );

给出以下输出，显示节点 2 和 5 之间的所有路径组合

示例 2：双向链路

这是包含仅非定向（双向）链路的 8 节点网络的图形表示。对于双向链路，为了清晰起见，我放弃了使用带有箭头的链路，因为两个方向的流量都是允许的

在创建仅具有双向链路的网络时，在创建使用 AddLink 方法的所需拓扑之前，双向状态设置为 true。如果已经在（例如）节点 1 到 2 之间添加了链路，则添加从节点 2 到 1 的链路不会创建额外的链路，因为它将被视为已经存在

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 );

给出以下输出，显示该 8 节点网络（仅包含双向链路）中节点 2 和 5 之间的所有可能路径组合