10. 그래프

 

 

💡 1분 핵심 요약 (TL;DR)

• ✅ 그래프(Graph) — 정점(Vertex)과 간선(Edge)의 집합 G = (V, E), 복잡한 객체 관계를 표현
• ✅ 주요 용어 — 인접 정점, 정점의 차수(무방향: 합=간선×2, 방향: 진입/진출차수), 경로, 단순경로, 사이클
• ✅ 그래프 종류 — 무방향/방향/가중치/완전/연결/트리 그래프 등 11가지
• ✅ 구현 방법 — 인접 행렬(2차원 배열, 0/1) vs 인접 리스트(연결 리스트)
• ✅ 탐색 알고리즘 — DFS(깊이 우선, 스택 기반) vs BFS(너비 우선, 큐 기반)

 

 

 

01 그래프(Graph)란?

요소들이 서로 복잡하게 연결된 관계를 표현하는 자료구조

 

그래프는 정점(Vertex, 노드)과 간선(Edge, 링크)의 집합으로 구성되는 자료구조다. 수학적으로는 G = (V, E)로 표시하며, V(G)는 정점들의 집합, E(G)는 간선들의 집합을 의미한다.

 

분야	그래프 활용 예
교통	지하철 노선도 — 역(정점)과 연결 구간(간선)으로 표현
SNS	인맥 지도 — 사람(정점)과 친구 관계(간선)로 표현
지도	최단 경로 탐색 — 도시(정점)와 도로(간선)로 표현
전기회로	회로도 — 소자(정점)와 연결선(간선)으로 구조 분석

 

 

📜 그래프의 역사 — 오일러 다리 문제

 

📖 쾨니히스베르크의 다리 문제
수학자 오일러(Euler)는 "모든 다리를 한 번씩만 건너서 출발 장소로 돌아올 수 있는가"라는 문제를 그래프 이론으로 풀었다.
· 위치(육지) → 정점(Vertex)
· 다리 → 간선(Edge)

오일러는 모든 정점에 연결된 간선의 수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명했다.

 

 

 

02 그래프의 핵심 용어

그래프를 읽고 쓰려면 반드시 알아야 할 개념들

 

 

용어	정의	예시 (그래프 G1 기준)
인접 정점 (adjacent vertex)	간선으로 직접 연결된 정점	정점 1의 인접 정점 → 0, 2
정점의 차수 (degree)	정점에 연결된 간선의 수 무방향: 모든 차수 합 = 간선 수 × 2	G1에서 정점 0의 차수 = 3
진입/진출 차수 (in/out-degree)	방향 그래프 전용 · 진입(in): 들어오는 간선 수 · 진출(out): 나가는 간선 수 진입차수 합 = 진출차수 합 = 전체 간선 수	G2에서 정점 1 진입 차수 = 1, 진출 차수 = 2
경로 (path)	간선을 따라 갈 수 있는 길 (정점의 나열로 표시)	0→1→2→3 ✅ 경로 0→1→3→2 ❌ (간선 1-3 없음)
단순 경로 (simple path)	처음과 마지막을 제외하고 중복되는 정점이 없는 경로 ※ 간선이 중복되지 않는 경로는 트레일(Trail)이라 구별함	1→0→2→3 ✅ 단순경로 (정점 중복 없음) 1→0→2→0 ❌ (정점 0이 두 번 등장)
사이클 (cycle)	단순 경로의 시작과 끝이 같은 경로	0→1→2→0 ✅ 사이클

 

 

 

03 그래프의 종류 (11가지)

각 그래프의 특징과 표기법을 그림과 함께 이해하기

 

① 무방향 그래프 (Undirected Graph)

 

📖 정의
간선에 방향이 없는 그래프. 하나의 간선은 양방향으로 이동 가능하다.
· 간선 (A, B) 와 (B, A) 는 동일한 간선
· 표기 : (A, B)

 

 

② 방향 그래프 (Directed Graph / Digraph)

 

📖 정의
간선에 방향(화살표)이 있는 그래프. 일방통행 도로처럼 한 방향으로만 이동 가능.
· <A, B> 와 <B, A> 는 서로 다른 간선
· 표기 : <A, B> (A에서 B로만 이동 가능)

 

 

