그래프(Graph), 그리고 DFS와 BFS - 1. 그래프에 관하여

DFS와 BFS는 탐색 알고리즘의 한 종류이다.

 

이 알고리즘은 그래프를 알고 있어야 이해할 수 있는 알고리즘이다. 그래서 그래프부터 다루고자 한다.

 

그래프란 점(정점)과 선(간선)으로 이루어진 자료구조를 의미한다.

 

별개 아니다. 그냥 숫자(인덱스)가 붙은 점들과 그 점들 간의 관계를 선으로 표시한 것 뿐이다.

 

 

출처 : https://www.javatpoint.com/bfs-vs-dfs

페이스북이 그래프고, 그래프가 곧 페이스북?

 

단순한 점과 선들의 조합인 그래프를 활용해 마크주커버그가 페이스북을 만들었다.

 

이 페이스북을 사례로 그래프를 설명할 것이다. 자고로 본인은 페이스북 안한지 100만년된 듯 싶다.

 

각 점을 사람으로 간주하고 각 선을 팔로우하여 관계를 표시하면 그것이 그래프다.

 

눈치 챈 사람도 있겠지만 A가 B를 팔로우하였다. B가 A를 맞팔로우하였다와 같이 (간)선들은 일종의 방향성을 가질 수 있다.

 

이와 같은 방향성의 유무를 따진 그래프가 유향 그래프(Directed Graph)와 무향 그래프(Undirected Graph)이다.

 

유향 그래프는 A가 B를 팔로우하였다. 즉 A->B라는 표시가 나타난 그래프이고, 무향 그래프는 A-B와 같이 서로 연결되어 있다라는 정보를 주는 그래프이다. 여기서 무향그래프는 다르게 보면 연결고리가 존재한다면(간선이 존재한다면) 무조건 양방향을 가리키는 간선인 그래프로 봐도 무방하다. 

 

연결된 선들의 방향성에 따라 탐색의 방향이 달라지기 때문에 간선의 방향성을 매우 중요하게 여기자.
관심 있는 사람에게 팔로우를 함부로 할 수 없는 것과 같이 말이다.

 

다시 페이스북으로 돌아와보자, 당신은 3명의 팔로워가 있고 4명을 팔로우하고 있다면 당신과 직접적으로 관련된 사람은 4명 ~ 7명이다.(3명의 팔로워를 당신이 모두 맞팔하고, 나머지 1명은 당신을 팔로우 하고 있지 않을시 4명, 그리고 전부 다른 사람일 경우 7명) 이 사람들이 그래프의 인접 정점(adjacent vertex)에 해당한다

 

페이스북을 보면 특정 사람의 팔로잉 갯수나 팔로워를 볼 수 있다. (기억이 가물가물하다)

 

이 때 팔로잉한 사람 수 또는 팔로워의 수는 그래프의 차수(인접한[바로 옆의] 정점[adjacent vertex]의 수)와 같은 개념이다. 

 

A는 3명의 팔로워가 있고, 4명을 팔로우하고 있는 경우는 다음과 같이 보면 된다.

 

나를 팔로우 해주는 사람의 수 = 진입 차수 = 3

내가 팔로우 하는 사람의 수 = 진출 차수 = 4

 

마지막으로 페이스북에는 알 수도 있는 친구라는 기능이 있다. 단순하게 생각해보면 내 친구의 친구 = 알 수 있는 사람이라고 생각하면 되지 않나? 내 기준 모든 친구를 일일이 확인하고 그리고 내 친구들의 친구들을 일일이 보는 것, 그것이 바로 DFS나 BFS이다.

 

DFS, 즉 깊이 우선 탐색은 '한 놈만 x진다!  그 친구의 친구의 친구의 친구의 친구, 더이상 친구가 없을 때 까지 일일이 클릭의 클릭의 클릭을 거듭했다가, 잠시 정신차린 뒤에 다른 친구를 보고, 어? 너도? x진다'는 마인드로 행위를 반복하는 것이다.

 

"깊이 우선(DFS)-> 일단 눈에 보이는 한 놈만 x진다."

 

반면 BFS, 즉 너비 우선 탐색은 '어? 내 여자친구가 내 친구를 알아? ok 일단 킵해두고, 다음, 어? 얘도 알아? 일단 킵해두고 다음, 어 이제 킵할 게 없네. 킵 해둔 거 봐야겠다'는 마인드로 행위를 반복하는 것이다.

너비 우선(BFS) -> 일단 킵해두고 다음, 없어? 그럼 킵 해둔 거 친구 봐야겠다.

 

 

이해가 안된다면 본인의 글짓기 실력이 부족해서다.

(사실 프로그래밍 언어든 어떤 학문이든 번역본을 보게 되면 오히려 이해가 안되는 경우가 허다하다.)

 

이제 되었다. DFS, BFS를 공부하기 위한 그래프에 관련된 내용은 이정도면 충분하다. 이제 DFS와 BFS를 부수러 가보자!

 

 

다음 주제 : DFS(Depth-First Search : 깊이 우선 탐색) 

그다음 주제 : BFS(Breadth-First Search : 너비 우선 탐색)