8강 그래프 (1) - 방통대, 알고리즘

학습개요

이번 강의에서는 그래프와 관련된 기본 개념(정의, 종류, 용어, 구현 방법)을 우선 살펴본 후, 그래프에 대한 기본 연산으로 사용되는 그래프 순회 방법을 학습한다. 또한 그래프 순회를 활용해서 위상 정렬, 연결 성분, 강연결 성분을 구하는 방법에 대해서도 함께 살펴본다.

학습목표

• 그래프의 개념, 주요 용어 그리고 구현 방법을 이해할 수 있다.
• 그래프의 순회 방법으로 깊이 우선 탐색과 너비 우선 탐색을 이해하고 적용할 수 있다.
• 그래프 순회 방법을 적용하여 위상 정렬, 연결 성분, 강연결 성분을 구할 수 있다.

주요용어

• 그래프(graph)
• - 연결할 객체를 나타내는 정점(vertex)의 집합과 정점을 연결하는 간선(edge)의 집합으로 구성된 비선형 자료구조
• 인접 행렬(adjacency matrix)
• - 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 2차원 배열 A=(n×n)으로 표현하는 방법
• 인접 리스트(adjacency list)
• - 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 n개의 연결 리스트로 표현하는 방법으로, 각 연결 리스트는 임의의 정점 u에 대해서 인접한 모든 정점을 표현함
• 그래프 순회(graph traversal)
• - 그래프의 모든 정점을 체계적으로 한 번씩 방문하는 방법으로, 깊이 우선 탐색과 너비 우선 탐색이 있음
• 깊이 우선 탐색(depth first search)- 최근의 주변 정점을 우선으로 탐색하는 방법
• - 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색하는 방법
• 너비 우선 탐색(breadth first search)- 주변 정점 중에서 가장 오래된 것부터 우선 방문하는 방법
• - 시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법
• 위상 정렬(topological sort)
• - 무사이클 방향 그래프에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것
• 연결 성분(connected component)
• - 주어진 무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프
• 강연결 성분(strongly connected component)
• - 주어진 방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래프

정리하기

📌 그래프 기본 개념

그래프 G = (V, E)

• 정점 집합 V와 간선 집합 E로 구성됨
• 그래프 종류
  • 무방향 그래프 / 방향 그래프
  • 가중 그래프 (간선에 가중치 존재)

주요 용어

• 인접(Adjacent): 두 정점이 간선으로 직접 연결됨
• 부수(Incidence): 정점과 간선이 연결됨
• 부분 그래프(Subgraph): 전체 그래프의 일부
• 경로(Path): 정점을 순서대로 따라가는 길
• 경로의 길이: 포함된 간선의 개수
• 차수(Degree)
  • 진입 차수 (In-degree)
  • 진출 차수 (Out-degree)
• 단순 경로: 정점을 중복 없이 지나는 경로
• 사이클 (Cycle): 시작점과 끝점이 같은 단순 경로
• 루프 (Loop): 정점이 자기 자신과 연결된 간선
• 연결 (Connected): 무방향 그래프에서 모든 정점이 연결
• 강하게 연결 (Strongly Connected): 방향 그래프에서 모든 정점 쌍이 양방향으로 연결
• 약하게 연결 (Weakly Connected): 방향 무시 시 연결됨

---

🛠 그래프 구현 방법

✅ 인접 행렬 (Adjacency Matrix)

• |V| × |V| 크기의 2차원 배열
• 간선 유무를 0 또는 1 (또는 가중치 값)으로 표현
• 장점: 간선 존재 여부를 O(1)에 확인 가능
• 단점: 메모리 낭비 가능 → 조밀한 그래프에 적합

✅ 인접 리스트 (Adjacency List)

• 각 정점마다 연결된 정점 리스트 보유
• 연결 리스트 혹은 동적 배열로 표현
• 장점: 메모리 효율 좋음 → 성긴 그래프에 적합
• 단점: 특정 간선 존재 여부 확인 시 느릴 수 있음

---

🔍 그래프 순회 (Traversal)

🔸 깊이 우선 탐색 (DFS: Depth-First Search)

• 가능한 깊게 들어간 후, 더 이상 갈 곳 없으면 되돌아감
• 스택 (또는 재귀) 사용
• 시간복잡도
  • 인접 리스트: O(|V| + |E|)
  • 인접 행렬: O(|V|²)

🔸 너비 우선 탐색 (BFS: Breadth-First Search)

• 시작 정점 기준으로 가까운 정점부터 순서대로 탐색
• 큐 사용
• 시간복잡도
  • 인접 리스트: O(|V| + |E|)
  • 인접 행렬: O(|V|²)

---

🌟 그래프 순회의 응용

🔸 위상 정렬 (Topological Sort)

