연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 !
연결할 객체를 나타내는 정점 (Vertex)와 간선(Edge)의 집합으로 구성됨
그래프의 종류
무방향 그래프
- 두 정점을 연결하는 간선에 방향이 없는 그래프
- (Vi, Vj)와 (Vj, Vi)는 같은 간선
방향 그래프
- 간선에 방향이 있는 그래프로, 다이그래프(Digraph) 라고도 함
- (Vi, Vj)와 (Vj, Vi)는 다른 간선
완전 그래프
- 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프
- 정점이 n개인 무방향 그래프 : 최대 간선 수가 n(n-1)/2개
- 방향 그래프 : 두 정점에 대해 방향이 다른 간선을 두 개 연결할 수 있으므로, 최대 간선 수는 무방향 그래프의 최대 간선 수보다 2배 많음 n(n-1)개가 됨
부분 그래프
- 원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프
가중 그래프
- 정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프, 네트워크(Network)라고도 함
그래프 관련 용어
차수(Degree)
- 정점에 연결된 간선의 개수
- 무방향 그래프: 정점에 연결된 전체 간선 수
- 방향 그래프:
- 진입 차수 (In-degree): 외부 정점에서 들어오는 간선 수
- 진출 차수 (Out-degree): 해당 정점에서 나가는 간선 수
경로(Path)
- 정점과 간선의 나열로, 한 정점에서 다른 정점으로 이동하는 순서
- 예: A → B → C
경로 길이(Path Length)
- 경로에 포함된 간선의 수
- 또는 가중치 그래프에서는 총 가중치의 합
단순 경로(Simple Path)
- 정점이나 간선이 반복되지 않는 경로
사이클(Cycle)
- 시작 정점과 끝 정점이 같고, 중간에 정점이나 간선이 반복되지 않는 경로
- 예: A → B → C → A
DAG(Directed Acyclic Graph)
- 방향성이 있으며 사이클이 없는 그래프
- 예: 작업 순서 그래프, 의존성 그래프
연결(Connected)
- 무방향 그래프에서 모든 정점이 하나의 경로로 연결되어 있을 경우
- 방향 그래프에서는 모든 정점 쌍 사이에 방향성을 고려한 경로가 존재하면 강하게 연결(strongly connected) 되었다고 함
간선(Edge)
- 무향 그래프(Undirected Graph)에서 두 정점을 연결
- 방향성이 없어, 정점 A와 정점 B를 연결하는 간선은 "A-B"나 "B-A"로 동일하게 표현됨
Arc
- 유향 그래프(Directed Graph)에서 두 정점을 연결
- 방향성이 있어, 정점 A에서 정점 B로의 Arc와, 정점 B에서 정점 A로의 Arc는 다르게 취급됨
그래프는 어떻게 구현할까? 🤔
그래프를 구현하기 위해서는 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 함
인접 행렬(Adjacency Matrix) : 순차 자료구조를 이용한 그래프의 구현
- 2차원 배열을 사용하여 정점 간 간선의 존재 여부 또는 가중치를 표현함
graph[i][j]가 1 (또는 가중치)이면 정점 i에서 j로 간선이 존재
특징
- 정점 수가 n일 때, n x n 정방 행렬을 사용
- 두 정점이 인접되어 있으면 정점을 나타내는 행과 열에 대한 행렬값을 1, 인접되어 있지 않으면 행렬값을 0으로 함
- 무방향 그래프에서는 <Vi, Vj>, <Vj, Vi>가 동일한 간선이므로 인접 행렬이 대각선을 중심으로 대칭
- 방향 그래프에서는 <Vi, Vj>, <Vj, Vi>가 서로 다른 간선이므로 인접 행렬이 대칭이 되지 않음
장점
- 구현이 간단하고, 두 정점 간 간선 존재 여부를 O(1) 시간에 확인 가능
- 행렬 연산이 필요한 알고리즘에 적합 (예: 플로이드 워샬)
단점
- 정점을 n개 가진 그래프를 n x n 인접 행렬로 표현하면 간선 개수에 상관없이 항상 n x n개 메모리를 사용
- 정점에 비해 간선 개수가 적은 희소 그래프는 인접 행렬이 희소행렬이 되므로 메모리 낭비 문제가 생길 수 있음
인접 리스트(Adjacency List) : 연결 자료구조를 이용한 그래프의 구현
- 각 정점마다 연결된 정점 목록(리스트) 을 따로 저장
- 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성됨
- 어떤 정점의 연결 리스트는 그 정점에 인접한 정점의 수만큼, 즉 그 정점의 차수만큼 노드가 연결되어 있음
- 리스트 내의 노드는 저장하는 정점에 대해 오름차순으로 연결함
- 정점에 대한 인접 리스트의 헤드 포인터는 정점 개수만큼 필요함
- 그래프는 정점의 집합이므로, 각 정점에 대한 헤드 포인터를 그룹으로 묶어서 포인터 배열로 구성함
- 정점이 n개이고 간선이 e개인 무방향 그래프에 대한 인접 리스트는 크기가 n인 헤드 포인터 배열이 필요하고 노드는 2e개 필요
- 일반적으로 딕셔너리나 배열 + 리스트의 형태로 구현
특징
- 정점 수가 n, 간선 수가 e일 때 메모리 사용량: O(n + e)
- 무방향 그래프는 간선 하나당 리스트에 2번 추가됨
장점
- 메모리 사용이 효율적 (희소 그래프에 적합)
- 특정 정점과 연결된 정점을 탐색할 때 빠름
단점
- 두 정점 간 연결 여부를 확인하려면 리스트를 순회해야 하므로 최악 O(n)
