그래프는 여러 개의 정점(Vertex)과 이를 연결하는 간선(Edge)으로 이루어진 구조다.
트리와 달리 그래프는 방향이 있을 수도 있고, 순환이 존재할 수도 있다.
용어
정점(노드) : 데이터가 저장되는 위치, 보통 번호 또는 이름으로 표현한다.
간선 : 정점과 정점을 연결하는 선. 간선은 방향 그래프에서 방향을 갖고 무방향 그래프에서는 방향 없이 연결만 표시한다.
인접 : 두 정점이 간선 하나로 직접 연결되어 있는 관계.
차수 : 정점에 연결된 간선의 개수.
방향 그래프일 경우
- 진입차수 : 들어오는 간선 수
- 진출차수 : 나가는 간선의 수
경로 : 정점을 따라 간선을 통해 이동하는 순서.
단순 경로 : 경로 중에 동일한 정점을 두 번 이상 방문하지 않는 경우.
순환(사이클) : 출발 정점과 도착 정점이 동일한 경우.
그래프의 종류
그래프는 간선에추가 정보비용, 거리, 시간, 무게가 붙어 있는지 여부에 따라 가중치 그래프와 비가중치 그래프로 나뉜다.
가충치 그래프
모든 간선의 비용이 동일한(=1) 그래프.
즉, 간선을 따라 이동하는 데 특별한 비용 차이가 없다.
간선에는 단순히 “연결되어 있음”만 표시된다.
특징
- 모든 간선의 값이 동일 → "한 칸 이동"으로 취급
- 최단 거리는 간선의 개수로 판단
- BFS(Breadth-First Search)로 최단 거리 계산 가능
adj = [
[], # 0 unused
[2, 3], # 1 → 2, 3
[1, 4], # 2 → 1, 4
[1], # 3 → 1
[2] # 4 → 2
]
비가충치 그래프
각 간선이 서로 다른 비용(weight)을 갖는 그래프.
간선에 “거리·시간·비용·에너지·무게” 같은 값이 함께 저장된다.
특징
- 모든 간선의 값이 동일 → 한 칸 이동으로 취급
- 최단 거리는 간선의 개수로 판단
- BFS로 최단 거리 계산 가능
int adj[5][5] = {0};
adj[1][2] = 7; // 1 → 2 비용 7
adj[1][3] = 3; // 1 → 3 비용 3
adj[2][4] = 2; // 2 → 4 비용 2
adj[3][4] = 5; // 3 → 4 비용 5
완전 그래프
완전 그래프는 모든 정점이 서로 직접 연결되어 있는 그래프를 말한다.
즉, 어떤 두 정점을 선택해도 반드시 하나의 간선이 존재한다.
단순 그래프
정점 사이에 중복 간선이 없고, 자기 자신으로 향하는 간선(루프)도 없는 그래프이다.
다중 그래프
정점 사이에 둘 이상 간선(중복 간선)이 존재할 수 있는 그래프
방향 그래프
간선에 방향이 있는 그래프.
무방향 그래프
간선에 방향이 있는 그래프.
연결 그래프
모든 정점이 서로 도달 가능한 그래프.
인접행렬과 인접리스트
그래프는 실제 구현 시 보통 인접 행렬 또는 인접 리스트 방식으로 다룬다.
인접행렬
정점 수가 V일 때, V × V 크기의 2차원 배열을 사용한다.
- matrix[a][b] == 1 → 정점 a에서 b로 간선이 존재
- 무방향 그래프는 matrix[a][b] == matrix[b][a]
- 가중치 그래프는 1 대신 가중치(weight) 저장
인접행렬 무방향 그래프 코드(C)
#include <stdio.h>
int main() {
int V = 4;
// 정점 개수: 4개 (1,2,3,4 사용)
int adj[5][5] = {0};
// 인접 행렬 사용 (5x5이지만 0번은 사용 안 함)
// 1이면 연결됨, 0이면 연결 안 됨
// 그래프 종류: 무방향 그래프
// 구현 방식: 인접 행렬
// 간선 설정 (무방향이므로 양쪽 모두 1)
adj[1][2] = 1; adj[2][1] = 1;
adj[1][3] = 1; adj[3][1] = 1;
adj[2][4] = 1; adj[4][2] = 1;
adj[3][4] = 1; adj[4][3] = 1;
adj[2][3] = 1; adj[3][2] = 1;
printf("인접 행렬:\n");
// 인접 행렬 출력
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
printf("%d ", adj[i][j]);
}
printf("\n");
}
return 0;
}*출처 : ChatGPT
인접행렬 방향 그래프 코드(C)
#include <stdio.h>
int main() {
int V = 4;
// 정점 개수: 4개
int adj[5][5] = {0};
// 인접 행렬 (1~4 사용, 0은 버림)
// 방향 그래프이므로 한쪽만 1로 표시
// 간선 추가 (방향 있음)
adj[1][2] = 1; // 1 → 2
adj[1][3] = 1; // 1 → 3
adj[2][4] = 1; // 2 → 4
adj[3][2] = 1; // 3 → 2
adj[4][1] = 1; // 4 → 1
printf("방향 그래프 인접 행렬:\n");
// 인접 행렬 출력
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
printf("%d ", adj[i][j]);
}
printf("\n");
}
return 0;
}*출처 : ChatGPT
인접행렬 장점
특정 간선 존재 여부 확인이 쉽다 0(1)
다루기에 단순하다.
인접행렬 단점
공간 복잡도 0(v) (정점이 많을수록 비효율적이다)
모든 정점을 사용하지 않으면 공간 낭비
인접리스트
각 정점에서 갈 수 있는 정점 목록을 “리스트 구조”로 저장한다.
인접리스트 무방향 그래프 코드(Py)
# 정점 개수
V = 4
# 인접 리스트 (1~4 정점 사용)
adj = [[] for _ in range(V + 1)]
# 간선 목록 (무방향 그래프)
edges = [
(1, 2),
(1, 3),
(2, 4),
(3, 4),
(2, 3),
]
# 인접 리스트 구성
for a, b in edges:
adj[a].append(b) # a와 b 연결
adj[b].append(a) # 무방향이므로 반대도 연결
# 출력
print("인접 리스트:")
for i in range(1, V + 1):
print(f"{i}: {adj[i]}")*출처 : ChatGPT
인접리스트 방향 그래프 코드(Py)
# 정점 개수
V = 4
# 인접 리스트 초기화
adj = [[] for _ in range(V + 1)]
# 방향 그래프 간선
edges = [
(1, 2),
(1, 3),
(2, 4),
(3, 4),
(3, 2),
]
# 인접 리스트 구성 (방향!)
for a, b in edges:
adj[a].append(b) # 한쪽 방향만 추가
# 출력
print("방향 그래프 인접 리스트:")
for i in range(1, V + 1):
print(f"{i}: {adj[i]}")*출처 : ChatGPT
인접 행렬 장점
메모리를 필요한 만큼만 사용할 수 있다. → O(V+E)
연결된 간선 순회가 효율적이다.
인접 행렬 단점
특정 간선 (a,b) 존재 확인은 느리다. — O(V)
구현이 다소 복잡하다.
정점·간선의 집합 표현
V(G) = {a, b, c}
E(G) = {(a, b), (a, c), (b, c)}
입력으로 이런 형태가 들어오면
실제 구현에서는 인접 행렬이나 인접 리스트로 전환하여 사용한다.