[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기

# 내용

그래프에서 많이쓰이는 넓이 우선탐색 방법(BFS)

시작 노드로부터 갈 수 있는 노드들을 차례로 방문예정 큐에 넣은 후, 방문완료 큐에 넣는다.

방문예정큐로부터 뽑아 방문하지 않았다면, 해당 노드에서 갈 수 있는 노드들을 뽑고, 방문완료 큐에 넣는 과정을 계속해서 반복하며, 더이상 방문할 노드가 없으면 끝이다.

 

파이썬에서는 그래프를 딕셔너리로 편하게 표현 할 수 있다. 

큐를 사용해도 되고, 파이썬의 강력한 list를 사용해 큐처럼 활용 가능하다.

파이썬의 리스트가 제공하는 extend를 사용하면 리스트를 맨뒤에 연장시켜준다.

 

# 사용 그래프

 

# 코드

# bfs ( 넓이 우선 탐색 )

def make_graph() :
  graph = dict()
  graph["A"] = ["B","C","D"]
  graph["B"] = ["A","E"]
  graph["C"] = ["A"]
  graph["D"] = ["A","F","G"]
  graph["E"] = ["B","H"]
  graph["F"] = ["D","I","J"]
  graph["G"] = ["D"]
  graph["H"] = ["E"]
  graph["I"] = ["F"]
  graph["J"] = ["F"]
  print(f"make OK {graph}")
  return graph

def bfs(graph,start_node) :
  # 큐 초기화
  queue_visited = list()
  queue_will_visit = list()

  # 시작노드
  cur_node = start_node
  # 시작노드와 연결된 노드 큐에 추가
  queue_will_visit.extend(graph[cur_node])
  # 방문 완료
  queue_visited.append(cur_node)

  while queue_will_visit :
    print(f"queue_visited : {queue_visited}",end="")
    print(f" queue_will_visit : {queue_will_visit}",end="")
    print(f" cur_node : {cur_node}")

    # 방문해야할 노드 하나 뽑음
    cur_node = queue_will_visit.pop(0)
    # 방문한 기록이 없다면
    if cur_node not in queue_visited :
      # 방문해야하는 노드들 기록
      queue_will_visit.extend(graph[cur_node])
      # 방문 완료
      queue_visited.append(cur_node)

  return queue_visited


if __name__ == '__main__':
  graph = make_graph()
  answer = bfs(graph,"A")
  print(answer)

 

# 시간복잡도

시간복잡도는 Vertex(노드) + Edge(간선)의 합이다.

while문이 V(ertex) + E(dge) 만큼 돈다는 의미이다.

 

O(V+E)