[Algorithm]그래프1

📚그래프

📄개념

그래프 G는 V와 E의 쌍으로 나타낼 수 있다.

V: 정점(vertex)의 집합. 연결할 객체의 집합

E: 간선(edge)의 집합. 정점들을 연결하는 선의 집합

📄종류

간선의 방향성에 따라 그래프를 구분할 수 있다. 간선에 방향(화살표)이 없으면 무방향 그래프, 방향(화살표)이 있으면 방향 그래프로 구분할 수 있다.

무방향 그래프 표현: (1, 4)=(4, 1)

방향 그래프 표현: <1, 4> <4, 1>

그리고 간선에 비용이나 시간과 같은 의미를 갖는 가중치를 부여한 그래프를 가중 그래프라고 한다.

그래프에서 특정한 조건을 만족하는 경우를 트리라고 한다. 트리가 되는 특정한 조건은 다음과 같다.

1. 무방향 그래프
2. 모든 정점이 연결된 그래프
3. 사이클이 없는 그래프

📄그래프 구현 방법

• 인접행렬

정점의 집합 V={1,2,…,n}인 그래프가 있을 때, 인접 행렬 A = (n x n)으로 그래프를 표현할 수 있다. A의 임의의 원소 A[i, j]의 값은 1 또는 0으로 지정된다. 정점 i와 j 사이에 간선이 존재하면 1, 존재하지 않으면 0이 된다. 그리고 i = j인 대각선상의 값은 0으로 정한다.

• 인접 리스트

임의의 정점을 중심으로 인접한 모든 정점을 하나의 연결 리스트로 표현한다.

📚그래프 순회

그래프의 모든 정점을 체계적으로 한 번씩 방문하는 것을 말한다. 그래프를 탐색하는 것과 같다.

• 탐색 과정에서의 정점 구분
  • 방문 정점: 방문이 완료된 정점
  • 주변 정점: 방문 정점에 인접한 정점 중에서 아직 방문하지 않은 정점
  • 미도달 정점: 방문 정점도 주변 정점도 아닌 전혀 접근하지 못한 정점

깊이 우선 탐색 -> 최근의 주변 정점을 우선 방문

너비 우선 탐색 -> 주변 정점 중에서 오래된 것을 우선 방문

📄깊이 우선 탐색(DFS)

한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하여 탐색하는 방법 -> 최근의 주변 정점을 우선으로 방문하는 탐색 방법

• 스택 구조를 사용해서 구현

현재 정점에 인접한 정점이 없어서 더 이상 탐색을 진행할 수 없으면 거꾸로 되돌아가면서 아직 탐색하지 않은 인접한 정점을 찾아서 탐색을 진행한다.

• 처리 과정
  • 시작 정점을 스택에 삽입
  • 스택의 top에 있는 정점에 대한 주변 정점이 존재하면 그중 하나의 정점을 스택에 삽입하고 방문한 정점으로 처리. 주변 정점이 없다면 스택의 top에 있는 정점을 제거
  • 스택에 더 이상 정점이 없을 때까지 두 번째 과정을 반복

깊이 우선 트리: DFS를 수행하는 과정에서 방문한 정점과 그때 사용된 간선으로 구성되는 트리

• 성능과 특징

인접리스트: O(|V| + |E|)

인접 행렬: O(|V|²)

DFS를 순환 알고리듬으로도 구현할 수 있다.

📄너비 우선 탐색(BFS)

시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법. 주변 정점 중에서 가장 오래된 것 부터 우선 방문하는 방법.(거리: 시작 정점으로부터의 경로 길이)

• 큐를 사용해서 주변 정점을 관리

📚그래프 순회 응용

📄위상 정렬

무사이클 방향 그래프에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것

• 깊이 우선 탐색(DFS)을 활용하여 구함

DFS를 수행하다가 더 이상 주변 정점이 없어서 되돌아갈 때, 스택에서 삭제되는 정점을 역순으로 나열하면 된다.

📄그래프의 연결성

정점간의 연결 관계를 다루는 것

• 연결 성분

무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프. 너비 우선 탐색 또는 깊이 우선 탐색을 활용하여 구한다.

모든 정점을 탐색할 때까지 다음과 같은 과정을 반복한다. 탐색을 수행하다가 큐나 스택이 비게되면 그때까지 탐색한 정점들을 하나의 연결 성분으로 구성한다.

• 강연결 성분

방향 그래프에서 임의의 두 정점 사이에 양방향 경로가 존재하는 최대 부분 그래프. DFS를 활용하여 구한다.

1. DFS를 적용하여 정점의 방문 완료 순서(방문 순서의 역순)를 구한다.
2. 기존의 방향 그래프의 모든 간선들의 방향을 바꾼 새로운 그래프를 구한다.
3. 모든 간선들의 방향이 바뀐 그래프에 대해 방문 완료 번호가 큰 것부터 DFS를 수행하여 갈 수 있는 정점들의 각 리스트가 강연결 성분이 된다.