ShortestPath with BFS (BreadthFirstSearch)

Question

그래프의 두 꼭지점 사이의 최단 경로를 반환하려고합니다. breadthFirstSearch를 찾기 위해 작성된 코드가 있지만 최단 경로를 반환하도록 수정하는 방법을 모르겠습니다. 아래는 내 breadthFirstSearch 함수입니다.

private void breadthFirstSearch(T start,T end){ 

    Queue<T> queue = new LinkedList<>(); 
    Set<T> visited = new HashSet<>(); 
    visited.add(start); 
    queue.add(start); 
    while(!queue.isEmpty()){ 
     T v = queue.poll(); 
      for(int i =0;i<this.keyToVertex.get(v).successors.size();i++){     if(visited.contains(this.keyToVertex.get(v).successors.get(i).key)){ 
       continue; 
      } 
      visited.add(this.keyToVertex.get(v).successors.get(i).key); 
      queue.add(this.keyToVertex.get(v).successors.get(i).key); 
     } 

    }  

} 

어떻게 최단 경로를 반환하도록 수정할 수 있습니까?

Answer 1

확인할 값뿐만 아니라 해당 값으로 이어지는 경로 이상의 내용을 Queue에서 추적해야합니다. 따라서 유형은 Queue<T> 이상이어야하지만 예를 들어 Queue<LinkedList<T>>이어야합니다.

대기열의 첫 번째 값은 싱글 톤 목록이 start이고 start이 아니어야합니다.

대기열의 값을 처리 할 때 방문중인 정점은 대기열 항목의 마지막 요소가되며 항목을 대기열에 추가하면 현재 항목의 복제본이됩니다. 다음 이웃이 추가되었습니다. 이 같은

뭔가 : 덕분에 많은 도움이

Queue<LinkedList<T>> queue = new LinkedList<>(); 
queue.add(new LinkedList<>(Collections.singleton(start))); 

while (!queue.isEmpty()) { 
    LinkedList<T> path = queue.poll(); 
    T v = path.getLast(); 
    if (v.equals(end)) { 
     return path; 
    } 

    for (int i = 0; i < this.keyToVertex.get(v).successors.size(); i++) { 
     T v2 = this.keyToVertex.get(v).successors.get(i).key; 
     if (visited.contains(v2)) { 
      continue; 
     } 

     LinkedList<T> path2 = new LinkedList<>(path); 
     path2.add(v2); 
     queue.add(path2); 
     visited.add(v2); 
    } 
}