BFS를 사용하여 두 노드 사이의 거리를 찾는 방법은 무엇입니까?

Question

위 코드의 의사 코드를 사용하여 C++에서 BFS 코드를 작성했습니다. 이 함수는 두 개의 매개 변수 s, t를 사용합니다. s가 소스 노드이고 t가 대상인 경우 대상이 fount 인 경우 검색은 대상 자체를 반환하거나 그렇지 않으면 -1을 반환합니다. 예를 들어,

너비 우선 탐색은 그래프 이론에 많은 문제를 해결하는 데 사용할 수 있습니다 : 나는 위키 피 디아에서이 글을 읽을

#include <iostream> 
#include <deque> 
#include <vector> 

using namespace std; 

struct vertex{ 
vector<int> edges; 
bool visited; 
}; 

int dist = 0; 

int BFS(vertex Graph[],int v,int target){ 
deque<int> Q; 
Q.push_front(v); 
Graph[v].visited = true; 
    while(!Q.empty()){ 
     int t = Q.back(); 
     Q.pop_back(); 
      if(t == target){ 
       return t; 
      } 
      for(unsigned int i = 0;i < Graph[t].edges.size();i++){ 
       int u = Graph[t].edges[i]; 
       if(!Graph[u].visited){ 
        Graph[u].visited = true; 
        Q.push_front(u); 
       } 
      } 
    } 
    return -1; 
} 

int main(){ 
int n; 
cin >> n; 
vertex Graph[n]; 
int k; 
cin >> k; 
for(int i = 0;i < k; i++){ 
    int a,b; 
    cin >> a >> b; 
    a--; 
    b--; 
    Graph[a].edges.push_back(b); 
    Graph[b].edges.push_back(a); 
} 

for(int i = 0;i < n; i++){ 
    Graph[i].visited = false; 
} 

int s,t; 
cin >> s >> t; 

cout << BFS(Graph,s,t); 

    } 

:
이 사이의 최단 경로를 찾는 여기 내 코드입니다 두 개의 노드 u와 v (경로 길이가 에지의> 번호로 측정 됨)

경로가없는 경우 가장 짧은 경로를 s에서 t로 되돌리기 위해 함수 BFS를 어떻게 변경합니까? 에스?

Answer 1

새 노드를 생성 할 때 노드를 생성 한 상위 노드의 ID를 추적하십시오. 그런 다음 목표에 도달하면 시작 상태에 도달 할 때까지 부모를 뒤로 추적합니다. 예를 들어 시작을 자신의 부모로 표시 할 수 있습니다. 즉, 시작 상태임을 나타냅니다. 또는 부모가 없다고 미리 정의 된 값 (-1)을 사용하십시오.

그래서 코드에 방문한 상태를 표시하는 대신 상위 ID가 있어야합니다. 부모 ID는 처음에 -1로 설정 한 다음 변경할 때 업데이트 될 수 있습니다. 상위 ID는 상위 그래프 구조의 위치 일 수 있습니다.

Answer 2

너비 우선 탐색은 시작점으로부터 거리 d에있는 모든 노드를 방문하여 거리 d+1에있는 노드를 방문하기 전에 정의됩니다. 따라서 너비 우선 순위로 그래프를 탐색 할 때 처음으로 대상 노드를 만날 때 가능한 가장 짧은 경로로 그곳에 도달했습니다.

Nathan S. ' 대답은 정확하지만이 대답이 왜이 작품이 더 많은 직관을 제공하기를 바랍니다. Paul Dinh의 의견도 정확합니다. 당신은 Nathan의 대답을 수정하여 실제 경로 대신 거리를 추적 할 수 있습니다.