BFS ( Breadth First Search ) (java / python 코드)

sehunbang 2024. 2. 2. 23:31

BFS ( Breadth First Search )( 그래프에서의 최소 거리 )

그래프 G가 주어졌다고 가정합니다. 경로의 길이는 그 경로에 있는 간선(단계)의 수입니다. 노드 u에서 v까지의 거리, dist(u, v),는 u에서 v로 가는 최단 경로의 길이입니다. 경로가 존재하지 않으면 dist(u, v) = 1입니다.

D와 J 간의 거리: 4
A와 K 간의 거리: (다을수 없기 에 무한)

Distance Problem

input: 그래프 G 및 두 노드 u, v

output: u에서 v로의 거리

Shortest Path Problem

input: 그래프 G 및 두 노드 u, v

output: u에서 v로의 최단 경로.

만약에 이런 문제가 있다고 합시다.

선교사와 식인종 :

1. 선교사와 식인종 한 강으로 오는 선교사 3명과 식인종 3명이 있는데,

2. 보트는 2명만 태울 수 있습니다.

3. 언제나 강 한쪽에 있는 식인종 수가 선교사 수를 초과해서는 안 됩니다.

4. 모든 사람들이 보트를 최소한으로 이용하여 강을 건너려면 어떻게 해야 할까요?

이문제를 그래프로 표현해봅니다.

현재 상황의 타임 스탬프를 '구성(configuration)'이라고 부릅니다.

구성은 각 둑에 얼마나 많은 선교사와 식인종이 있으며, 보트의 위치를 나타냅니다.

예를 들면 (MC•, MMCC)는 왼쪽 둑에 선교사 1명 + 식인종 1명, 오른쪽 둑에 선교사 2명 + 식인종 2명, 보트는 왼쪽 둑에 있다는 것을 나타냅니다.

노드가 모든 구성인 그래프 G = (V, E)를 정의합니다.

노드는 모든 구성입니다.
두 노드는 한 노드(configuration)에서 여섯 명의 사람이 다른 노드(configuration)로 한 번의 보트 여행을 통해 이동할 수 있는 경우에만 간선으로 연결됩니다

Breadth-First Search(BFS)는 거리 및 최단 경로 문제를 해결하는 데 사용되는 전략입니다. BFS 전략은 노드를 "층별"이나 레벨별로 순회하는 것을 포함합니다. 다음은 단계별 안내입니다:

출발 노드 s를 방문: 초기 노드를 방문하여 시작합니다.
s에서 거리가 1인 모든 노드를 방문(V1이라고 부릅니다): 거리가 1인 모든 노드를 탐험하고 방문합니다.
V1에서 거리가 1인 모든 노드를 방문(V2라고 부릅니다): V1에서 거리가 1인 모든 노드를 탐험하고 방문합니다.
V2에서 거리가 1인 모든 노드를 방문(V3이라고 부릅니다): V2에서 거리가 1인 모든 노드를 탐험하고 방문합니다.
... ... 이러한 방식으로 계속 진행합니다.

BFS의 큐(Queue) 구현 탐험해야 할 노드의 큐를 유지합니다. 각 반복에서:

먼저 큐의 첫 번째 요소를 완료하고 큐에서 제거합니다(dequeue).
그런 다음 dequeued된 요소의 out-이웃을 큐에 enqueue합니다.

탐험해야 할 노드의 큐를 유지합니다. 각 반복에서:

먼저 큐의 첫 번째 요소를 완료하고 큐에서 제거합니다(dequeue).
그런 다음 dequeued된 요소의 out-이웃을 큐에 enqueue합니다

1 번째 턴

Q = [0]

2 번째 턴

(탐험할 노드의 큐를 유지하면서 각 반복에서 다음 단계를 수행합니다:)

큐의 첫 번째 요소를 완료하고 큐에서 제거합니다 (dequeue).
그 후, dequeue된 요소의 외부 이웃을 큐에 enqueue합니다)

