Queue_1

BFS

---

BFS (Breadth First Search)

그래프를 탐색하는 방법에는 크게 두 가지가 있음

• 깊이 우선 탐색 (Depth First Search, BFS)

• 너비 우선 탐색 (Breadth First Search, BFS)

너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용함

출발 노드로 부터의 거리 혹은 시간을 구해야 할 때 사용

C에 인접하면서 방문하지 않은 점

A는 인접이지만 이미 방문했기 때문에 제외

BFS 예제

---

아까랑 다르게 Q에 요소를 넣을 경우 visited 에 방문 표시를 남김

가장 빠른 속도로 처리됨 -> 트리 같은 형태

거리에 관련된 정보를 구하고자 할 땐 BFS를 쓰는 것이 좋음

'''
V E : V 1~V 번 까지 V 개의 정점. E 개의 간선
E개의 간선 정보
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''
def bfs(s, N) :     # 시작정점 s, 노드 개수 N
    q = []  # 큐
    visited = [0] * (N+1)   # visited
    q.append(s)         # 시작점 인큐
    visited[s] = 1      # 시작점 방문표시
    while q:            # 큐가 비워질때까지...(남은 정점이 있으면)
        t = q.pop(0)
        # t에서 할 일....
        print(t)
        for i in adjl[t]:   # t에 인접인 정점
            if visited[i] == 0:     # 방문하지 않은 정점이면
                q.append(i)     # 인큐
                visited[i] = 1 + visited[t]     # 방문표시
    # print(visited)  # 거리 정보를 얻을 수 있음
V, E = map(int, input().split())

arr = list(map(int, input().split()))
# 인접 리스트 형태로 저장
adjl = [[] for _ in range(V+1)] # 0번부터 V 번 까지 배열을 갖는 리스트를 생성
for i in range(E):
    n1, n2 = arr[i*2], arr[i*2+1]   # 2개의 쌍을 읽어내는 방법
    adjl[n1].append(n2)
    adjl[n2].append(n1)     # 무향그래프

bfs(1, V)

노드의 거리

'''
3
6 5
1 4
1 3
2 3
2 5
4 6
1 6 
7 4
1 6
2 3
2 6
3 5
2 5 
9 9
2 6
4 7
5 7
1 5
2 9
3 9
4 8
5 3
7 8
1 9
'''
def bfs(s, N, G) :     # 시작정점 s, 노드 개수 N
    q = []  # 큐 생성
    visited = [0] * (N+1)   # visited 생성
    q.append(s)         # 시작점 인큐
    visited[s] = 1      # 인큐 표시
    while q:            # 처리 안된 정점이 남아있으면
        t = q.pop(0)    # 처리할 정점 디큐
        if t == G:
            return  visited[t] - 1    # 시작 점이 1부터 시작하기 때문에 간선 수를 나타내기 위해선 -1을 해줘야 함
        for i in adjl[t]:           # t 의 인접 정점이
            if visited[i]==0:           # 인큐되지 않았으면(처리된 적이 없으면)
                q.append(i)
                visited[i] = visited[t] + 1
    return  0           # G까지 경로가 없는 경우
T = int(input())
for tc in range(T):
    V, E = map(int, input().split())

    # 인접 리스트 형태로 저장
    adjl = [[] for _ in range(V+1)] # 0번부터 V 번 까지 배열을 갖는 리스트를 생성
    for i in range(E):
        n1, n2 = map(int, input().split())   # 2개의 쌍을 읽어내는 방법
        adjl[n1].append(n2)
        adjl[n2].append(n1)     # 무향그래프
    S, G = map(int, input().split())
    print(f'#{tc+1} {bfs(S, V, G)}')    # G 끝까지 가는 목적지