[java] 최단 경로를 찾을 때 너비 우선 검색은 어떻게 작동합니까?
나는 약간의 연구를 해왔고이 알고리즘의 작은 부분이 빠져있는 것 같습니다. 너비 우선 검색의 작동 방식을 이해하지만 각 개별 노드가 어디로 갈 수 있는지 알려주는 것이 아니라 정확히 특정 경로로 이동하는 방법을 이해하지 못합니다. 혼란을 설명하는 가장 쉬운 방법은 예제를 제공하는 것입니다.
예를 들어 다음과 같은 그래프가 있다고 가정 해 봅시다.
그리고 내 목표는 A에서 E로 얻는 것입니다 (모든 가장자리는 가중되지 않습니다).
나는 A에서 시작합니다. 왜냐하면 그것이 나의 기원이기 때문입니다. A를 대기열에 넣은 다음 즉시 A를 대기열에서 빼고 탐색합니다. A가 B와 D에 연결되어 있기 때문에 B와 D가 생성됩니다. 따라서 B와 D를 모두 대기열에 넣습니다.
B를 대기열에서 빼서 탐색 한 후 A (이미 탐색) 및 C로 연결되는 것을 발견했습니다. 그래서 C를 대기열에 넣습니다. 그런 다음 D를 대기열에서 빼고 E로 연결됩니다. 그런 다음 C를 대기열에서 빼고 목표 인 E로 연결되는 것도 발견했습니다.
나는 가장 빠른 경로가 A-> D-> E라는 것을 논리적으로 알고 있지만, 너비 우선 탐색이 정확히 어떻게 도움이되는지 잘 모르겠습니다. 경로를 어떻게 기록하여 마무리 할 때 결과를 분석하고 볼 수 있는지 최단 경로는 A-> D-> E입니까?
또한 실제로 트리를 사용하고 있지 않으므로 “부모”노드가없고 자식 만 있습니다.
답변
엄밀히 말하면 BFS (Breadth-First Search) 자체만으로는 BFS가 최단 경로를 찾지 않기 때문에 최단 경로를 찾을 수 없습니다. BFS는 그래프를 검색하기위한 전략을 설명하지만 반드시 특히 무엇이든.
Dijkstra의 알고리즘 은 BFS를 조정하여 단일 소스 최단 경로를 찾을 수 있습니다.
원점에서 노드까지의 최단 경로를 검색하려면 그래프의 각 노드에 대해 현재 최단 거리와 최단 경로에있는 선행 노드의 두 항목을 유지해야합니다. 처음에는 모든 거리가 무한대로 설정되고 모든 선행 작업은 비어 있습니다. 이 예에서는 A의 거리를 0으로 설정 한 다음 BFS를 진행합니다. 각 단계에서 하위 항목의 거리를 개선 할 수 있는지 확인합니다. 즉, 원점에서 선행 작업까지의 거리에 탐색중인 모서리의 길이에 해당 노드의 현재 최고 거리보다 작습니다. 거리를 개선 할 수있는 경우 새 최단 경로를 설정하고 해당 경로를 획득 한 선행 작업을 기억하십시오. BFS 대기열이 비어 있으면 노드 (예 : E)를 선택하고 이전 노드를 다시 원래 위치로 이동합니다.
약간 혼란스러워 보이는 경우, 위키 백과에는 주제에 대한 의사 코드 섹션이 있습니다.
답변
위에서 지적한 것처럼 BFS는 다음과 같은 경우에만 그래프에서 최단 경로를 찾는 데만 사용할 수 있습니다 .
-
루프가 없습니다
-
모든 모서리의 무게는 동일하거나 무게가 없습니다.
가장 짧은 경로를 찾으려면 소스에서 시작하여 광범위한 첫 번째 검색을 수행하고 대상 노드를 찾을 때 중지하면됩니다. 추가로해야 할 일은 방문한 모든 노드에 대해 이전 노드를 저장할 배열 이전 [n]을 갖는 것입니다. 이전 소스는 null 일 수 있습니다.
경로를 인쇄하려면 대상에 도달하고 노드를 인쇄 할 때까지 소스에서 이전 [] 배열을 반복합니다. DFS를 사용하여 유사한 조건에서 그래프에서 최단 경로를 찾을 수도 있습니다.
그러나 가중치가 적용된 모서리와 루프를 포함하는 그래프가 더 복잡한 경우 더 복잡한 버전의 BFS 즉 Dijkstra 알고리즘이 필요합니다.
답변
에서 여기 자습서
“그래프의 모든 모서리가 가중되지 않은 경우 (또는 동일한 가중치) 노드를 처음 방문 할 때 소스 노드에서 해당 노드까지의 최단 경로라는 매우 유용한 특성이 있습니다.”
답변
BFS를 사용하여
최단 거리
를 찾는 데 사용되는
그래프 질문을 궁극적으로 3 일 동안 낭비했습니다.
경험을 나누고 싶다.
When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges
#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)
#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path
#3
It does not matter what queue you use
deque/queue(c++) or
your own queue implementation (in c language)
A circular queue is unnecessary
#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.
#5
Wikipedia BFS will work, and is sufficient.
https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode위의 모든 대안을 시도하면서 3 일을 잃어 버렸습니다. 위에서 다시 확인하고 다시 확인하는
것은 문제가 아닙니다.
(위의 5 가지 문제가 발견되지 않으면 다른 문제를 찾는 데 시간을 투자하십시오).
아래 의견에서 더 많은 설명 :
A
/ \
B C
/\ /\
D E F G위의 그래프
그래프가 아래로 내려 간다고 가정하면
A의 경우 인접 항목은 B & C이고
B의 경우 인접 항목은 D & E
이고 C의 경우 인접 요소는 F & G입니다
예를 들어 시작 노드는 A입니다.
-
A, B, C에 도달하면 A에서 B & C까지의 최단 거리는 1입니다.
-
B를 통해 D 또는 E에 도달하면 A 및 D까지의 최단 거리는 2 (A-> B-> D)입니다.
마찬가지로 A-> E는 2 (A-> B-> E)입니다.
또한 A-> F & A-> G는 2
이제 노드 사이의 1 거리 대신 6이면 대답에 6
예제를 곱하십시오.
각 거리가 1이면 A-> E는 2입니다 (A-> B-> E = 1 + 1 )
각각 사이의 거리가 6이면 A-> E는 12 (A-> B-> E = 6 + 6)입니다.
예, bfs는 경로를 취할 수
있지만 모든 경로를 계산합니다
A에서 Z로 가야하는 경우 모든 경로를 A에서 중간 I로 이동하고 많은 경로가 있으므로 I까지 가장 짧은 경로를 제외한 모든 경로를 버리고 다음 노드 J로 가장 짧은 경로를
다시 계속합니다. I에서 J까지의 다중 경로가 있으며, 우리는 가장 짧은 한 가지
예를
가정합니다.
A-> 거리 5
(STEP)가 있다고 가정합니다. I-> J 거리가 7 & 8 인 다중 경로가 있다고 가정합니다.
우리는 A-> J를 5 (A-> I shortest) + 8 (지금 가장 짧음) = 13으로 취합니다
.A-> J는 이제 13
입니다 .J-> K에 대해 위의 (STEP)를 반복합니다. Z로
이 부분을 2 ~ 3 회 읽고 종이에 그려라. 내가 말한 것을 확실히 얻을 것이다.
답변
acheron55 답변을 기반으로 가능한 구현을 여기에 게시했습니다 .
다음은 여름에 대한 간략한 설명입니다.
목표에 도달 한 경로를 추적하기 만하면됩니다. 이를 수행하는 간단한 방법 Queue은 노드 자체가 아닌 노드에 도달하는 데 사용되는 전체 경로를 사용하는 것입니다.
이렇게하면 대상에 도달했을 때 큐에 도달하는 데 사용 된 경로가 큐에 유지됩니다.
이것은 노드가 둘 이상의 부모를 가질 수있는 순환 그래프에도 적용됩니다.
답변
일정 시간 동안 활동이 없으면이 실을 방문하지만, 완전한 답을 볼 수 없다면, 여기에 2 센트가 있습니다.
너비 우선 검색은 항상 가중치가없는 그래프에서 가장 짧은 경로를 찾습니다. 그래프는 주기적 또는 비 주기적 일 수있다.
의사 코드는 아래를 참조하십시오. 이 의사 코드는 큐를 사용하여 BFS를 구현한다고 가정합니다. 또한 정점을 방문한 것으로 표시 할 수 있고 각 정점이 거리 매개 변수를 저장하고 무한대로 초기화된다고 가정합니다.
mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
push the start vertex on the queue
while(queue is not empty)
dequeue one vertex (we’ll call it x) off of the queue
if the value of x is the value of the end vertex:
return the distance value of x
otherwise, if x is not marked as visited:
mark it as visited
for all of the unmarked children of x:
set their distance values to be the distance of x + 1
enqueue them to the queue
if here: there is no path connecting the vertices이 방법은 가중치 그래프에는 적용되지 않습니다. Dijkstra 알고리즘을 참조하십시오.
답변
다음 솔루션은 모든 테스트 사례에 적용됩니다.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
for (int i = 0; i < testCases; i++)
{
int totalNodes = sc.nextInt();
int totalEdges = sc.nextInt();
Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();
for (int j = 0; j < totalEdges; j++)
{
int src = sc.nextInt();
int dest = sc.nextInt();
if (adjacencyList.get(src) == null)
{
List<Integer> neighbours = new ArrayList<Integer>();
neighbours.add(dest);
adjacencyList.put(src, neighbours);
} else
{
List<Integer> neighbours = adjacencyList.get(src);
neighbours.add(dest);
adjacencyList.put(src, neighbours);
}
if (adjacencyList.get(dest) == null)
{
List<Integer> neighbours = new ArrayList<Integer>();
neighbours.add(src);
adjacencyList.put(dest, neighbours);
} else
{
List<Integer> neighbours = adjacencyList.get(dest);
neighbours.add(src);
adjacencyList.put(dest, neighbours);
}
}
int start = sc.nextInt();
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
int[] costs = new int[totalNodes + 1];
Arrays.fill(costs, 0);
costs[start] = 0;
Map<String, Integer> visited = new HashMap<String, Integer>();
while (!queue.isEmpty())
{
int node = queue.remove();
if(visited.get(node +"") != null)
{
continue;
}
visited.put(node + "", 1);
int nodeCost = costs[node];
List<Integer> children = adjacencyList.get(node);
if (children != null)
{
for (Integer child : children)
{
int total = nodeCost + 6;
String key = child + "";
if (visited.get(key) == null)
{
queue.add(child);
if (costs[child] == 0)
{
costs[child] = total;
} else if (costs[child] > total)
{
costs[child] = total;
}
}
}
}
}
for (int k = 1; k <= totalNodes; k++)
{
if (k == start)
{
continue;
}
System.out.print(costs[k] == 0 ? -1 : costs[k]);
System.out.print(" ");
}
System.out.println();
}
}
}