• *방향 비순환 그래프(DAG)**에서 정점을 순서대로 나열
• DFS 종료 후 역순으로 나열
• 순서: DFS → 되돌아갈 때 스택에 쌓은 순서 반대로 출력

🔸 연결 성분 (Connected Components)

• 무방향 그래프에서 경로로 연결된 정점 집합
• DFS/BFS 수행 중 큐나 스택이 빌 때까지 탐색한 정점 = 하나의 성분
• 미방문 정점이 남을 때까지 반복

🔸 강연결 성분 (Strongly Connected Components)

• 방향 그래프에서 모든 정점 쌍이 서로 도달 가능한 최대 집합
• 알고리즘 순서:
  1. DFS → 방문 종료 시간 기준 역순 스택 생성
  2. 그래프의 간선 방향을 뒤집은 전치 그래프(GR) 생성
  3. GR에서 스택의 순서대로 DFS 수행 → 결과가 강연결 성분

---

1. 기본개념

그래프라는 G → G=(V,E)

V:(vertex) 정점의 집합, E:(edge)간선의 집합

이들의 차이를 보면 간선에 방향에 대한 차이점이 있다 이를통해 무방향 그래프와 방향그래프로 분류한다

여기에 각 비용을 더한 가중그래프 까지해서 3종류가 존재한다

표기는 V (G_2) = {1, 2, 3, 4, 5} G_3{ (1, 2), (1,4), (2,5), (3,5) }

모든 무방향 그래프는 트리로 구성될 수 있다

다음과 같은 조건을 가진다

1. 무방향
2. 모든 정점 연결
3. 사이클이 없어야 한다

그래프 주요 용어 정리

1. 인접(Adjacent)과 부수(Incident)

• 인접(Adjacent): 두 정점 u, v 사이에 간선이 있으면 정점 u와 v는 인접한다고 한다.
• 부수(Incident): 간선이 특정 정점에 연결되어 있을 때, 그 간선은 해당 정점에 부수되었다고 한다.
• 예시: 정점 A와 B 사이에 간선 e가 있다면, A와 B는 인접하고, 간선 e는 정점 A와 B에 부수된다.

2. 부분 그래프(Subgraph)

• 정의: 원래 그래프 G = (V, E)에서 일부 정점과 간선을 선택하여 만든 그래프
• 조건: 부분 그래프의 모든 간선의 양 끝점이 선택된 정점 집합에 포함되어야 함
• 유도 부분 그래프(Induced Subgraph): 특정 정점 집합을 선택했을 때, 그 정점들 사이의 모든 간선을 포함하는 부분 그래프

3. 경로(Path)

• 정의: 그래프에서 정점 v₀부터 정점 vₙ까지의 경로란 간선들의 연결된 순서
• 표현: v₀ → v₁ → v₂ → ... → vₙ
• 경로의 길이: 경로상에 있는 간선의 개su
• 예시: A-B-C-D는 길이 3인 경로

4. 차수(Degree)

• 무방향 그래프에서의 차수: 해당 정점에 부수된 간선의 수
• 방향 그래프에서의 차수:
  • 진입차수(In-degree): 정점으로 들어오는 간선의 수
  • 진출차수(Out-degree): 정점에서 나가는 간선의 수
• 핸드셰이킹 정리: 모든 정점의 차수의 합 = 2 × 간선의 수

5. 단순 경로(Simple Path)

• 정의: 한 경로상에서 처음과 마지막 정점을 제외한 모든 정점이 서로 다른 경로
• 특징: 같은 정점을 두 번 이상 방문하지 않음 (시작점과 끝점 제외)
• 예시: A-B-C-D (모든 중간 정점이 다름)

6. 사이클(Cycle)

• 정의: 처음과 마지막 정점이 같은 단순 경로
• 루프(Loop): 사이클이면서 경로의 길이가 1인 경우 (자기 자신으로 돌아오는 간선)
• 단순 사이클: 시작점을 제외하고 모든 정점이 서로 다른 사이클
• 예시: A-B-C-A (길이 3인 사이클)

7. 연결(Connected)

• 연결된 정점: 무방향 그래프에서 서로 다른 두 정점 사이에 경로가 존재할 때
• 연결된 그래프: 그래프의 모든 정점 쌍이 연결되어 있는 그래프
• 연결 성분(Connected Component): 최대 연결된 부분 그래프
• 강연결(Strongly Connected): 방향 그래프에서 모든 정점 쌍에 대해 양방향 경로가 존재

8. 추가 중요 용어들

트리(Tree)

• 정의: 연결되어 있고 사이클이 없는 무방향 그래프
• 특징: n개의 정점을 가진 트리는 정확히 (n-1)개의 간선을 가짐

완전 그래프(Complete Graph)

• 정의: 모든 정점이 서로 인접한 그래프
• 표기: Kₙ (n개의 정점을 가진 완전 그래프)
• 간선 수: n(n-1)/2

