인접리스트의 구조, 구현, 복잡도까지

그래프 이론에서 인접리스트(Adjacency List)의 개념과 정의

인접리스트(Adjacency List)란, 그래프의 정점 간 연결 관계를 표현하기 위한 자료구조로, 각 정점이 연결된 다른 정점들의 리스트를 개별적으로 유지하는 방식입니다.

이는 희소 그래프(Sparse Graph) 즉, 간선의 수가 적은 그래프에서 특히 유리한 표현 방식으로, 메모리 공간의 효율성과 탐색 효율성을 동시에 고려한 구조입니다.

인접리스트의 기본 구조 정의

• 그래프에 정점이 V개 존재할 때, **크기가 V인 배열(또는 리스트)**을 생성합니다.
• 각 인덱스 i는 정점 i를 의미하며, 그 위치에는 정점 i와 연결된 정점들의 리스트가 저장됩니다.

예: 정점 0과 연결된 정점이 1, 3이면 → adj[0] = [1, 3]

• 리스트의 구현 방식은 배열, 연결 리스트, 동적 리스트(vector 등) 모두 가능합니다.

---

인접리스트의 메모리 구조와 구현 방식 분석

인접리스트의 메모리 저장 원리

• 인접리스트는 연결된 정점만 저장하므로, 메모리 낭비가 없습니다.
• 방향 그래프는 연결된 방향만 저장, 무방향 그래프는 양방향으로 모두 저장
• 가중치 그래프의 경우 (노드, 가중치) 쌍으로 저장

vector<int> adj[100]; // 무가중치 방향 그래프
vector<pair<int, int>> adj[100]; // 가중치 그래프

공간 복잡도 분석

• 공간 복잡도: O(V + E)
  • V: 정점 수 (리스트 배열 크기)
  • E: 간선 수 (리스트 내부 요소 수)
• 인접행렬이 O(V²)였던 것과 비교해, 희소 그래프에서 메모리 절약이 크다는 장점이 있습니다.

---

인접리스트 기반 그래프 연산의 시간복잡도 분석

연산 종류	시간복잡도	설명
간선 추가	O(1) (vector push_back 기준)	해당 정점 리스트에 삽입
간선 제거	O(degree(v))	해당 리스트에서 탐색 후 삭제
간선 존재 확인	O(degree(v))	리스트 순회 필요
인접 정점 탐색	O(degree(v))	리스트 순회
전체 정점 순회	O(V + E)	모든 리스트 순회 필요

degree(v)는 정점 v와 연결된 간선 수

---

방향 그래프, 무방향 그래프, 가중치 그래프에서의 인접리스트 구성 방식

무방향 그래프에서의 인접리스트 구성

• 양방향으로 간선을 저장해야 하므로, 각 간선을 두 번 추가합니다.

adj[u].push_back(v);
adj[v].push_back(u);

방향 그래프에서의 인접리스트 구성

• 한 방향만 저장하므로, 간선 수가 줄어듭니다.

adj[u].push_back(v); // u → v

가중치 그래프에서의 인접리스트 구성

• 각 연결 정보를 pair(정점, 가중치) 형태로 저장합니다.

vector<pair<int, int>> adj[100]; // pair<next_node, weight>

---

인접리스트의 장점과 단점에 대한 상세 분석

인접리스트의 주요 장점

1. 희소 그래프에 적합한 공간 효율성
   → 간선 수가 적을수록 공간 절약 효과가 큼
2. 정점 간 연결 정보가 선형적으로만 저장됨
   → 인접 정점 탐색이 빠르고 직관적임
3. 유연한 자료구조로 구현 가능
   → 배열, vector, 연결 리스트 등 다양한 형태로 확장 가능
4. 동적 그래프에 유리
   → 정점 추가, 간선 추가에 유연하게 대처 가능

---

인접리스트의 주요 단점

1. 간선 존재 여부 확인이 느림
   → 연결된 정점 리스트를 선형 탐색해야 하므로 O(degree(v)) 시간 소요
2. 정점 전체 간선 정보를 한번에 파악하기 어려움
   → 2차원 배열보다 직관성은 낮음
3. 인접행렬 대비 연산 단순성이 떨어짐
   → 리스트 순회, 삭제, 정렬 등 추가 연산이 필요할 수 있음

---

인접리스트와 인접행렬의 차이점 비교 요약

항목	인접리스트	인접행렬
공간 복잡도	O(V + E)	O(V²)
간선 존재 확인	O(degree(v))	O(1)
간선 추가	O(1)	O(1)
인접 정점 탐색	O(degree(v))	O(V)
구현 복잡도	중간 (동적 자료구조 필요)	낮음 (배열만 사용)
희소 그래프 적합성	매우 높음	낮음

 

---

면접 대비: 인접리스트 관련 자주 묻는 질문과 설명 팁

질문설명 포인트

질문	설명 포인
인접리스트란 무엇인가요?	정점별로 연결된 정점 정보를 리스트로 저장하는 그래프 표현 방식입니다.
인접행렬과 비교해 어떤 상황에서 유리한가요?	간선 수가 적은 그래프에서 메모리와 탐색 효율성이 뛰어납니다.
간선 확인이 왜 O(degree(v))인가요?	리스트를 순회하며 비교해야 하므로 선형 시간 소요됩니다.
가중치 그래프에서의 인접리스트 구성 방식은?	연결 정점을 (노드, 가중치) 쌍으로 저장합니다.
동적 정점 추가에 유리한 이유는 무엇인가요?	배열이나 리스트 확장에 유연하며 전체 구조 변경이 필요 없습니다.

 

---

요약

• 인접리스트는 그래프의 각 정점이 연결된 정점 목록을 따로 저장하는 효율적인 표현 방식입니다.
• 공간복잡도는 O(V + E)로, 간선 수가 적은 희소 그래프에서 매우 유리합니다.
• 각 정점의 인접 정점을 리스트 순회로 탐색하며, 구현은 배열, vector, 연결 리스트 등으로 다양하게 할 수 있습니다.
• 인접행렬보다 메모리를 적게 쓰지만, 간선 탐색이 느리고 구현 복잡도가 다소 높은 단점도 존재합니다.
• 면접에서는 자료구조 선택 기준, 공간/시간 복잡도 분석, 실제 구현 전략까지 깊이 있게 설명할 수 있어야 합니다.