BFS 제대로 정리

BFS: 너비우선 탐색

그래프를 맹목적으로 탐색하는것이다

 

시간복잡도는

노드수:V

간선수: E

이떄시간복잡도는 O(V+E) 이다.

 

->단순 탐색방법으로 문제에 어떻게 적용하는가가 중요하다.

사용하는 문제유형

그래프의 모든 정점을 방문할시

최단거리 문제의 경우 BFS -> 최단거리 DFS 쓰면 최단거리 아닐수있음

 

BFS가 DFS보다 더빠름 대체적으로

BFS가 더 복잡함

 

일단 근데 그래프 자료구조 뭐로 쓰는데?

->뭐 어쩌구 저꺼구 제끼고

파이썬에서는 걍 딕셔너리 자료형에 리스트를 넣어서 구현한다. -> 인접 리스트 기반 그래프

 

key	value
A	B	C
B	A	D
C	A	G	H	I
D	B	E	F
E	D
F	D
G	C
H	C
I	C	J
J	I

요렇게 하면됨 key 값이 각 노드들

그리고 그 value 값으로 그거에 간선으로 연결된 노드들의 리스트를 넣어주면된다.

 

코드로 치면 이렇게 된다

graph = {}

graph['A'] = ["B","C"]
graph['B'] = ["A","D"]
graph['C'] = ["A","G","H","I"]
graph['D'] = ["B","E","F"]
graph['E'] = ["D"]
graph['F'] = ["D"]
graph['G'] = ["C"]
graph['H'] = ["C"]
graph['I'] = ["C","J"]
graph['J'] = ["I"]
#리스트의 원소들 순서는 상관없음

 

출처:https://rhdtka21.tistory.com/140

요런 느낌으로 가는거다

 

일단 구현해보자 구현만 하면 어짜피 나중에 아이디어랑 응용싸움이다 이거 구현이 문제가아냐

구현!!!!

큐 두개 만들거임

need visit 큐랑 -> 방문해야할것들

visited 큐 -> 이미 방문한것들  -> 방문한 노드들을 순서대로 기입한 큐이다

마지막에 visited 큐 까보면 방문한 순서대로 순서가 나온다.

 

개념의 순서 -> 일단  need visit 큐에 start할거 집어넣음

need visit 큐에서 첫번째 popleft하면서 그거 visited에 있는지 확인하고 없다면 visited에다가 넣어줌

-> 넣으면서 중복확인하고 만약 여기서 중복있으면 큐에 안넣고 need visited에도 아무것도 안넣음

넣어준 노드와 연결된노드 그냥 need visited에다가 넣음 (visited)에 있는지 없는지는 여기에 넣을때는 상관없음 

나중에 visited큐에 들어갈때 검사해서 있으면 안넣는거임

 

이제 코드로 구현해 볼것이다.

 

from collections import deque

graph = {}

graph['A'] = ["B","C"]
graph['B'] = ["A","D"]
graph['C'] = ["A","G","H","I"]
graph['D'] = ["B","E","F"]
graph['E'] = ["D"]
graph['F'] = ["D"]
graph['G'] = ["C"]
graph['H'] = ["C"]
graph['I'] = ["C","J"]
graph['J'] = ["I"]



#함수화 시켜서 쓸꺼
# 그래프는 graph,start_node는 시작점

# 강의에서는 queue 안쓰고 list 썻음 적절히 뜯어고쳐봐야지

def bfs (graph,start_node):
    visited = []
    need_visited= deque()

    #최초할일 need_visited에다가 start넣기
    need_visited.append(start_node)

    #while 문 조건으로 need_visited에 뭐가있는지없는지 이제 탐색할꼐 있는지 없는지 판단
    while need_visited:
        # 임시저장소 node에 가장 왼쪽 원소 뽑아서 visited에 있나 판단후 없다면 append하면서 need_visited 에도 원소 추가 
        node = need_visited.popleft()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

    return visited


print(bfs(graph=graph,start_node="A"))

# 구현은 간단하다

그냥 bfs 문제 풀면서 외우면 될꺼같다  이제 문제좀 풀어보면 될것이다.