[Data Structure] 그래프의 정의와 표현

그래프

그래프의 정의

• 그래프 G(V, E): 어떤 자료나 개념을 표현하는 정점(Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료 구조
• 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다.
  • -> 같은 그래프라고 하더라도 여러 모양으로 그릴 수 있다

그래프의 종류

• 방향 그래프(directed graph, 유향 그래프): 각 간선이 '방향'이라는 속성을 갖는 그래프
• 무향 그래프(undirected graph): 간선에 방향이 없는 그래프
• 가중치 그래프(weighted graph): 각 간선에 가중치(weight)라 불리는 속성을 부여한 그래프
  • ex) 두 도시사이의 거리, 두 물건 사이의 교환 비율, 두 사람 사이의 호감도 등의 다양한 정보 표현하는 데 사용
  • 최소 스패닝 트리, 최단 경로 문제 등에서 중요하게 다룸
• 다중 그래프(multi graph): 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프
• 단순 그래프(simple graph): 두 정점 사이에 최대 한 개의 간선만 있는 그래프
• 루트 없는 트리(unrooted tree): 부모 자식 관계가 없을 뿐, 간선 들의 연결 관계만 보면 트리와 같은 무향 그래프
  • 간선들의 연결 관계가 트리와 같다는 말은, 간선을 통해 두 정점을 잇는 방법이 딱 하나 뿐이라는 의미
• 이분 그래프(bipartite graph): 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프
• 사이클 없는 방향 그래프(directed acyclic graph, DAG): 방향 그래프인데 사이클이 없는 그래프
  • 사이클(cycle): 한 점에서 출발해 자기 자신으로 돌아오는 경로
  • 여러 작업들 간의 상호 의존 관계 등을 그래프로 표현할 때 흔하게 출현
  • 간선의 방향을 무시할 경우 DAG에는 사이클이 존재할 수도 있다

그래프의 경로

• 겅료(path): 끝과 끝이 서로 연결된 간서들을 순서대로 나열한 것
• 단순 경로(simple path): 경로 중 한 정점을 최대 한 번만 지나는 경로로, 경로라고 하면 대부분 단순 경로를 의미
• 사이클(cycle): 시작한 점에서 끝나는 경로(= 시점과 종점이 같은 경로)

---

그래프의 표현 방법

그래프는 트리와 별다를 것이 없어서 매우 유사한 방식으로 구현이 가능하다. 하지만, 많은 경우 그래프는 트리에 비해 훨씬 정적인 용도로 사용되기 때문에 좀더 간단하고 메모리를 적게 차지하는 방법으로 구현하는 것이 일반적이다.

정적이라는 말은 새로운 정점이나 간선을 추가 & 삭제하는 일이 자주 일어나지 않는다는 의미

인접 리스트(adjacency list) 표현

• 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록 저장, 즉 각 정점마다 하나의 연결 리스트를 갖게 됨
  • -> graph[i]: 정점 i와 간선을 통해 연결된 정점들의 번호 저장 연결 리스트

ArrayList<Integer>[] graph;

• 간선이 추가적 속성을 갖는 그래프(ex. 가중치 그래프)인 경우
  • -> 간선의 정보 구조체로 표현

인접 행렬 표현

• |V|X|V| 크기의 행렬, 즉2차원 배열을 이용해 그래프의 간선 정보 저장
  • -> adj[i][j]: 정점 i에서 정점 j로 가는 간선이 있는지를 나타내는 불린 값 변수

boolean[][] graph;

• 간선이 추가적 속성을 갖는 그래프(ex. 가중치 그래프)인 경우
  • -> 각 간선의 정보를 불린 값이 아닌 정수나 실수 변수로 표현
  • -> 두 정점 사이에 간선이 없는 경우 -1 또는 아주 큰 값 등 존재할 수 없는 값으로 지정

인접 리스트 vs 인접 행렬

• 인접 행렬 표현
  • 두 정점 u, v가 주어질 때 간선(u, v)가 있는지 한 번의 배열 접근 adj[u][v]만으로 알 수 있음
  • |V|X|V| 크기의 2차원 배열 사용 -> 항상 O(|V|^2) 크기의 공간 사용
    • 노드가 3만 개가 넘으면 자바 힙 스페이스(java.heap.space) 에러가 발생
  • 하지만, 노드와 관련되어 있는 간선을 탐색하려면 N번 접근해야 한다
• 인접 리스트 표현
  • 두 정점 u, v가 주어질 때 간선(u, v)가 있는지 연결 리스트 adj[u]를 모두 확인해야 알 수 있음
  • |V|개의 연결 리스트에 실제 간선 수 |E| 만큼의 원소가 들어있다 -> O(|V| + |E|)의 공간 사용
    • 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러가 발생하지 않음
  • 인접 행렬에 비해 구현이 조금 복잡
  • 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어남

희소 그래프(sparse graph) ->  인접 리스트 표현

밀집 그래프(dense graph) -> 인접 행렬 표현

암시적 그래프 표현

입력이 직접적으로 그래프 형태를 띠지 않는 문제의 경우, 그래프의 구조를 직접 사용하지 않고도 문제를 해결할 수 있는 경우가 자주 있다.

• 미로에서 최단 경로 찾기
  • 주어진 입력을 그래프로 변환하는 번거로운 과정을 없앨 수 있음
• 그래프의 크기가 아주 큰데 실제로는 그중 일부만 사용하는 경우 ex) 15-퍼즐
  • 조각들의 배치 상태를 정점으로 하는 암시적 그래프 표현을 통해 그래프 전체를 메모리에 올리지 않고 문제를 풀 수 있음

그래프에 대해 복잡한 연산이나 알고리즘을 수행할 것이라면 번거롭더라도 입력을 미리 그래프 표현으로 바꿔 두는 것이 전체 코드를 간결하게 할 수 있다.