그래프(Graph) — 자료구조와 개념

1. 그래프 개념

그래프는 **노드(Vertex, 정점)**와 **노드를 연결하는 간선(Edge)**으로 구성된 자료구조입니다. 노드들이 복잡하게 연결된 구조를 표현하는 데 적합합니다.

2. 구성 요소

• 정점(Vertex, Node): 그래프의 개별 객체
• 간선(Edge): 정점 간 연결 관계

• 방향성:

  • 무방향 그래프(Undirected Graph): 간선에 방향 없음
  • 방향 그래프(Directed Graph, Digraph): 간선에 방향 있음
• 가중치(Weight): 간선에 비용이나 거리 값을 부여할 수 있음

3. 표현 방법

• 인접 행렬(Adjacency Matrix)

  • 2차원 배열로 간선 존재 여부 또는 가중치 저장
  • 공간 복잡도: O(V²) (V는 정점 개수)
  • 간선 존재 여부 빠르게 확인 가능

• 인접 리스트(Adjacency List)

  • 각 정점에 연결된 정점 목록 저장
  • 공간 효율적, 특히 간선이 적은 경우 유리
  • 탐색 시 인접 노드 순회에 적합

4. 기본 연산 및 탐색

• DFS(Depth-First Search): 깊게 탐색하며 방문
• BFS(Breadth-First Search): 넓게 탐색하며 방문
• 최단 경로 알고리즘: 다익스트라, 벨만-포드, 플로이드-워셜 등
• 최소 신장 트리(MST): 크루스칼, 프림 알고리즘

5. 활용 사례

• 소셜 네트워크 연결 관계
• 도로, 통신망 경로 탐색
• 작업 스케줄링 (의존성 그래프)
• 추천 시스템, 게임 맵 탐색

6. 간단한 인접 리스트 구현 (Swift)

class Graph<T: Hashable> {
    private var adjacencyList: [T: [T]] = [:]
    
    func addVertex(_ vertex: T) {
        adjacencyList[vertex] = []
    }
    
    func addEdge(from: T, to: T, directed: Bool = false) {
        adjacencyList[from]?.append(to)
        if !directed {
            adjacencyList[to]?.append(from)
        }
    }
    
    func neighbors(of vertex: T) -> [T]? {
        return adjacencyList[vertex]
    }
}

7. 마무리

그래프는 복잡한 연결 관계를 나타내는 데 필수적이며, 컴퓨터 과학의 다양한 문제 해결에 사용됩니다. 자료구조와 알고리즘을 이해하면 효율적인 그래프 활용이 가능합니다.