[수업기록] 알고리즘 : queue (2)

1. bfs 

- bfs는 쉽게 생각하면, 교실에서 안내문을 돌릴때(문단 대표 한명이 받고, 그줄 나눠주고 그 다음줄로 넘기는 형식)

- 가장 가까운 노드를 먼저 처리한다- 인접한 노드들 인큐에 append- 최단거리 탐색- 왜 que를 쓸까? 

 

 

dfs vs bfs

 

def BFS(G,v): #그래프 g, 탐색 시작점 v
    #초기화 단계 
    visited = [0] * (n+1)  #n : 정점의 개수 #1번부터 시작하는 경우에
    queue = [] # 큐 생성 
    queue.append(v) #시작점 v를 큐에 삽입
    visited[v] = 1
    
    #탐색 단계
    while queue: #큐가 비어있지 않은 경우
        t = queue.pop(0)
        visit(t)

        for i in G[t]: #t와 연결된 모든 정점에 대해
            if not visited[i]: #방문되지 않은 곳이라면
                queue.append(i)
                visited[i] = visited[t] + 1 #n으로부터 1만큼 이동 #탐색깊이를 visited를 활용

 

def bfs(s, V): #시작점, 정점수
    # 준비 :
    visited  = [0] * (V+1)
    q = [] #큐생성
    q.append(s) #시작점 인큐
    visited[s] = 1 #방문표시

    # 탐색 :
    while q:  #탐색할 정점이 남아있으면
        t = q.pop()
        for w in adj_l[t]:
            if visited[w] == 0:
                q.append(w)
                visited[w] = 1



V,E = map(int,input().split())
arr = list(map(int,input().split()))
adj_l = [[]for i in range(V+1)]
for i in range(E):
    v1,v2 = arr[i*2], arr[i*2+1]
    adj_l[v1].append(v2)
    adj_l[v2].append(v1) #방향 없는경우 삭제
    
bfs(1,V) #출발점, 정점수