algorithm - 查找路径是否存在于单向有向图中的最佳方法

Question

我有一个包含大量节点的图，其中有一个起始节点(所有边都向外)和一个结束节点(所有边都朝向它)。它是一个单向且未加权的图。如何优化此类图中的搜索以找出两个节点之间是否存在路径？我知道 BFS 提供了一个解决方案。有没有办法优化搜索(比如添加一些额外的信息)，因为我将在图表上进行频繁搜索？

编辑:要添加有关图的更多信息，图有一个起始节点和多个出边和一个结束节点和多个入边。在这两者之间，连接着数百万个节点。它是一个未加权的 DAG。并且不涉及启发式方法。只需检查 isConnected(node a,node b)。

Answer 1

考虑到你的图表是非循环的，这里有一种方法:-

1. Do DFS on graph start with source vertex(only outgoiong edges)

2. For each edge (u,v) in the graph connected[u][v] = true

3. Try to store the previous node in DFS stack in a array & for each vertex v visited check the previous nodes in the stack and do connected[u][v] = true where u is a previous node.

如果图不是非循环的，则首先使用 Kosaraju 或 Tarjan 计算 SCC，然后将图简化为非循环的，并对 SCC 中的每一对执行 connected[u][v] = true

修改后的 DFS 例程的伪代码:-

bool connected[n][n] = {false};   
bool visited[n] = {false};   
int stack[n]; 

for each source vertex v do :   
     DFS(v,stack,0);


void DFS(int u,int stack[n],int depth) {


    if(!visited[v]) {

          visited[v] = true;

          for(int i=0;i<depth;i++) {

               connected[stack[i]][v] = true; 
          }

          stack[depth] = u;

          for each edge(u,v) {
             connected[u][v] = true;
             DFS(v,stack,depth+1);
          }
    }
} 

空间复杂度:O(V^2)

时间复杂度:O(V^2)

注意:-

如果您的查询数量较少，则尝试对它们单独使用 DFS 并缓存结果，因为这会比那样更耗时。