안녕하세요. 이번 시간에는 그래프를 검색하는 방법에 대해 알아볼게요.

그래프를 검색하는 방법에는 대표적으로 깊이 우선 탐색

넓이 우선 탐색 이렇게 두 가지가 있어요. 깊이 우선 탐색은 랩스 퍼스트 서치

약자로 DFS라고 하고요, 넓이 우선 탐색은 레벨 퍼스트 서치 약자로는 BFS라고 해요.

바이너리 트리를 순회할 때 사용했던 프리오더, 인오더, 포스트오더

방법이 바로 이 깊이 우선 탐색에 속합니다. 깊이 우선 탐색 방법은 말

그대로 하나의 자식 노드를 방문한 후, 해당 자식 노드의

모든 자식 노드를 끝까지 파고드는 겁니다.

그리고 나와서 다음 경로를 가고, 또 나와서 그 다음 경로를 가고 이런

식으로 자식 노드들을 마지막 노드를 만날 때까지 갔다가 다시 올라와서

옆에 형제 노드를 방문하는 겁니다. 넓이 우선 탐색은 시작점에서 자기 자식 노드들을 먼저 다 방문하고 그

다음에 자식의 자식을 방문하고 하는 식으로 레벨 단위로 검색을 하는 것이

BFS입니다. 그림으로 DFS와 BFS 둘의 이동 경로를 순서대로 한번

8, 9. 차이점이 눈으로 보이시나요? 그럼 이번에는 어떻게 구현하는지 한번 살펴볼게요. 깊이 우선 탐색은 스택을

이용해서 그런 하구요 넓이 우선 탐색은 BFS를 이용해서 그렇게 합니다

스택을 이용해서 구현하는 DFS를 먼저 살펴볼게요

DFS를 진행하는 순서는요, 스택을 하나 만들고 처음에는 스택에 노드가

없으니까 시작할 노드를 일단 넣고 그 다음부터 시작을 하는데요,

스택에서 노드를 하나 꺼내서 그 해당 자식 노드를 전부 스택에 넣고,

꺼낸 노드는 출력하는 거예요. 여기서 자식 노드를 스택에 넣을 때는 한

번씩, 스택에 담았던 노드는 다시 넣지 않습니다.

0부터 시작해서 이 그래프를 한번 순회해 볼게요.

우선 시작 노드 0번 노드를 스택에 담았죠.

자, 그럼 돌립니다. 스택에서 하나 꺼내고 그 노드의 자식 노드를 스택에

담아줍니다. 그리고 얘는 출력해 줍니다. 또 스택에서 데이터를 꺼내고 자식 노드를 추가합니다.

그리고 얘는 출력하고 또 스택에서 꺼내고 예, 자식 노드를 추가하는데요,

이번에는 아까 이미 스택에 들어갔죠? 그럼 이번에는 빼고 2번하고 5

번만 스택에 넣어줍니다. 그리고 꺼내서 출력합니다. 스택에서 데이터를 하나 더

꺼내고 이 노드의 자식 노드를 스택에 추가합니다.

그리고 꺼내 출력합니다. 스택에서 데이터를 하나 꺼내고 자식 노드가

없으니까 그냥 출력합니다. 스택에서 데이터를 하나 꺼내고 자식 노드를

스택에 추가합니다. 그리고 꺼내 출력합니다. 스택에서 데이터를 하나 더 꺼내고 자식 노드가

없으니까 그냥 출력합니다. 스택에서 데이터를 하나 꺼내고 자식 노드가 2개

2개 있지만 이미 스택에 넣었죠. 그러면 그냥 출력합니다. 스택에서 데이터를 하나 꺼내고, 얘도 마찬가지로 다

이미 스택에 들어갔으니까요. 그러면 그냥 출력합니다. 이제 스택이 비었죠.

이번엔 큐를 이용해서 구현하는 BFS 한번 해볼게요.

BFS를 진행하는 순서는요. 일단 큐를 하나 만들고요,

처음에는 큐에 노드가 없으니까 시작할 노드를 먼저 넣고, 그 다음부터

시작을 하는데요. 마찬가지로 큐에서 노드를 하나 꺼내서 그 해당 자식 노드들을 전부

큐에 넣고, 꺼낼 노드는 출력하면 되는 거예요. 여기서 자식 노드를 큐에

넣을 때, 한 번 큐에 들어간 노드는 다시 넣지 않습니다.

그럼 0부터 시작해서 BFS를 수행해볼게요. 시작 노드는 먼저 큐에 넣었으니까 방문했다고 마크를 하고, 그럼

시작해볼게요. 큐는 위로 집어넣고 아래에서 빼죠. 밑에서 하나 꺼내고, 그 노드의

자식 노드들을 표에 추가하고, 그 노드는 출력합니다.

표에서 노드 하나를 꺼내고 자식 노드들을 하나씩 추가합니다.

그리고 꺼낸 노드는 출력합니다. 표에서 데이터를 하나 꺼내고, 그 노드의

자식 노드를 추가하는데요. 다른 노드들은 이미 처리되었습니다.

40,000을 추가합니다. 그리고 꺼낸 노드는 출력합니다.  회사나 꺼내고

남은 자식 노드를 추가합니다. 3을 출력합니다. 큐에서 데이터를 하나 꺼내고, 4의 자식 노드들은 이미

다 처리되었습니다. 그러면 그냥 출력합니다. 큐에서 데이터를 하나 꺼내고, 자식 노드들을

