6. Graph (1)

그래프(Graph)

정점(Vertex, Node) 과 간선(Edge) 으로 이루어진 관계 구조
즉, 객체들(정점) 사이의 연결 관계(간선) 를 표현하는데 사용됨

G = (V, E)

• V: 정점(Vertex)의 집합
• E: 정점 쌍의 집합 (간선)

예를 들어

정점 V = {A, B, C, D}
간선 E = {(A,B), (A,C), (B,D), (C,D)}

 

시각화하면 다음과 같음:

   A
  / \
 B---C
  \ /
   D

---

Types of Graphs 종류

 

종류	설명	예시
무방향 그래프	간선에 방향이 없음 (A–B = B–A)	친구 관계
방향 그래프 (Digraph)	간선에 방향이 있음 (A→B ≠ B→A)	팔로우 관계
가중치 그래프	간선마다 가중치(거리, 비용 등)가 있음	지도, 네트워크
비가중치 그래프	단순히 연결만 표현	연결 관계
부분 그래프 (Subgraph)	그래프의 일부를 추출한 그래프
완전 그래프 (Complete Graph)	모든 정점 쌍이 직접 연결
연결 그래프 (Connected Graph)	모든 정점이 경로로 연결됨

---

Terminologies (용어 정리)

 

용어	설명
정점(Vertex)	데이터를 담는 그래프의 기본 단위
간선(Edge)	정점 간의 연결선
차수(Degree)	한 정점에 연결된 간선의 개수
경로(Path)	간선을 따라 이동하는 정점의 순서
사이클(Cycle)	시작점과 끝점이 같은 경로
연결 요소(Connected Component)	서로 연결된 정점들의 집합
단절점(Articulation Point)	제거 시 그래프가 분리되는 정점
이중 연결 요소(Biconnected Component)	단절점 없이 연결된 부분 그래프

---

 

Graph Representation (그래프 표현 방식)

그래프는 메모리에서 어떻게 연결 관계를 표현하느냐에 따라 여러 방식이 있음.

 

(1) 인접 행렬 (Adjacency Matrix)

2차원 배열로 정점 간의 연결 관계를 저장.

장점	단점
간선 존재 여부를 O(1)에 확인 가능	간선이 적을 때 메모리 낭비 심함

int adj[5][5] = {
  {0,1,1,0,0},
  {1,0,1,1,0},
  {1,1,0,0,1},
  {0,1,0,0,1},
  {0,0,1,1,0}
};

 

(2) 인접 리스트 (Adjacency List)

각 정점마다 연결된 정점들의 리스트를 따로 관리.

장점	단점
메모리 효율적 (희소 그래프에 유리)	특정 간선 존재 여부 확인은 O(V) 필요

vector<int> adj[5];
adj[0] = {1, 2};
adj[1] = {0, 2, 3};
adj[2] = {0, 1, 4};

 

---

Graph Traversal (그래프 탐색)

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

DFS는 한 경로를 끝까지 탐색한 후 되돌아오는 방식.
재귀 호출 또는 스택으로 구현

void DFS(int v, bool visited[], vector<int> adj[]) {
    visited[v] = true;
    printf("%d ", v);
    for (int next : adj[v])
        if (!visited[next])
            DFS(next, visited, adj);
}

 

 

• 특징: 깊이 중심 탐색, 재귀 구조
• 트리 구조와 유사하며, 깊게 파고드는 탐색에 적합.
• 예: 경로 탐색, 사이클 탐지, 위상 정렬

 

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

BFS는 가까운 정점부터 차례로 탐색하는 방식.
큐(Queue)를 이용해 구현

void BFS(int start, bool visited[], vector<int> adj[]) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        printf("%d ", v);

        for (int next : adj[v])
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
    }
}

 

• 특징: 거리(단계) 기반 탐색
• 최단 경로 탐색에 유용함.
• 예: 네트워크 탐색, 최단 거리 계산.

---

Finding Spanning Trees using DFS and BFS

그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프.
즉, 최소한의 간선으로 모든 정점을 연결한 트리 구조임.

• 정점이 V개이면, 간선은 항상 V - 1개
• 하나의 그래프에는 여러 신장 트리가 존재할 수 있음

 - DFS/BFS를 이용한 신장 트리 찾기

그래프를 DFS나 BFS로 탐색하면서,

새로운 정점을 처음 방문할 때 사용하는 간선만 저장하면

그 자체가 신장 트리(Spanning Tree)가 됨.

void spanningTreeDFS(int v, bool visited[], vector<int> adj[]) {
    visited[v] = true;
    for (int next : adj[v]) {
        if (!visited[next]) {
            printf("(%d, %d)\n", v, next); // 트리 간선 출력
            spanningTreeDFS(next, visited, adj);
        }
    }
}

• 이렇게 얻은 트리는 DFS Spanning Tree 또는 BFS Spanning Tree라고 부름.

---

Determining Biconnected Components (이중 연결 요소)

이중 연결 요소(Biconnected Component, BCC)는

어떤 한 정점을 제거해도 그래프가 분리되지 않는 부분 그래프를 말함.

= 그래프의 "안정적인 연결 단위"

즉, 그래프의 ‘끊김 없는 부분’을 찾는 과정

 

단절점(Articulation Point)

: 특정 정점을 제거했을 때 그래프가 두 개 이상의 부분으로 나뉜다면 그 정점을 단절점(Articulation Point) 이라 함.

 

단절점(Articulation Point) 찾기

1. DFS로 그래프를 탐색하며 각 정점의 발견 시간(discovery time)과 가장 빨리 도달할 수 있는 조상(low value) 을 기록함.
2. 어떤 정점 u에 대해, v가 u의 자식이고 low[v] ≥ disc[u]라면 u는 단절점이 됨.
3. 단절점을 기준으로 그래프가 분리되며 각각이 이중 연결 요소를 형성함.

 

예를 들면,

A
| \
B  C
|   \
D----E

여기서 A를 제거하면 그래프가 두 부분으로 분리됨 → A는 단절점
{A, B, D} 와 {A, C, E} 가 각각 하나의 BCC