③ 가중치 그래프 (Weighted Graph / Network)

 

📖 정의
간선에 비용(가중치)가 할당된 그래프. 연결 유무뿐 아니라 연결의 강도도 표현 가능.
· 정점 : 도시 / 간선 : 도로 / 가중치 : 도로의 길이
· 활용 : 최단 경로, 통신망 비용, 회로 소자 용량 등

 

 

④ 부분 그래프 (Subgraph)

 

📖 정의
원래 그래프 G의 정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진 그래프.
원본 그래프에서 일부 정점·간선만 선택해 만든 작은 그래프다.

 

 

⑤ 다중 그래프 (Multigraph)

 

📖 정의
두 정점 사이에 간선이 여러 개 존재하거나, 자기 자신으로 돌아오는 루프(loop)가 있는 그래프.
· 같은 정점을 연결하는 간선이 2개 이상 가능
· 루프 : 간선의 시작 정점 = 끝 정점

 

 

⑥ 정규 그래프 (Regular Graph)

 

📖 정의
모든 정점이 같은 차수(degree)를 갖는 그래프.
예) 모든 정점의 차수가 3인 그래프 → 3-정규 그래프(3-regular graph)

 

 

⑦ 완전 그래프 (Complete Graph)

 

📖 정의
모든 정점 쌍 사이에 간선이 존재하는 그래프.
· 무방향 완전 그래프 (정점 수 = n) : 간선의 수 = n(n-1)/2
  → 예) 정점 4개 → 간선 6개, 정점 5개 → 간선 10개
· 방향 완전 그래프 (정점 수 = n) : 간선의 수 = n(n-1)
  → 왕복 간선이 모두 존재하므로 무방향의 정확히 2배

 

 

⑧ 동형 그래프 (Isomorphic Graph)

 

📖 정의
두 그래프 사이에 정점의 수, 간선의 수, 각 정점의 차수가 모두 같은 그래프.
생김새는 달라 보여도 구조적으로 동일한 그래프다.

 

 

⑨ 해밀턴 그래프 & 오일러 그래프

 

해밀턴 그래프 · 동일 정점을 두 번 이상 지나지 않고 · 시작 정점 = 끝 정점인 경로가 존재 · 즉, 모든 정점을 단 한 번씩만 방문하고 돌아옴

오일러 그래프 · 해밀턴 그래프이면서 · 모든 정점의 차수가 짝수인 그래프 · 즉, 모든 간선을 한 번씩 통과하고 돌아옴

 

⑩ 연결 그래프 (Connected Graph)

 

📖 정의
모든 정점 쌍에 대한 경로가 존재하는 그래프. 어떤 정점에서도 다른 정점으로 반드시 도달할 수 있다.
· 연결 그래프 : 떨어진(고립된) 정점이 없음
· 비연결 그래프 : 경로가 없는 정점 쌍이 존재

 

 

⑪ 트리 그래프 (Tree Graph)

 

📖 정의
그래프의 특수한 형태로, 사이클이 없는 연결 그래프.
· 트리는 그래프의 일종이지만, 사이클이 없어 계층 구조 표현에 적합
· n개의 정점을 가진 트리는 항상 n-1개의 간선을 가짐

 

 

 

 

04 그래프의 구현 방법

인접 행렬 vs 인접 리스트 — 언제 무엇을 쓸까?

 

① 인접 행렬 (Adjacency Matrix)

 

📖 개념
그래프를 n×n 2차원 배열로 표현. 정점 i와 j 사이에 간선이 있으면 1, 없으면 0으로 표기.
· 무방향 그래프 → 인접 행렬이 대칭 행렬 (상위/하위 삼각만 저장하면 메모리 절약)
· 방향 그래프 → 인접 행렬이 일반적으로 비대칭
· 가중치 그래프 → 0/1 대신 가중치 값 저장 (간선 없음은 별도 처리 필요)

 

 

② 인접 리스트 (Adjacency List)

 

📖 개념
각 정점에 인접한 정점들을 연결 리스트로 표현.
· 각 정점은 헤더 포인터(배열)를 가지며, 그 정점과 연결된 정점들을 연결 리스트로 이음
· 연결 리스트 노드는 데이터 필드 + 포인터 필드로 구성
· 마지막 노드의 포인터 필드는 NULL로 처리
· 리스트 내 순서는 무관

 

 

