[알고리즘] 8강 - 그래프(1)

✅ 1. 그래프 기본 개념

(1) 그래프란?

• 그래프: 정점(Vertex)의 집합(V)와 간선(Edag)의 집합(E) 로 구성이 되어있는 자료구조이다.
• 방향 그래프: <> 괄호로 표기를 하며, 양방향이면 두 가지 경우를 모두 기재함.
• 무방향 그래프: () 괄호로 표기를 하며, 방향이 없기 때문에 한 가지 경우만 기재함.
• 가중 그래프: 간선에 의미에 대한 값을 부여 할 수 있는데, 이 의미값을 가중치라고 하며, 가중치가 있는 그래프를 의미함.
• 트리는 그래프의 일종: 방향을 가지지않는 무방향이며, 모든 정점이 연결되며, 사이클이 존재하지 않는 그래프를 트리라함.

(2) 그래프 - 주요 용어

• 인접: 두 정점이 하나의 간선으로 직접 연결되어 있으면 두 정점은 인접하다 라고함. ( 정점과 정점 사이의 관계 )
• 부수: 두 정점 a, b가 간선 e로 연결되어 있을 때, 간선 e는 a 또는 b에 부수함과 동시에 a와 b에 부수함.
• 부분 그래프: 그래프 내부의 또 다른 그래프로 논리적으로 분리해서 보는 것이 부분 그래프이다. ( 예: 네비게이션 지도에서 현재 내가 원하는 경로의 정점과 선들을 보여주는데 이것이 부분 그래프로 볼 수 있음. )
• 경로: 정점 a에서 b까지 간선을 따라 이동할 수 있는 일련의 순서를 의미함. (예: v1 -> v2 -> v3)
• 경로의 길이: 경로를 구성하는 간선의 총 개수를 의미함. ( 정점이 3개인 경로라면 길이는 2가 될 수 있음. )
• 차수: 한 정점에 연결된 간선의 수를 의미함.
• 진입차수: 방향 그래프에서 해당 정점으로 들어오는 화살표의 개수를 의미함.
• 진출차수: 방향 그래프에서 해당 정점에서 나가는 화살표의 개수를 의미함.
• 단순 경로: 경로 중에서 똑같은 정점을 두 번 지나지 않는 경로를 의미하는데, 처음과 끝은 제외 대상임.
• 사이클: 시작 정점과 끝 정점이 같은 단순 경로로써 한 바퀴 돌아 제자리로 오는 형태로 보면 됨.
• 루프: 하나의 간선이 자기 자신(정점)으로 다시 돌아오는 형태를 의미함. 쉽게 말해, 곧장 자기 자신에게로 꽂히는 형태로 돼지 꼬리나 동그란 고리 모양의 간선처럼 생김.
• 강하게 연결: 방향 그래프에서 정점 사이의 간선이 왕복으로 서로 연결 된 경우 강하게 연결되었다고 함.
• 약하게 연결: 방향 그래프에서 정점 사이의 간선이 일방통행으로 한 방향으로만 연결되어 있는 경우 약하게 연결되었다고 함.

(3) 그래프 - 구현 방법

• 인접 행렬: 2차원 배열로 구현을 하는 방식임. ( 방향 그래프와 무방향 그래프 둘 다 표현 가능 )
• 인접 행렬에서 가중치 표현은 연결은 되어있지만 인접하지 않은 정점과는 무한으로 표현함.
• 인접 리스트: 연결 리스트로 구현을 하는 방식이며, 배열 요소 하나에 연결리스트가 들어있는 형태임.
• 인접 리스트에서 가중치 표현은 단순히 리스트의 각 노드를 하나씩 늘려 가중치 표현을 함.

---

✅ 2. 그래프 순회

(1) 그래프 순회란?

• 그래프 순회: 그래프의 모든 정점을 한 번씩만 방문하는 것을 그래프 순회라고 함.
• 대표적인 순회 방법은 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 가 존재함.

(2) 탐색 과정에서의 정점의 구분

