그래프는 어떻게 구현할까? 🤔

그래프를 구현하기 위해서는 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 함

인접 행렬(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)