③ 인접 행렬 vs 인접 리스트 비교

 

항목	인접 행렬	인접 리스트
자료구조	2차원 배열	배열 + 연결 리스트
공간 복잡도	O(V²) — 정점 수에 비례 간선이 적어도 n² 공간 필요 (낭비)	O(V + E) — 정점+간선 수에 비례 간선이 적으면 공간 절약
간선 확인	O(1) — 배열 인덱스로 즉시 확인	O(degree) — 리스트 순회 필요
적합한 경우	밀집 그래프 (간선이 많을 때)	희소 그래프 (간선이 적을 때)

 

 

 

05 그래프 탐색 — DFS vs BFS

그래프의 모든 정점을 체계적으로 방문하는 두 가지 방법

 

깊이 우선 탐색 (DFS) Depth First Search · 사용 자료구조 : 스택(Stack) · 한 방향으로 갈 수 있을 때까지 계속 탐색 · 막히면 가장 가까운 갈림길로 백트래킹 · 방문한 정점은 반드시 방문 표시 · 미로 탐색 방식과 유사

너비 우선 탐색 (BFS) Breadth First Search · 사용 자료구조 : 큐(Queue) · 시작 정점에서 가까운 정점 먼저 방문 · 멀리 있는 정점은 나중에 방문 · 방문 시마다 인접 정점을 큐에 삽입 · 최단 경로 탐색에 적합

 

DFS 탐색 흐름

 

① 시작 정점 방문 방문 표시 후 스택에 Push

→

② 인접 정점 탐색 미방문 인접 정점 으로 이동 후 반복

→

③ 막힌 경우 인접 미방문 없음 → 스택 Pop (되돌아감)

→

④ 반복 종료 스택이 빌 때까지 ②③ 반복

 

✓ C언어에서 DFS는 재귀 함수로 구현하는 경우가 많다
스택 자료구조를 직접 구현해서 DFS를 만들 수도 있지만, C언어에서는 함수 호출 자체가 내부적으로 스택 메모리(콜 스택)를 사용한다. 따라서 재귀 함수(Recursive Function)를 이용하면 스택을 직접 구현하지 않고도 DFS를 매우 간결하게 표현할 수 있다.

재귀 DFS의 핵심 구조 : 정점 방문 → 방문 표시 → 미방문 인접 정점에 대해 DFS 재귀 호출
단, 재귀 깊이가 매우 깊어지면 스택 오버플로우(Stack Overflow)가 발생할 수 있으므로 주의가 필요하다.

 

BFS 탐색 흐름

 

① 시작 정점 방문 방문 표시 후 큐에 Enqueue

→

② 큐에서 꺼내기 Dequeue한 정점의 인접 정점 확인

→

③ 인접 정점 삽입 미방문 인접 정점 큐에 Enqueue

→

④ 반복 종료 큐가 빌 때까지 ②③ 반복

 

 

 

 

📌 핵심 정리

· 그래프 : G = (V, E), 정점(Vertex)과 간선(Edge)의 집합으로 복잡한 관계 표현
· 인접 정점 : 간선으로 직접 연결된 정점 / 차수 : 연결된 간선 수 (무방향: 합=간선×2)
· 경로→단순경로→사이클 : 간선 따라 이동 → 중복 정점 없음(처음·끝 제외) → 시작=끝
· 주요 그래프 종류 : 무방향(A,B) / 방향<A,B> / 가중치(비용 포함) / 완전(n(n-1)/2개 간선) / 연결(모든 정점 도달 가능) / 트리(사이클 없는 연결 그래프)
· 인접 행렬 : n×n 배열, 간선 확인 O(1), 무방향이면 대칭
· 인접 리스트 : 헤더 배열+연결 리스트, 희소 그래프에 메모리 효율적
· DFS : 스택, 깊게 파고들다 막히면 백트래킹 / BFS : 큐, 가까운 정점부터 순서대로

 

 

태그 : 그래프란그래프 종류그래프 용어 정리인접행렬 인접리스트 차이DFS BFS 차이깊이우선탐색너비우선탐색완전그래프 간선수자료구조 그래프오일러 해밀턴 그래프