그래프를 표현하는 두가지 방식

인접 행렬(Adjacency Matrix)

2차원 배열로 그래프의 연결 관계를 표현하는 방식
2차원 리스트로 구현을 함
a 노드에서 b 노드로 가는 비용을 graph[a,b]에서 알 수 있다.

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

인접 리스트(Adjacency List)

리스트로 그래프의 연결 관계를 표현하는 방식

링크드리스트로 구현을 함 -> c++이나 java의 경우는 linkedlist 라이브러리를 사용하여 구현하면 되고, python의 경우는 리스트 자료형에 append()와 같은 메서드를 제공하므로 2차원 리스트로 구현하면 된다.

#행이 3개인 2차원 리스트
graph = [[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

#노드 1에 ...
graph[1].append((0,7))

#노드 2에...
graph[2].append((0,5))

DFS(Depth-First Search)

깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
기본적으로 스택을 이용.

DFS의 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

DFS 예제

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
#visited = [False] * 9

BFS(Breadth Frist Search)

너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘.
기본적으로 큐를 이용.

BFS의 동작 과정

1. 탐색 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드에서 방문하지 않은 노드들을 모두 큐에 넣고 방문처리
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

BFS 예제

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    
    visited[start] = True
    
    while qeueue:
    	v = queue.popleft()
        print(v, end=' ')
        
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

언제 무엇을 써야할까?

이름 그대로, DFS는 해당 트리가 깊을 때, BFS는 해당 트리가 넓을 때 사용하는 것이 좋다.

문제 유형에 따라 나눠보면
현재 위치에서 가까운 노드들을 탐색해야하는 최단경로, 가중치 없는 그래프 문제: BFS
가중치가 존재하고, 탐색에 대한 제약 조건이 있는 문제, 트리, 백트래킹: DFS
*너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊다