[자료구조] 그래프(Graph)의 구현

그래프 (graph)

 - 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多관계를 가지는 원소를 표현하기 위한 자료구조

 - 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합

 ☞ G = (V, E)

    ㄴ V : 그래프에 있는 정점들의 집합

    ㄴ E : 정점을 연결하는 간선들의 집합

 - 인접, 부속

    ㄴ 그래프에서 두 정점 Vi와 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다고 표현

    ㄴ 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 표현

 - 차수(degree)

    ㄴ 무방향 그래프의 Vn정점의 차수 = Vn정점에 부속되어 있는 간선 수

    ㄴ 방향 그래프의 Vn정점의 차수 = Vn정점으로 진입하는 간선 수 + Vn정점에서 진출하는 간선 수

                                               = 진입 차수(in-degree) + 진출 차수(out-degree)

                                               = Vn정점을 머리로 하는 간선 수 + Vn정점을 꼬리로 하는 간선 수

 - 경로(path) : 그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 것.

 - 경로 길이(path length) : 경로를 구성하는 간선의 수

 - 단순 경로(simple path) : 모두 다른 정점으로 구성된 경로

 - 사이클(cycle) : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

 - DAG(directed acyclic graph) : 방향 그래프이면서 사이클이 없는 그래프

 - 연결 그래프(connected graph) : 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프(= 떨어져 있는 정점이 없는 그래프)

 - 트리 = 사이클이 없는 연결 그래프

---

그래프의 종류

 - 무방향 그래프(undirected graph)

    ㄴ 두 정점을 연결하는 간선의 방향이 없는 그래프

    ㄴ 정점 Vi와 정점 Vj를 연결하는 간선 = (Vi, Vj) = (Vj, Vi)  ☜ ★무방향 그래프에서만 같은 의미, 무방향 = 소괄호★

- 방향 그래프(directed graph), 다이 그래프(digraph)

    ㄴ 간선이 방향을 가지고 있는 그래프

    ㄴ 정점 Vi에서 정점 Vj를 연결하는 간선 = Vi → Vj = <Vi(꼬리), Vj(머리)> (≠ < Vj, Vi>)

 - 완전 그래프(complete graph)

    ㄴ 각 정점에서 다른 모든 정점을 연결하여 최대의 간선 수를 가진 그래프

    ㄴ 정점이 n개인 무방향 그래프에서 최대 간선 수 = n(n-1)/2

    ㄴ 정점이 n개인 방향 그래프에서 최대 간선 수 = n(n-1)

 - 부분 그래프(subgraph)

    ㄴ 원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프

    ㄴ 그래프 G와 부분 그래프 G'의 관계 = V(G') ⊆ V(G), E(G') ⊆ E(G)

 - 가중 그래프(weight graph), 네트워크(network)

    ㄴ 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프

---

인접행렬(adjacent matrix)

 - 행렬에 대한 2차원 배열을 사용하는 순차 자료구조

 - 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장

    ㄴ n개의 정점을 가진 그래프 : n X n 정방행렬

    ㄴ 행렬의 행 번호와 열 번호 : 그래프의 정점

    ㄴ 행렬 값 : 두 정점이 인접되어 있으면 1, 인접되어 있지 않으면 0

 - 무방향 그래프의 인접 행렬

    ㄴ 행 i의 합 = 열 i의 합 = 정점 i의 차수

 - 방향 그래프의 인접 행렬

    ㄴ 행 i의 합 = 정점 i의 진출 차수

    ㄴ 열 i의 합 = 정점 i의 진입 차수

 - 단점

    ㄴ n개의 정점을 가지는 그래프를 항상 n X n개의 메모리를 사용하기 때문에 정점의 개수에 비해 간선의 개수가 적은 희소 그래프에 대한 인접 행렬이 희소 행렬이 되므로 메모리 낭비가 발생