• 방문 정점: 방문이 완료된 정점을 의미함.
• 주변 정점: 방문 정점에 인접한 정점 중에서 아직 방문하지 않은 정점을 의미함.
• 미도달 정점: 방문 정점도 주변 정점도 아닌 전혀 접근하지 못한 정점을 의미함.
• 깊이 우선 탐색: 현재 정점의 주변 정점(인접한 정점)을 우선 방문하는 방식
• 너비 우선 탐색: 현재 정점의 주변 정점(인접한 정점) 중에서 오래된 것을 우선 방문 하는 방식

(3) 깊이 우선 탐색 (DFS)

• 깊이 우선 탐색: 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색을 하는 방법
• 스택 구조를 사용해서 구현: 현재 정점에 인접한 정점이 없어 더 이상 탐색을 진행할 수 없으면, 거꾸로 되돌아가면서 아직 탐색하지 않은 인접한 정점을 찾아서 탐색을 진행하는데, 이 과정은 스택 구조를 활용해 구현 할 수 있음.

• (1) 시작 정점을 스택에 삽입하며, 방문 정점으로 처리를 진행
• (2) 방문 정점의 주변 정점(방문하지 않은 인접한 정점)을 발견하면 Stack에 push 한 뒤, push 한 주변 정점을 방문 정점으로 처리 한 뒤, 이어서 또 해당 방문 정점의 주변 정점을 push, 방문 처리 ... 반복
• (3) 만약 주변 정점이 더 이상 없다면 스택의 top 에 있는 정점을 제거하면 뒤로 돌아가게 되고 거기서 또 주변 정점을 찾아서 방문하며, 또 주변 정점이 없다면 스택의 top 에 있는 정점을 제거 과정도 반복함.
• (4) 스택에 더 이상의 정점이 없을 때까지 2의 과정 반복

(4) 깊이 우선 탐색 (DFS) - 예시

• 깊이 우선 탐색(DFS) 동작 과정: 시작 정점으로부터 시작해 주변 정점(방문하지 않은 인접한 정점)을 기준으로 정점을 Stack 에 쌓으며 방문을 진행하고, 더 이상 주변 정점이 존재하지 않는 정점까지 갔다면, Stack 에서 하나씩 꺼내면서 꺼낸 정점의 주변 정점을 확인하는 방법이다.
• 결국 Stack 이 NULL 인 경우가 모든 주변 정점을 방문한 결과로 볼 수 있음.

(5) 깊이 우선 탐색 (DFS) - 방문 순서

• 여러개의 방문 순서: 주변 정점(방문하지 않은 인접한 정점)이 많을 때 어떤 정점을 먼저 방문 하냐에 따라서 방문 순서가 제각각 다를 수 있음. ( 예: 위와 같이 10가지의 방문 순서에 대한 경우가 발생 할 수 있음. )

(6) 깊이 우선 탐색 (DFS) - 성능과 특징

• 순환 알고리즘: 재귀 호출 방식이 아닌, 순환 알고리즘으로도 구현이 가능함.

(7) 너비 우선 탐색 (BFS)

• 너비 우선 탐색(BFS): 시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문하는 그래프 탐색임.
• 큐를 사용하여 주변 정점을 관리함.

• (1) 시작 정점을 Queue 에 넣고 방문 처리를 진행
• (2) 방문 처리 된 시작 정점의 주변 정점을 모두 Queue 에 삽입. ( 삽입 순서에 따라 방문 순서가 달라 질 수 있음. )
• (3) Queue에 삽입 된 주변 정점 중 가장 먼저 삽입 된 정점을 방문 처리 후 해당 정점의 주변 정점을 모두 Queue 에 삽입.
• (4) 만약 주변 정점이 없는 경우 다시 Queue 맨 앞 정점을 방문 처리 후 주변 정점을 Queue 에 넣음.
• (5) 결과적으로 주변 정점이 없는 상태인 Queue 가 비어있는 상태가 된다면 탐색 완료로 간주함.

(8) 너비 우선 탐색 (BFS) - 예시

• 너비 우선 탐색(BFS) 는 위와 같이, Queue 에 주변 정점을 모두 넣고, Queue 에서 맨 앞 부분을 꺼내 방문 처리를 한 뒤, 이후에 방문 처리가 된 정점의 주변 정점을 Queue에 넣는 과정을 반복하는 탐색 알고리즘임.

(9) 너비 우선 탐색 (BFS) - 방문 순서

