Найти расстояние между двумя узлами в неориентированном и невзвешенном графике

Question

Я хочу найти расстояние от s до t на графике. как я могу изменить bfs, чтобы найти расстояние или использовать другой алгоритм, который имеет хорошие O(n). именно это важно, чтобы граф невзвешенный и неориентированный

Answer 1

Вы можете изменить BFS найти (короткое) расстояния между двумя узлами.

Две важных моментов отметить перед использованием этого алгоритма:

• В Ребре из Graph имеет вес либо или .
• График неориентированный.

Еще одна важная вещь, чтобы отметить:

• Вам не нужно Boolean массив пометить узел, потому что вы должны проверить условие оптимального расстояния при посещении каждого узла.
• A Deque используется для хранения узла.
• если вес ребра является 1, то он проталкивается к задней части, и если это 0, к фронту.

Реализация

Здесь края [v] [я] является список смежности, который существует в виде пар, т.е. ребра [v] [я] .first будет содержат узел, к которому подключен v, и edge [v] [i] .second будет содержать расстояние между v и ребрами [v] [i] .first.

Q является двухсторонняя очередь. Расстояние - это массив, где Расстояние [v] будет содержать расстояние от начального узла до узла v. Первоначально расстояние, определенное от исходного узла до каждого узла, равно бесконечности.

void bfs (int start) 
{  
     deque <int > Q;  //Double-ended queue 
     Q.push_back(start); 
     distance[ start ] = 0;  
     while(!Q.empty()) 
      { 
      int v = Q.front(); 
      Q.pop_front(); 
      for(int i = 0 ; i < edges[v].size(); i++) 
      { 


      /* if distance of neighbour of v from start node is greater 
      than sum of distance of v from start node and edge weight between v and its neighbour 
      (distance between v and its neighbour of v) ,then change it */ 


      if(distance[ edges[ v ][ i ].first ] > distance[ v ] + edges[ v ][ i ].second) 
      { 

       distance[ edges[ v ][ i ].first ] = distance[ v ] + edges[ v ][ i ].second; 

      /*if edge weight between v and its neighbour is 0 then push it to front of 
      double ended queue else push it to back*/ 

       if(edges[ v ][ i ].second == 0) 
       { 
        Q.push_front(edges[ v ][ i ].first); 
       } 
       else 
       { 
         Q.push_back(edges[ v ][ i ].first); 

       } 
      } 
      } 
     } 
}