그래프 탐색 알고리즘 (Graph Search Algorithm)

https://jin1ib.tistory.com/entry/BFS-DFS-1

그래프 탐색 알고리즘(Graph Search Algorithm)

 

 

1. DFS

깊이 우선 탐색이라고도 불림

재귀 혹은 스택을 통해 탐색을 수행하고 더이상 간선이 없을 때까지 탐색하면 다시 되돌아가 연결된 정점을 탐색

 

1. 시작점인 1번 노드를 스택에 넣고 방문처리를 한다.
2. 스택 최상단 노드(1번)와 미방문한 노드 중 가장 번호가 낮은 2번 넣고 방문처리
3. 스택 최상단 노드(2번)와 미방문한 노드(7번)를 스택에 넣고 방문처리
4. 스택 최상단 노드(7번)와 미방문한 노드 중 가장 번호가 낮은 6번 넣고 방문처리
5. 스택 최상단 노드(6번)와 미방문한 노드가 없을때는 추출(pop)
6. 스택 최상단 노드(7번)와 미방문한 노드(8번)를 스택에 넣고 방문처리
7. 이와같은 메커니즘으로 스택에 아무것도 없을때까지 반복

 

def dfs(v):
    v를 이미 방문한 곳으로 처리한다 
    for 각각의 v에 연결된 모든 정점 i에 대해서:
        if i에 방문하지 않았다면:
            dfs(i)

 

def dfs(v,visited=[]):
    visited.append(v)
    for i in graph[v]:
        if not i in visited:
            visited = dfs(i,visited)
    return visited # [1,2,5,6,7,3,4]

 

 

 

2. BFS

너비 우선 탐색이라고 불림

시작점을 큐에 넣은 뒤에, 큐에 아무런 요소가 없을 때까지 인접한 정접을 탐색해 나아가면서 진행

 

 

 

1. 시작점인 1을 큐에 넣고 방문처리를 한다.
2. 1을 꺼내고 인접한 정점인 2,3,8을 큐에 넣고 방문처리를 한다.
3. 큐에서 2를 꺼내고 방문하지 않은 7을 꺼내서 방문처리
4. 큐에서 3을 꺼내고 방문하지 않은 4,5를 꺼내서 방문처리
5. 위와 같이 큐에서 더이상 꺼낼것이 없을때까지 반복

 

** 큐 자료구조

3) FIFO를 리스트로 구현하는게 아니라 deque를 사용하는 이유는?

위 질문과 일맥상통하는 질문이다. deque에서 원소를 삽입할때는 .append(N)를 사용하고, 원소를 뺄때는 .popleft(),원소를 역순으로 바꾸고자 할때는 .reverse()를 사용한다.
그러나 리스트를 이용해서 특정 인덱스의 원소를 삭제하기위해 .pop를 사용한다면, 원소를 꺼내고 위치를 조정하는 O(k) 만큼 시간복잡도가 더 필요하기 때문에 list가 아닌 deque를 사용한다.

 

def bfs(v):
    큐 선언 
    v를 이미 방문한 곳으로 처리 
    v를 큐에 추가해준다 
    while 큐가 비어있지 않다면:
        큐에서 v를 pop해준다 
        for v에 연결된 각각의 정점 i에 대하여:
            if i에 아직 방문하지 않았다면:
                i를 방문한 곳으로 처리한다 
                큐에 i를 추가한다

 

def bfs(v): 
    visited = [v]
    que = [v]
    while que:
        v = que.pop(0)
        for i in graph[v]:
            if i not in visited:
                visited.append(i)
                que.append(i)
    return visited # [1, 2, 3, 4, 5, 6, 7]