• 너비 우선 탐색(BFS) 방문 순서: 주변 정점을 Queue 에 넣을 때, 어떤 순서로 넣느냐에 따라서 방문 순서가 달라짐.
• 위의 그래프같은 경우는 방문하는 순서에 따라 24가지의 경우가 존재 할 수 있음.
• 너비 우선 탐색의 성능과 특징: 깊이 우선 탐색(DFS) 과 똑같음.

---

✅ 3. 그래프 순회와 응용

(1) 위상 정렬

• 깊이 우선 탐색(DFS) 순회 기술을 위상 정렬이라는 목적에 맞게 응용한 대표적인 사례가 위상 정렬임.

• 위상 정렬: 무사이클 방향 그래프에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것을 의미함.
• 쉽게 말해, 깊이 우선 탐색(DFS)를 수행하며, 주변 정점을 Stack 에 쌓게 되고, 만약 주변 정점이 없는 지점에 도달 한다면, Stack 에서 top 을 꺼내 배열의 맨 마지막 요소에 삽입을 하고, 다음 Stack top 에 해당하는 정점의 주변 정점이 존재하지 않는다면 동일하게 top 을 꺼내 배열의 맨 마지막 요소 앞에 삽입을 하고, 만약 주변 정점이 존재한다면, 주변 정점을 Stack에 쌓는 과정을 반복하며, 그래프를 정렬하는 것임.
• 위상 정렬 핵심: 본질적인 그래프 연결 구조는 변하지 않지만, 그래프의 구조(추상적인)를 배열의 인덱스 구조로 변경함으로써, 컴퓨터가 어떤 노드부터 처리를 해야하는지 정렬해서 알려주는 원리라고 보면 됨.
• 즉, 그래프 자체는 추상적인 개념으로 사람이 보기 편하게 만들어놓은 구조라 이걸 위상 정렬을 통해 컴퓨터에서 돌리는 느낌

(2) 위상 정렬 예시

• 위상 정렬 과정: 깊이 우선 탐색(DFS) 를 활용해 주변 정점을 Stack 에 쌓고, 주변 정점이 없을 때 Stack 에서 꺼내서 배열의 마지막 인덱스에서부터 차근차근 삽입을 진행하는 과정임.
• 결과적으로 위상 정렬은 그래프 구조를 배열로 만듦으로써 정렬을 시키는 것으로 볼 수 있음.

(3) 그래프의 연결성

• 그래프의 연결성: 정점 간의 연결 관계를 다루는 것으로 연결 성분, 

(4) 그래프의 연결성 - 연결 성분

• 연결 성분: 무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프를 의미한다.
• 쉽게 말해, 그래프 내에서 임의의 두 정점을 고르고, 그 두 정점이 연결되어 있을 때 모든 경로에 해당하는 부분 그래프를 하나의 연결 성분이라고 하는 것임. ( 연결 성분을 이루고 있으며, 연결 성분이 몇 개 존재한다는 느낌임. )
• 이러한 연결 성분은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 을 활용하여 구할 수 있음.

(5) 그래프의 연결성 - 강연결 성분

• 강연결 성분: 방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래프를 의미함.
• 인접한 정점 사이의 양방향이 존재하지 않더라도, 부분 그래프에서 임의의 정점 간의 연결이 이어지는 부분 그래프면 됨.
• 즉, 특정 정점 두 개가 왕복이 가능한가를 따지는 것임.
• 깊이 우선 탐색(DFS) 를 활용해서 강연결 성분을 구할 수 있음.

(5) 그래프의 연결성 - 강연결 성분 예시

• (1) 깊이 우선 탐색(DFS) 를 적용하여 정점의 방문 완료 순서를 역순으로 구하게 됨.
• (2) 그래프의 방향 간선을 모두 거꾸로 변환을 시켜주어 G^R = (V, E^R) 의 형태로 바꿔줌.
• (3) 거꾸로 된 방향 간선과 역순의 방향 완료 순서를 기반으로, 역순의 방향 완료 순서 중 가장 큰 수인 6부터 1까지 강연결인지 파악을 하게 된다면, 강연결 성분을 구할 수 있음.
• 즉, DFS 를 수행하여 갈 수 있는 정점들의 각 리스트가 강연결 성분이 될 수 있음.