BFS

• 탐색 순서 : 1->2,3->4,5,6->7,8->9->10,11->12,13
• 별도의 시작노드가 주어져야 한다.

BFS(G,s) # G는 그래프, s는 시작 정점
    for v -> V
        visited[v] = False # 방문여부를 체크할 수 있는 배열 초기화 
    visited[s] = True # 시작정점에 대해서 방문 체크 
    enqueue(Q,s) # 시작정점을 큐에 삽입 
    while Q # 큐가 존재할때 까지 반복
        u= dequeue(Q) # 큐에서 노드 꺼내기 및 삭제 
        for v->L(u) # 해당 노드에서 갈 수 있는 모든 노드 탐색 
            if visited[v] == False # 방문여부 체크 
                visited[v] = True # 방문 체크 
                enqueue(Q,v) # 해당 노드를 큐에 삽입 

• 방문여부를 체크할 때는 불리안 값으로 체크할 수도 있지만, 정수형태로 체크해서 0이면 False, 0이 아닌 값이면 True로 표현함과 더불어 해당 노드까지 거리나 탐색횟수도 카운트 할 수 있다

📒 파이썬에서는 주로 Deque를 이용해서 구현한다.

---

다익스트라 (Dijkstra Algorithm)

• 다익스트라는 특정 정점에서 모든 노드까지의 최단거리를 찾는 알고리즘이다.
• 그리디 알고리즘에 기반한 알고리즘이다.
• 가중치가 있는 유향 그래프까지 가능
• 간선의 가중치가 모두 0 이상인 경우 단일 시작점 최단 경로 생성이 가능하다는 강력한 장점이 있다.

import heapq  # 우선순위 큐 구현을 위함

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
  distances[start] = 0  # 시작 값은 0이어야 함
  queue = []
  heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

  while queue:  # queue에 남아 있는 노드가 없으면 끝
    current_distance, current_destination = heapq.heappop(queue)  # 탐색 할 노드, 거리를 가져옴.

    if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음 + 방문여부 체크 
      continue

    for new_destination, new_distance in graph[current_destination].items():
      distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
      if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
        distances[new_destination] = distance
        heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입

  return distances

• 수행시간 : O(E logV)
• 파이썬에서는 힙큐를 통해 구현할 수 있다.
• 힙큐에서 힙정렬을 할때 0번째 인덱스를 기준으로 정렬을 하는데, 다익스트라는 그리디알고리즘에 기반해 거리우선으로 정렬해야하기 때문에 튜플값의 0번째 인덱스에 반드시 거리를 넣어줘야 한다.