하나씩 추가합니다. 그리고 꺼낸 노드는 출력합니다. 큐에서 데이터를 하나 꺼내고, 자식 노드를

추가합니다. 꺼낸 노드를 출력합니다. 데이터를 하나 꺼내고, 자식

노드가 없으니까 그냥 출력합니다. 데이터를 하나 꺼내고, 추가할 자식 노드가

없으니까 그냥 출력합니다. 그리고 이제 Q가 비었죠. 그러면 순회가

종료되는 거에요. 이렇게 두 가지 방법을 통해서 순회하면서 출력한 결과입니다.

그런데 그래프는 트리가 아니니까 반드시 0에서 시작할 필요는 없어요.

3에서 시작해도 결과는 다르지만, 규칙에 맞게 모든 노드들이 잘

처리됩니다. 추가로 DFS를 구현할 때 재귀 호출을 이용하면 코드가 훨씬 간결하고

세련된 집니다. 재귀 함수를 이용한 신의 방법은요, 일단 노드를 방문하면 데이터를 출력하고

자식들을 순서대로 재귀적으로 호출해 주는 거예요.

자식들이 호출을 받으면 마찬가지로 자기 자신을 출력하고 자기 자식들을 재귀적으로

호출하겠죠. 그렇게 호출을 받으면 반환하기 전에 자식들을 먼저 호출하기 때문에 재귀

호출로 깊이 우선 탐색이 가능한 거예요. 그럼 이 그래프에서 0에서 시작할

때 순회하는 경로를 한번 살펴볼게요.

우선 시작 노드 0으로 함수를 호출합니다. 함수 호출되면 자식을 부르기

전에 먼저 자기 자신을 출력해 줘요. 만약에 재귀 호출을 다녀와서 출력을 한다면 자식들이 먼저 출력되니까

거꾸로 되어서, 잎에서부터 올라오는 게 되어 버려서 이상하잖아요.

그러니까 호출되면 일단 출력을 합니다. 0 출력. 자식 노드 2를 호출합니다. 출력하고… 요 이래 이야기죠.

첫 번째 자식 2를 호출하고 출력합니다. 여기에서 스택과 다른 점은요,

자식이 1개 이상인 경우에 스택은 쌓고 나서 호출하기 때문에 자식 중에

맨 마지막으로 들어간 노드가 먼저 출력이 되는데요,

재귀 호출은 정방향으로 호출하기 때문에 2가 먼저 출력됩니다. 그리고

2의 자식 노드 4와 4가 남아 있죠. 4는 1의 자식 노드이면서 2의 자식 노드이기도

여기서 먼저 사회 노드를 방문하면 나중에 1로 돌아왔을 때 이 노드를 방문하지 않겠죠. 그런데 여기에는 자식 노드도 있고, 삶(부모) 노드도 있어요.

어느 쪽으로 갈지에 따라서 3을 역순으로 출력할지 말지를 결정하는데요.

그 순서는 연결 관계를 입력할 때 어떤 노드와의 관계를 먼저 입력했는지에 따라 결정돼요. 저는 왼쪽부터 입력했다고 가정하고, 3을 먼저

방문하도록 하겠습니다. 3을 먼저 호출하고 출력. 3의 자식 노드

중에서 사회의 자식 노드기도 하죠. 그런데 여기서 먼저 만났으니까 3을 사회의 자식 노드로서 호출하고 출력.

나중에 돌아와서 1을 호출하려고 봤을 때, 3은 이미 호출됐기 때문에 더 이상 호출하지 않겠죠.

이제 3의 자식 노드들은 다 호출되고 하나 남았네요. 5를 호출하고 출력. 5의 자식 노드인 6이 있는데, 여기 먼저 있으니까

요걸 호출하고 출력. 6의 자식 노드인 8이 있으니까 8을 호출하고 출력. 더 이상

자식 노드가 없으니까 나와서, 다음 자식 노드 7을 호출합니다. 그리고

출력. 그리고 지금까지 호출된 것들을 쭉 나열하고 프로그램을 종료합니다.

코드로 구현해 볼게요. 우선 BFS에 필요한 Q는 지난 시간에 만든

Q 클래스를 사용할게요. 코드가 궁금하신 분들은 표기된 영상을

참고해주세요. 그럼 우선 그래프 클래스를 선언하고

노드가 필요하죠. 데이터는 간단하게 정수로 할게요.

그리고 인접한 노드들과의 관계는 링크드 리스트로 표현하겠습니다. 제가

아까 설명하면서 자식 노드라는 표현을 계속 썼는데요,

사실 그래프에서는 부모 자식 관계는 없구요,

인접한 노드가 뭐냐, 이렇게 링크드 리스트로 쭉 나열합니다.

대부분 트리의 예시니까 자식이라고 하는 게 쉬울 것 같아서 그냥

자식이라고 한 거구요. 사실 인접한 노드라고 해야 정확한 표현입니다.

그리고 방문했는지 마킹하는 플래그도 하나 선언합니다.

노드 생성자에서는 데이터를 받고, 마킹 플래그를 false로 초기화하고, 링크드 리스트를 준비시킵니다.

이제 그래프를 만들어 볼게요. 그래프에는 노드들을 저장할 배열이 필요하죠.

간단하게 구현하기 위해서 그래프의 노드 개수는 2개로 고정으로 할게요.

노드 개수를 받아서 그 개수만큼 배열 방을 만들어 줍니다.

[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java

[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java