그래프란?(Computer Science) bfs, dfs, scc, dag

1. 먼저 그래프란 뭘까?

개체들과 개체들의 일대일 관계를 수학적으로 나타내는 표현 방법이다. 

2. 그래프의 종류에는 이렇게 크게 세가지 정도가 있다.

1. 희소 그래프 (Sparse Graph): 간선의 수가 정점 수에 비해 상대적으로 적은 그래프.
2. 완전 그래프 (Complete Graph): 모든 정점이 서로 간선으로 연결된 그래프.
3. 밀집 그래프 (Dense Graph): 간선의 수가 정점 수에 비해 상대적으로 많은 그래프.

3. 그리고 그래프의 기본 알고리즘은  bfs, dfs가 있는데 이를 응용한 알고리즘이 존재한다.

BFS (Breadth-First Search)

BFS는 그래프의 모든 정점을 층층이 탐색하는 알고리즘입니다. 큐(Queue)를 사용하여 시작 정점에서 가까운 정점부터 탐색한다.

일반적인 bfs 코드

알고리즘 과정

1. 시작 정점을 큐에 삽입하고 방문 표시.
2. 큐에서 정점을 꺼내고, 해당 정점과 연결된 모든 인접 정점을 방문하지 않았다면 큐에 삽입.
3. 큐가 빌 때까지 반복.

응용

1. 최단 경로 탐색 (Shortest Path)
   • BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용됩니다.
   • 응용: 네트워크 전송 경로 계산, 미로 문제.
2. 다익스트라 알고리즘 (Dijkstra’s Algorithm)
   • BFS의 아이디어를 확장하여, 가중치가 있는 그래프에서 최단 경로를 탐색.
     (우선순위 큐 사용으로 BFS와 차별화.)
3. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
   • BFS와 비슷한 접근을 사용하여 음수 가중치를 포함한 그래프의 최단 경로 계산.
4. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
   • BFS는 그래프의 연결 관계를 초기화하는 데 도움을 줄 수 있으며, 모든 쌍 최단 경로를 계산.

 

 

---

DFS (Depth-First Search)

DFS는 그래프의 한 방향으로 끝까지 탐색한 후, 다시 되돌아가며 탐색을 이어가는 알고리즘입니다. 스택(Stack)을 사용하거나 재귀적으로 구현된다.

일반적으로 아래와 같은 형식을 가진다.

그리고 저기서 왜 Stack이 안 쓰이고 재귀가 쓰이냐는 의문이 생길 수 있는데(내가 처음에 그랬다.)

재귀 함수를 돌리면 스택처럼 함수가 쌓이기 때문이다.

알고리즘 과정

1. 시작 정점을 방문하고 스택에 삽입.
2. 인접 정점을 탐색하여 방문하지 않은 정점이 있으면 이동.
3. 더 이상 방문할 정점이 없으면 스택에서 꺼냄.
4. 스택이 빌 때까지 반복.

그림으로 보기

오른쪽 하단에 있는 스택처럼 저렇게 쌓인다.

응용

1. 스패닝 트리 (Spanning Tree)
   • DFS로 그래프를 탐색하며 최소 연결 트리를 생성.
2. 연결 요소 (Connected Components, CC)
   • DFS를 사용하여 그래프의 모든 연결 요소를 찾을 수 있음.
     응용: 네트워크의 클러스터 분리.
3. 이중 연결 요소 (Biconnected Components, BCC)
   • DFS 기반 탐색으로 그래프에서 단절점(Articulation Point)이나 단절 간선(Bridge)을 찾아 분리.
4. 강한 연결 요소 (Strongly Connected Components, SCC)
   • 방향 그래프에서 각 노드가 다른 노드로 도달 가능한 구성 요소를 탐색.
     예: 타잔 알고리즘(Tarjan’s Algorithm), 코사라주 알고리즘(Kosaraju’s Algorithm).

SCC 알고리즘

SCC 알고리즘만 자세히 설명해보겠다.

SCC는 Strong Connected Component인데 한국말로는 강한 연결 성분이다.

즉, 방향 그래프에서 모든 정점이 서로 도달 가능한 부분 그래프(서브그래프)를 의미한다.

사이클을 이루는 작은 소집합?

SCC를 이해하기 위해선 

1. pre visit/post visit

2. type of edge

3. dag(directed acyclic graph)

이 세가지의 개념의 이해가 필요하다.

 

1. pre visit/post visit

Previsit이란 어떤 node를 처음 방문하는 이벤트를 의미한다.

반대로 postvisit이란 어떤 node를 최종적으로 떠나는 이벤트를 의미한다.

 

만약 1번 노드부터 작은 노드를 우선으로 DFS를 돌렸다고 치면 1-2-4-3-5-6 이렇게 방문이 될 것이다.

여기서 방문하면 pre, 떠나면 post에 각각 넘버링을 해준다. 이 넘버링은 어떻게 하냐?

