[알고리즘 이론] DFS, BFS (1)

🌀 그래프 🌀

프로그래밍에서 그래프는 크게 2가지로 나타낼 수 있음.

1. 인접행렬 : 2차원 배열로 그래프를 표현

2. 인접 리스트 : 리스트로 그래프를 표현

graph

#인접행렬 방식
INF = 999999999

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]   

#인접리스트 방식
graph2 = [[] for i in range(3)]

#노드 0에 연결된 노드정보
graph2[0].append((1, 7))
graph2[0].append((2, 5))
    
#노드 1에 연결된 노드정보
graph2[1].append((0,7))
#노드 2..
graph2[2].append((0,5))

🌀 DFS 🌀

Depth-First-Search, 깊이 우선 탐색

그래프에서 깊은 부분을 먼저 탐색한다. 그래프는 노드(=정점, vertex)와 간선(edge)으로 이루어짐.

 

⚡️DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입 & 방문 처리

2. 스택의 최상단노드에 방문하지 않은 인접 노드가 있다면 그 인접노드를 스택에 넣고 방문처리.

    방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄

3.  2번과정을 더 이상 수행할 수 없을 때까지 반복

🌀 BFS 🌀

Breadth-First-Search, 너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘

 

⚡️BFS 동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 & 방문처리

3. 2번 과정을 더이상 수행할 수 없을 때까지 반복