Q = [6,5]

이런 식으로 계속 하다가 ...

......

목포 지점에 찾으면....

Q = [7,8]

Q = [8]

Q = [] 후 종료.

각 노드 u에 대해 dist(u) 필드를 유지합니다. bfs_explore(G, s) 절차.

input: 그래프 G 및 시작 노드 s

dist(s) ← 0

// 시작 노드의 거리를 0으로 설정 빈 큐 Q를 생성하고 enqueue(Q, s)

Q가 비어 있지 않은 동안 반복 u ← dequeue(Q) // Q에서 첫 번째 노드를 dequeue합니다. (참고: u는 Q에서 첫 번째 노드입니다)

모든 나가는 엣지(u, v)에 대해 dist(v)가 무한이면 enqueue(Q, v) dist(v) ← dist(u) + 1

Breadth-First Search - Complexity

복잡성 분석 G에서 BFS를 실행할 때, 모든 노드 u는 최대 한 번씩 enqueue 및 dequeue될 수 있습니다.

모든 간선은 최대 한 번씩 확인될 수 있습니다.

BFS 알고리즘의 실행 시간은 O(m + n)입니다. 여기서, m은 간선의 수, n은 노드의 수입니다

BFS 코드

java 코드

import java.util.*;
public class BFSExplore {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(5, 6));
        graph.put(1, Arrays.asList(3, 4));
        graph.put(2, Arrays.asList(3, 6));
        graph.put(3, Arrays.asList(7, 8));
        graph.put(4, Arrays.asList(3, 9));
        graph.put(5, Arrays.asList(2));
        graph.put(6, Arrays.asList(4));
        graph.put(7, Arrays.asList(8));
        graph.put(8, new ArrayList<>());
        graph.put(9, new ArrayList<>());
        int startNode = 0;
        Map<Integer, Integer> distances = bfsExplore(graph, startNode);
        System.out.println(distances);
    }
    public static Map<Integer, Integer> bfsExplore(Map<Integer, List<Integer>>
                                                           graph, int s) {
        Map<Integer, Integer> dist = new HashMap<>();
        for (int node : graph.keySet()) {
            dist.put(node, Integer.MAX_VALUE);
        }
        dist.put(s, 0);
        Queue<Integer> Q = new LinkedList<>();
        Q.add(s);
        while (!Q.isEmpty()) {
            int u = Q.poll(); // Dequeue a node
// Visit all neighbors of u
            for (int v : graph.get(u)) {
                if (dist.get(v) == Integer.MAX_VALUE) { // If node v hasn't been
                    visited
                    dist.put(v, dist.get(u) + 1);
                    Q.add(v);
                }
            }
        }
        return dist;
    }
}

python

from collections import deque
def enqueue(queue, item):
        """Adds an item to the end of the queue."""
        queue.append(item)
def dequeue(queue):
        """Removes and returns an item from the front of the queue."""
        return queue.popleft()
def bfs_explore(graph, s):
        # Graph is assumed to be represented as an adjacency list
# Initialize distances to infinity for all nodes
dist = {node: float('inf') for node in graph}
        # Set distance of starting node to 0
dist[s] = 0
        # Create an empty queue and enqueue the starting node
        Q = deque()
enqueue(Q, s)
while Q:
u = dequeue(Q) # Dequeue a node (from the front)
# Visit all neighbors of u
for v in graph[u]:
        if dist[v] == float('inf'): # If node v hasn't been visited
dist[v] = dist[u] + 1 # Update its distance
enqueue(Q, v) # Enqueue it (to the back)
return dist
# Example usage:
graph = {0: [5,6], 1: [3,4], 2: [3,6], 3:[7,8], 4:[3,9], 5:[2], 6:[4], 7:[8], 8:[],
        9:[]}
start_node = 0
print(bfs_explore(graph, start_node))