Лучший способ найти, существует ли путь в однонаправленном ориентированном графе

Question

У меня есть график с огромным количеством узлов с одним стартовым узлом (все ребра - наружу) и одним конечным узлом (все кромки к нему). Это однонаправленный и невзвешенный график. Как оптимизировать поиск в этом виде графика, чтобы выяснить, существует ли путь между двумя узлами? Я знаю, что BFS предоставляет решение. Есть ли способ оптимизировать поиск (например, добавить дополнительную информацию), поскольку я буду делать частый поиск на графике?

EDIT: Чтобы добавить дополнительную информацию о графике, граф имеет один стартовый узел с несколькими внешними ребрами и одним конечным узлом с несколькими краями. Между ними соединяются миллионы узлов. Это невзвешенный DAG. И нет никаких эвристик. Просто проверьте isConnected (узел a, узел b).

Answer 1

Учитывая ваш граф ациклический здесь есть способ сделать это: -

1. Do ДФС на графике начинается с исходной вершиной (только outgoiong кромок)

2. Для каждого ребра (U , v) в графе, связанном [u] [v] = true

3. Попробуйте сохранить предыдущий узел в стеке DFS в массиве & для каждой проверенной вершины v проверить предыдущие узлы в stack и do connected [u] [v] = true, где u - предыдущий узел.

Если граф не является ациклическим, то сначала рассчитать SCC, используя Kosaraju или Тарьян, а затем уменьшить график ациклические и сделать подключен [и] [V] = верно для каждой пары в SCC

псевдокод для модифицированной подпрограммы 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); 
      } 
    } 
} 

Space Сложность: O(V^2)

Время Сложность : O(V^2)

Примечание: -

Если количество запросов меньше, то попробуйте использовать DFS для них индивидуально и кэшировать результаты, как это будет больше времени, чем это.