그냥 DFS 돌리는 코드에 clock과 같은 전역변수를 하나 추가해서 계속 갱신하게 해주면 된다.

 

2. type of edge

pre와 post의 관계를 통해서 edge의 type을 알 수 있게 된다.

tree edge -> parent - child를 연결

forward edge -> ancestor – (non-child) descendant를 연결

back edge -> descendant - ancestor를 연결

cross edge -> 아무 관계도 아닌 vertex를 연결

 

간단히 DFS의 정방향 edge라면 tree/forward, 역방향 edge라면 back, 횡방향 edge하면 cross라고 이해하면 된다.

 

3. dag

비순환 방향 그래프이다. 즉 cycle이 없다는 것이다.

 

cycle이란?

이렇게 자기 자신으로 돌아 오는 것이다.

 

비순환 방향 그래프는 source와 sink를 가진다.

source: 나가는 edge만 있는 vertex

예) 2

sink: 들어오는 edge만 있는 vertex

예) 5, 6

예시 그래프

 

dag는 아래와 같은 성질을 가진다.

• 성질 1: DFS에서 Back Edge가 발견되면 사이클이 존재하며, DAG에는 Back Edge가 없다.
• 성질 2: DAG의 모든 간선은 항상 더 낮은 Post 번호를 가진 정점으로 연결된다.
• 성질 3: 모든 DAG에는 최소 하나의 Source와 Sink가 존재한다.

 

 

4. 그래프의 표현방법

컴퓨터는 그림으로 그래프를 이해할 수 없다. 그러므로 컴퓨터가 이해하는 방식으로 말해줘야한다.

 

SCC (Strongly Connected Components) 알고리즘

유향 그래프의 SCC(강한 연결 요소)를 찾는 대표적인 알고리즘은 아래와 같이 세가지가 있다.

코사라주(Kosaraju's Algorithm),    타잔(Tarjan's Algorithm),   가보우(Gabow's Algorithm)

• 요약
  1. 성질 1: DFS는 시작 정점에서 도달 가능한 모든 정점을 탐색한 후 종료된다.
  2. 성질 2: 가장 높은 post 번호를 가진 정점은 소스 SCC에 속한다.
  3. 성질 3: SCC C→SCC C′ 간선이 존재하면, SCC C의 최고 post 번호는 SCC C′보다 크다.

 

그래프 표현 방식

1. Adjacency Matrix (인접 행렬)
   • 그래프를 2D 행렬로 표현하며, 행과 열이 정점이고, 간선이 존재하면 1(또는 가중치), 없으면 0으로 나타냅니다.
   • 장점:
     • 간선 존재 여부를 O(1) 시간에 확인 가능.
   • 단점:
     • 메모리 사용량이 높음 (특히 희소 그래프의 경우).
2. Incidence Matrix (관계 행렬)
   • 정점과 간선을 기준으로, 행은 정점, 열은 간선을 나타냄. 간선이 연결된 정점에 1(또는 방향에 따라 -1)로 표시.
   • 장점:
     • 간선의 정보와 연결된 정점을 명확히 표현.
   • 단점:
     • 메모리 사용량이 많고, 구현이 복잡.
3. Adjacency List (인접 리스트)
   • 각 정점마다 연결된 정점 목록을 리스트로 저장.
   • 장점:
     • 희소 그래프에서 메모리 효율적.
   • 단점:
     • 간선 존재 여부를 확인하는 데 O(V) 시간이 걸림.
4. Edge List (간선 리스트)
   • 모든 간선을 리스트로 저장하며, 각 간선은 (출발 정점, 도착 정점)의 쌍으로 표현.
   • 장점:
     • 그래프 간선 정보를 직접적으로 활용 가능.
   • 단점:
     • 특정 정점의 인접 정점 탐색이 비효율적.
5. Paths (경로)
   • 특정 정점들 간의 경로를 나열하여 표현.
   • 장점:
     • 경로 기반 문제 해결에 직접 활용.
   • 단점:
     • 그래프 전체를 표현하는 데 적합하지 않음.

---

활용

• Adjacency Matrix: Dense Graph에서 활용 (플로이드-워셜 등).
• Adjacency List: Sparse Graph에서 활용 (DFS, BFS).
• Edge List: MST 알고리즘 (크루스칼 등).
• Paths: 경로 탐색 문제 (예: 최단 경로).

그래프를 **인접 행렬(Adjacency Matrix)**과 **인접 리스트(Adjacency List)**로 구현하는 것은 그래프의 구조와 성격에 따라 선택됩니다. 이 두 방법은 메모리 사용량, 시간 복잡도, 구현의 편의성 등에서 차이가 있습니다. 각각의 차이를 비교해 보겠습니다.

 

추가로 인접 행렬과 인접 리스트의 차이이다. 각 상황에 맞게 구현하면 된다.