그래프 / 그래프 탐색 / DFS / BFS

요약

그래프

• 그래프는 네트워크 모델이다

• 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.

• self-loop 뿐만 아니라 loop/circuit 모두 가능하다.

• 부모-자식 관계 개념이 없다.

• 간선의 유무는 그래프에 따라 다르다.

그래프의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.

• 하나의 점을 그래프에서는 정점(vertes, 노드, 정점)이라고 표현하고, 하나의 선은 간선(edge)라고 합니다.

• 간선으로 연결된 두 정점은 관계가 있다고 말할 수 있으며, 이를 인접하다고 한다.

그래프 용어

• 정점(vertex): 위치 개념. node라고도 불림

• 간선(edge): 정점들을 연결하는 선. 정점과의 관계. 분기(branch)라고도 불림

• 인접 정점(adjacent vertex): 어떠한 정점에서 1개의 간선으로 직접 연결된 정점

• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수.
• 무방향 그래프에서 존재하는 정점의 모든 차수의 합 == 무방향 그래프의 간선 수의 2배

• 진입 차수(in-degree): 방향 그래프에서 외부에서 들어오는 간선의 수. 내차수

• 진출 차수(out-degree): 방향 그래프에서 외부로 나가는 간선의 수. 외차수
• 방향 그래프에 있는 정점의 진입차수와 진출차수의 합 == 방향 그래프의 간선 수

• 경로(path) : 두 정점을 잇는 간선의 순서(sequence)이다.

• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수

• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우

• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 종류

그래프의 표현 방식

1. 인접 행렬
• 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 표현합니다.
• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냅니다.
• 두 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한 표입니다.
• 최단 경로를 찾고자 할 때 주로 사용됩니다.

1. 인접 리스트
• 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현합니다.
• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있습니다.
• 메모리를 효율적으로 사용하고 싶을 때 사용합니다.

1. 인접 배열
• 각 정점에 연결된 정점들을 연결 리스트로 저장하든 대신 배열로 저장한다.
• 각 노드에 인접 정점 수를 명시하여, 필요한 부분까지 배열을 탐색합니다.
• 배열을 정렬된 상태로 만들면 이진 탐색을 사용할 수 있기 때문에 |log2 K| + 1 번 이내의 비교로 인접성을 확인할 수 있다.

1. 인접 해시 테이블
• 각 인접 배열 크기를 더해 필요한 전체 배열 크기를 다 계산한 다음 하나의 배열을 할당받는다.
• 인접 배열을 해시 테이블로 대체할 수 있다.
• 인접 배열에서의 2배정도 되는 크기로 해시테이블을 만든다면 인접성의 확인을 훨씬 빠르게 할 수 있다.

그래프 탐색

• 그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한번씩 방문하는 것입니다.

DFS(깊이 우선 탐색, Depth-First Depth)

• 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

• 루트 노드(1)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.

• 스택/재귀함수를 이용해 표현할 수 있습니다.

• DFS 작동 방법
1. 탐색 시작 노드(루트 노드)를 큐에 삽입하고 방문 처리를 합니다(boolean 배열을 생성하고, 해당 노드를 true 처리합니다)
2. 스택 최상단 노드의 인접 노드 중 방문하지 않은 노드 하나를 스택에 넣고 방문처리를 합니다. 만약 인접 노드를 모두 방문한 경우 해당 노드를 pop 처리합니다(stack pop과 해당 노드 false 처리)
3. 2단계를 더 이상 수행할 수 없을 때까지 반복합니다(스택이 빌 경우 = 모든 경로를 탐색한 경우)

• DFS 이용 사례
• 모든 정점을 방문하는 경우
• 경로/방법 등을 구할 때 모든 경로와 방법을 모두 탐색해야 하는 경우(완전 탐색)

BFS(너비 우선 탐색, Breadth-First Depth)

• 최대한 넓게 이동한 다음, 더이상 넓게 갈 곳이 없을 경우 아래로 이동

• 큐를 이용해서 구현합니다.

• BFS 작동 방법
1. 탐색 시작 노드(루트 노드)를 큐에 삽입하고 방문 처리를 합니다(boolean 배열을 생성하고, 해당 큐를 true 처리합니다)
2. 큐에서 Deque 하고, Deque 한 노드의 방문하지 않은 모든 인접노드를 큐에 넣고 방문처리한다.
3. 2 단계를 더 이상 수행할 수 없을 때까지 반복합니다(큐가 빌 때까지)

• BFS 이용 사례
• 모든 정점을 방문하는 경우
• 최단 거리를 구해야 하는 경우

참고 사이트