무 방향성 및 비가 중 그래프에서 두 노드 간의 거리 찾기

Question

그래프에서 s에서 t까지의 거리를 찾고 싶습니다. 어떻게하면 거리를 찾거나 좋은 알고리즘을 사용하여 bfs를 바꿀 수 있습니까? O(n). 정확히 그래프 당신은 두 노드 사이의 (짧은) 거리를 찾기 위해 BFS을 수정할 수 있습니다 비가 중 및

Answer 1

방향성 것이 중요합니다.

두 가지 중요한 점은이 알고리즘을 사용하기 전에 참고 :

• 가장자리 그래프의 것은 체중이 중 0 또는 1.
• 그래프는 무향입니다. 주의 할

또 다른 중요한 것은 : 당신은 당신이 각 노드를 방문 할 때 최적의 거리 상태를 확인해야하기 때문에

• 노드를 표시하는 부울 배열이 필요하지 않습니다.
• Deque은 노드를 저장하는 데 사용됩니다. 에지의 중량 1 경우
• 후이를 후방으로 푸시하고 전면에 0 경우.

여기

[I] 쌍의 형태로 존재하는 인접리스트는 에지하여 예이다 구현 에지 [V] [V] [i]는 좁은 방 것 v가 연결된 노드를 포함하고 edges [v] [i] .second은 v와 edges [v] [i] .first 사이의 거리를 포함합니다.

Q는 양단 큐입니다. 거리는 배열입니다. distance [v]에는 시작 노드에서 v 노드까지의 거리가 포함됩니다. 초기에 소스 노드에서 각 노드로 정의 된 거리는 무한대입니다.