📖 그래프 탐색 방법

📌 그래프 탐색

✅ 그래프 표현 방법 (복습)

1. 인접 행렬 (2차원 배열)

2. 인접 리스트

3. 간선 배열

✅ 탐색 기법

• 트리 (그래프, 2차원 배열) 순회(탐색)는 모든 자료(노드, 정점)를 빠짐 없이 탐색하는 것을 의미한다.

1. 깊이 우선 탐색 (DFS, Depth First Search)
   :

2. 너비 우선 탐색 (BFS, Breadth First Search)
   :

📌 깊이 우선 탐색(Depth First Search)

✅ DFS

• 깊이 우선 탐색

• 루트 노드(시작 정점, 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드(정점)로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회 방법

• 가장 마지막에 만났던 갈림길의 노드(정점)로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출(LIFO : Last In First Out) 자료구조인 스택(Stack) 사용

• 재귀 함수는 시스템 스택을 이용하므로 이를 이용하여 간단하게 구현할 수도 있음

✅ 트리 탐색 (Stack)

1. 루트 노드 stack push

2. stack 공백 상태가 될 때까지 반복
   1) stack에서 노드 (curr)pop
   2) curr의 모든 자식 노드 stack push

DFS(v) { // v : 루트 노드
	stack.push(v)
    while(not stack.isEmpty) {
		curr = stack.pop
        for w in (curr의 모든 자식)
        	stack.push(w)
    }
}

✅ 트리 탐색 (재귀)

1. 현재 노드 v 방문
2. v의 자식 노드 w를 차례로 재귀 호출

DFS(v) {
	v 방문;
    for w in (v의 모든 자식) {
    	DFS(w);
    }
}

✅ 그래프 탐색 (재귀)

// G : 그래프
// visited : 방문 배열

DFS(v) {
	visited[v] <- TRUE // v 방문 설정
    
    FOR each all w in adjacency(G, v)
    	IF visited != True
        	DFS(w)

✅ 2차원 배열에서의 DFS

// arr : 2차원 배열
// visited : 방문 배열
DFS(r, c) {
	visited[r][c] <- TRUE // v 방문 설정
    
    FOR(r, c)를 기준으로 4방향 탐색
    	IF 다음 좌표는 이동 가능한 것인지 체크
        	DFS(nr, nc)
}

📌 너비 우선 탐색 (Breadth First Search)

✅ BFS

• BFS는 너비 우선 탐색

• 너비 우선 탐색은 탐색 루트 노드 (시작 정점, 출발 위치)의 자식 노드(인접한 정점)들을 모두 차례로 방문한 후에 방문했던 자식 노드를(인접한 정점) 시작점으로 하여 다시 해당 노드의 자식 노드(인접한 정점)들을 차례로 방문하는 방식

• 자식 노드(인접한 정점)들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출(FIFO, First In First Out) 형태의 자료구조인 큐를 활용함.

• 너비 우선 탐색은 인접한 노드들부터 차례대로 방문하여 시작 정점과 끝 정점이 주어졌을 때 최단 길이를 구할 수 있다.

✅ 트리 탐색

1. 루트 노드를 Queue에 탐색

2. Queue가 공백이 될 때 까지 반복 수행
   1) Quyeue에서 원소(cur) 꺼내기
   2) 해당 원소 방문
   3) cur의 자식 노드 Queue에 삽입

✅ 그래프 탐색

// 그래프 G, 탐색 시작점 v
BFS(G, v)
	큐 생성
    시작점 v를 큐에 삽입
    while 큐가 비어있지 않은 경우
    	t = 큐의 첫 원소 반환
        FOR t와 연결된 모든 선에 대해
        	u <- t의 이웃점
            u가 방문되지 않은 곳이면,
            u를 큐에 넣고, 방문한 것으로 표시