이분 그래프(Bipartite Graph)

• 정의: 정점 집합을 두 개의 분리된 집합으로 나눌 수 있고, 각 집합 내부의 정점들 사이에는 간선이 없는 그래프

평면 그래프(Planar Graph)

• 정의: 간선들이 교차하지 않도록 평면에 그릴 수 있는 그래프

오일러 경로와 해밀턴 경로

• 오일러 경로: 모든 간선을 정확히 한 번씩 지나는 경로
• 해밀턴 경로: 모든 정점을 정확히 한 번씩 방문하는 경로

그래프 구현

인접행렬과 인접리스트로 나눌 수 있다 아래사진을 보자

한눈에 봐도 알수있을만큼 쉽다 이해가 안간다면 한번 수기로 작성해보길 바랍니다.

2. 그래프 순회

그래프 순회란?

그래프의 모든 정점을 체계적으로 한 번 씩 방문하는 것

순회방법

• 깊이 우선 탐색 DFS Depth First Search
• 너비 우선 탐색 BFS Breadth First Search

탐색 과정에서의 정점 구분

• 방문 정점
  • 방문이 완료된 정점
• 📌 주변 정점
  • 방문 정점에 인접한 정점 중에서 아직 방문하지 않은 정점
• 미도달 정점
  • 방문 정점도 주변 정접도 아닌 전혀 접근하지 못한 정점

여기서 주변 정점을 주의깊게 보자

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

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

깊이 우선 탐색

한 정점을 시작으로 매번 인접한 정점 중 한곳으로 이동하며 탐색하는 방법

• 최근의 주변 정점을 우선으로 방문하는 탐색 방법

스택 구조를 사용해서 구현

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

위의 사진을 보면 A→B→C→D까지 탐색이 완료되어 더 이상 탐색할 것이 없다면, 다시 C로 돌아온 후 인접 정점을 탐색하고 상위 정점으로 올라가는 방식이라고 생각하면 된다.

반응형

깊이 우선 탐색

처리과정

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

이중 인접한 2,3,4 중 아무거나 하나를 선택 예제에서는 2를 선택

top이 이제 2가됐으니 2의 주변중점을 확인 이미 스택에 있는곳은 방문할 수 없음

이미 방문한 곳들밖에없어 갈 곳이 없다면 pop을 하여 top을 돌림

이런식으로 방문한 정점과 사용된 간선으로 구성하는 트리가 깊이우선 트리이다

깊이 우선 탐색의 성능과 특징

너비우선 탐색

시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법

“거리” → 시작 정점으로 경로의 길이 주변 정점 중에서 가장 오래된 것부터 우선 방문하는 방법

큐를 사용하여 주변 정점을 관리

너비 우선 탐색 예시

똑같이 시작 정점 1로 시작

방문을 했다면 큐에서 삭제 이후 큐는 스택과 다르게 하나만 스택에 넣는것이 아닌 주변 정점 모두를 스택에 할당함

이후 앞에서부터 top을 제거 후 주변정점 확인

3. 그래프 순회의 응용

위상정렬

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

깊이 우선 탐색을 활용하여 구함

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

그래프의 연결 관계를 다루는 것

• 연결성분
  • 임의의 두 정점간의 경로가 존재하는 그래프 - (무방향 그래프)
    • 너비 우선 탑색 깊이 우선 탐색을 활용하여 구함
    • 탐색을 하다가 큐/스택이 비게 되면 그때까지 탐색한 정점들을 하나의 연결 성분으로 구성

• 강연결성분
  • 두 임의의 정점이 있으면 양방향의 경로가 존재하는 최대 부분 그래프 - (방향그래프)

정점 (1 → 2 → 5 → 3) → (4) → (6) 강연결 끼리 묶음

즉, 방문 순서에 따라:

• 첫 번째: 정점 1
• 두 번째: 정점 2
• 세 번째: 정점 5
• 네 번째: 정점 3
• 간선이 없음으로 다시 첫번째: 정점 4
• 두번째: 정점 6

이를 후위 순서(finishing time)로 표현하기 위해 탐색 완료 순서를 역순으로 뒤집습니다.

왼쪽 강연결부터

• 마지막으로 완료된 정점(정점 3) → 후위 순서 1
• 다섯 번째로 완료된 정점(정점 5) → 후위 순서 2
• 네 번째로 완료된 정점(정점 2) → 후위 순서 3
• 세 번째로 완료된 정점(정점 1) → 후위 순서 4
• 두 번째로 완료된 정점(정점 6) → 후위 순서 5
• 첫 번째로 완료된 정점(정점 4) → 후위 순서 6

 

간선의 방향을 바꿈 G^R 이라고부름

숫자가 큰거부터 떼내어 보면 강연결 성분이 이뤄진다 사진에서는 4, 6, 부터 떼어져 나갔다