그래프와 표현 방식
그래프 (Graph)와 표현 방식
그래프(Graph)는 정점(Vertex)과 그 정점들을 연결하는 간선(Edge)의 집합으로 이루어진 비선형 자료구조입니다. 현실 세계의 복잡한 관계(예: 소셜 네트워크, 지하철 노선도, 컴퓨터 네트워크)를 모델링하고 분석하는 데 매우 유용하게 사용됩니다.
📈 그래프의 주요 용어와 종류
- 주요 용어 (Terminology)
> * 정점 (Vertex / Node) : 데이터를 나타내는 개체 (도시, 사람 등). > * 간선 (Edge) : 정점 간의 관계를 나타내는 선 (도로, 친구 관계 등). > * 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점. > * 차수 (Degree) : 한 정점에 연결된 간선의 수. (방향 그래프에서는 진입/진출 차수로 나뉨) > * 경로 (Path) : 정점들을 순서대로 나열한 것. > * 사이클 (Cycle) : 시작 정점과 끝 정점이 같은 단순 경로.
- 종류 (Types)
> * 무방향 그래프 (Undirected Graph) : 간선에 방향이 없는 그래프. (A-B와 B-A가 같음) > * 방향 그래프 (Directed Graph) : 간선에 방향이 있는 그래프. (A→B와 B→A가 다름) > * 가중치 그래프 (Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프.
🛠️ 그래프의 표현 방식
메모리에 그래프를 표현하는 대표적인 두 가지 방식입니다.
- 인접 행렬 (Adjacency Matrix)
> * '방식': V x V 크기의 2차원 배열로 그래프를 표현. `matrix[i][j]`가 1(또는 가중치)이면 정점 i와 j 사이에 간선이 있음을 의미합니다. > * '장점': 두 정점 사이의 연결 여부를 O(1)의 빠른 속도로 확인할 수 있습니다. > * '단점': 정점 수(V)의 제곱에 비례하는 공간(O(V²))이 필요하여, 간선이 적은 '희소 그래프(Sparse Graph)'의 경우 메모리 낭비가 심합니다.
- 인접 리스트 (Adjacency List)
> * '방식': 각 정점마다 해당 정점과 연결된 다른 정점들의 리스트를 저장합니다. (배열이나 해시 테이블을 사용하여 각 정점의 리스트에 접근) > * '장점': 간선의 수(E)에 비례하는 공간(O(V+E))만 필요하여, 희소 그래프에서 메모리 효율이 좋습니다. > * '단점': 두 정점 사이의 연결 여부를 확인하려면 해당 정점의 리스트를 순회해야 하므로, 인접 행렬보다 시간이 더 걸릴 수 있습니다.
💡 개발자 핵심 Point
- 언제 무엇을 사용할까?
> * 인접 행렬 : 그래프에 간선이 많이 존재하는 '밀집 그래프(Dense Graph)'일 경우, 또는 두 정점의 연결 여부 확인이 빈번할 때 유리합니다. > * 인접 리스트 : 그래프에 간선이 적은 '희소 그래프(Sparse Graph)'일 경우, 또는 특정 정점의 모든 이웃을 찾는 작업이 빈번할 때 유리합니다. (대부분의 실제 문제에서는 희소 그래프가 많아 인접 리스트가 더 선호됩니다.)
- 그래프는 소셜 네트워크 분석, 내비게이션 경로 탐색, 네트워크 패킷 라우팅, 추천 시스템 등 현실 세계의 복잡한 관계를 모델링하고 문제를 해결하는 데 필수적인 자료구조입니다.
- 그래프를 다루기 위해서는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이라는 두 가지 기본 탐색 알고리즘을 반드시 이해해야 합니다. 이 두 탐색법은 그래프 관련 문제 해결의 시작점입니다.
