그래프 순회
그래프 순회는 우물에서 정확히 한 번 모든 정점과 가장자리를 방문하는 것을 의미합니다. 정의 된 순서. 특정 그래프 알고리즘을 사용하는 동안 그래프의 각 정점을 정확히 한 번 방문했는지 확인해야합니다. 정점을 방문하는 순서는 중요하며 해결하려는 알고리즘이나 질문에 따라 달라질 수 있습니다.
순회 중에 방문한 정점을 추적하는 것이 중요합니다. 정점을 추적하는 가장 일반적인 방법은 표시하는 것입니다.
BFS (Breadth First Search)
그래프를 탐색하는 방법에는 여러 가지가 있습니다. BFS는 가장 일반적으로 사용되는 접근 방식입니다.
BFS는 선택한 노드 (소스 또는 시작 노드)에서 탐색을 시작하고 그래프를 계층 적으로 탐색하여 인접 노드 (소스 노드에 직접 연결된 노드)를 탐색해야하는 탐색 알고리즘입니다. 그런 다음 다음 수준의 인접 노드로 이동해야합니다.
BFS라는 이름에서 알 수 있듯이 다음과 같이 그래프 폭을 가로 질러야합니다.
- 먼저 수평으로 이동하고 현재 레이어의 모든 노드를 방문합니다.
- 다음 레이어로 이동
다음 다이어그램을 고려하세요. 
계층 1의 노드 간 거리는 계층 2의 노드 간 거리보다 상대적으로 작습니다. 따라서 BFS에서는 계층 2의 노드로 이동하기 전에 계층 1의 모든 노드를 통과해야합니다.
자식 노드 탐색
그래프에는주기가 포함될 수 있으며, 그래프를 탐색하는 동안 동일한 노드로 다시 이동할 수 있습니다. 동일한 노드의 처리를 다시 방지하려면 처리 된 후 노드를 표시하는 부울 배열을 사용하십시오. 그래프 레이어의 노드를 방문하는 동안 비슷한 순서로 해당 자식 노드를 순회 할 수있는 방식으로 저장합니다.
이 프로세스를 쉽게 수행하려면 대기열을 사용하여 노드를 저장하고 모든 인접 항목 (직접 연결된 정점)이 표시 될 때까지 “방문 됨”으로 표시하십시오. 큐는 FIFO (First In First Out) 큐잉 방법을 따르므로 노드의 인접 노드는 노드에 삽입 된 순서대로 방문됩니다. 즉, 먼저 삽입 된 노드가 먼저 방문됩니다. 의 위에.
의사 코드
순회 프로세스 
순회 소스 노드에서 시작하여 s를 대기열에 넣습니다. 은 “방문 함”으로 표시됩니다.
첫 번째 반복
- 가 대기열에서 팝됩니다.
- 즉, 1과 2의 인접 항목이 순회됩니다.
- 이전에 순회되지 않은 1과 2가 순회됩니다.
- 대기열에 푸시
- 1 및 2는 방문한 것으로 표시됩니다.
두 번째 반복
- 1은 대기열에서 팝됩니다.
- 1 ie s와 3의 이웃이 순회됩니다.
- 는 “방문 됨”으로 표시되기 때문에 무시됩니다.
- 이전에 순회되지 않은 3이 순회됩니다.
- 대기열에 푸시
- 방문한 것으로 표시
세 번째 반복
- 2는 대기열에서 팝됩니다.
- 2, 즉 s, 3, 4의 이웃이 순회됩니다.
- 3 및 s는 “방문 됨”으로 표시되기 때문에 무시됩니다.
- 4는 이전에 순회되지 않았습니다.
- 대기열에 푸시 됨
- 방문한 것으로 표시됨
4 번째 반복
- 3은 대기열에서 팝됩니다.
- 3, 즉 1, 2, 5의 이웃이 순회됩니다.
- 1과 2는 “방문 됨”으로 표시되기 때문에 무시됩니다.
- 5는 이전에 순회되지 않았습니다.
- 대기열에 푸시
- 방문한 것으로 표시
다섯 번째 반복
- 4는 대기열에서 팝됩니다
- 4의 이웃, 즉 2가 순회됩니다
- 2는 이미 “방문 됨”으로 표시되었으므로 무시됩니다.
6 번째 반복
- 5는 대기열에서 팝됩니다.
- 이웃 5, 즉 3이 순회됩니다.
- 3은 이미 “방문 됨”으로 표시됨
큐가 비어 있고 루프에서 나옵니다. 모든 노드는 BFS를 사용하여 순회되었습니다.
그래프의 모든 간선이 동일한 가중치 인 경우 BFS를 사용하여 그래프에서 노드 간의 최소 거리를 찾을 수도 있습니다.
p>
예
이 다이어그램에서와 같이 소스 노드에서 시작하여 소스 간의 거리를 찾습니다. BFS 알고리즘을 따르지 않으면 소스 노드에서 노드 2로 이동 한 다음 노드 1로 이동할 수 있습니다.이 방법은 소스 노드와 노드 1 사이의 거리를 2로 계산하는 반면 최소 거리는 실제로 1입니다. BFS 알고리즘을 사용하여 최소 거리를 올바르게 계산할 수 있습니다.
복잡도
BFS의 시간 복잡도는 O (V + E)입니다. 여기서 V는 노드 수이고 E는 에지 수입니다.
응용 프로그램
1. 주어진 트리에서 각 노드의 레벨을 결정하는 방법은 무엇입니까?
BFS에서 알다시피 레벨을 순회합니다. BFS를 사용하여 각 노드의 수준을 확인할 수도 있습니다.
구현
이 코드는 BFS 코드와 유사하지만 다음과 같은 차이점 만 있습니다.
level] = level + 1;
이 코드에서 각 노드를 방문하는 동안 해당 노드의 수준은 상위 노드 수준의 증분으로 설정됩니다. 이것이 각 노드의 수준이 결정되는 방법입니다.
2 . 0-1 BFS
이 유형의 BFS는 그래프의 가장자리에 가중치가 0 또는 1 인 경우 그래프에서 두 노드 사이의 최단 거리를 찾는 데 사용됩니다. 앞에서 설명한 BFS를 적용하는 경우 이 기사에서는 두 노드 사이의 최적 거리에 대해 잘못된 결과를 얻을 수 있습니다.
이 접근 방식에서는 최적 거리의 조건이 확인 될 때 노드를 표시하는 데 부울 배열을 사용하지 않습니다. 각 노드를 방문하십시오. 이중 종료 대기열은 노드를 저장하는 데 사용됩니다. 0-1 BFS에서 에지의 가중치가 0이면 노드가 대기열에서 빼기 앞으로 밀려납니다. 가장자리의 가중치가 1이면 노드가 대기열에서 빼기 뒤로 밀려납니다.
구현
Q는 양단 대기열입니다. 거리는 배열이며 거리는 시작 노드에서 v 노드까지의 거리를 포함합니다. 처음에 소스 노드에서 각 노드까지 정의 된 거리는 무한대입니다.
다음 그래프를 통해이 코드를 이해하겠습니다.
그래프의 인접 목록은 다음과 같습니다.
여기서 “s”는 0 또는 소스 노드로 간주됩니다.
0-> 1-> 3-> 2
edges.first = 1, edge.second = 1
edges.first = 3, edges.second = 0
edges.first = 2, edge.second = 1
1 -> 0-> 4
edges.first = 0, edges.second = 1
edges.first = 4 , edge.second = 0
2-> 0-> 3
edges.first = 0 , edge.second = 0
edges.first = 3, edge.second = 0
3-> 0-> 2-> 4
edges.first = 0, edges.second = 0
edges.first = 2, edge.second = 0
edges.first = 4, edge.second = 0
4-> 1-> 3
edges.first = 1, edge.second = 0
edges.first = 3, edge.second = 0
BFS 알고리즘을 사용하는 경우 결과가 잘못 표시됩니다. s 사이의 최적 거리 노드 1과 s 및 노드 2를 각각 1로 지정합니다. 이는 s의 자식을 방문하여 s와 자식 사이의 거리 인 1을 계산하기 때문입니다. 실제 최적 거리는 두 경우 모두 0입니다.
처리
소스 노드, 즉 0에서 시작하여 1, 2, 3으로 이동합니다. 0과 1과 0과 2 사이의 에지 가중치는 각각 1이므로 , 1 및 2는 대기열 뒤로 푸시됩니다. 그러나 0과 3 사이의 에지 가중치가 0이므로 3은 대기열의 맨 앞으로 푸시됩니다. 거리는 그에 따라 거리 배열로 유지됩니다.
3은 대기열에서 팝되고 동일한 프로세스가 이웃에 적용됩니다.