Graph

Graph란?
그래프는 비선형적 자료구조입니다. 그래프는 데이터를 담는 정점과 정점들을 연결하는 간선으로 구성되며 객체(정점) 간의 관계를 표현할 수 있습니다.
용어
- 연결(Incident): 정점과 간선 사이의 관계를 나타내는 용어로 간선이 정점에 연결되어 있다고 말합니다.
- 인접(Adjacent): 정점 사이의 관계를 나타내는 용어로 두 정점이 동일한 간선에 연결되어 있다면 두 정점이 인접해 있다고 말합니다.
- 유향 그래프(Directed Graph): 방향성이 있는 간선들로 이루어진 그래프를 말합니다.
- 무향 그래프(Undirected Graph): 방향성이 없는 간선들로 이루어진 그래프를 말합니다.
- 가중치 그래프(Weighted Graph): 그래프를 구성하는 간선에 가중치가 존재하는 그래프를 말합니다.
- 정점의 차수(Degree): 무향 그래프에서 정점 V 와 인접한 정점의 수를 정점 V 의 차수라고 합니다.
- 진입 차수(In-Degree): 유향 그래프에서 다른 정점에서 정점 V 로 향하는 방향을 가진 간선의 수를 정점 V 의 진입 차수라고 합니다.
- 진출 차수(Out-Degree): 유향 그래프에서 정점 V 에서 다른 정점으로 향하는 방향을 가진 간선의 수를 정점 V 의 진출 차수라고 합니다.
- 경로(Path): 한 정점에서 다른 한 정점으로 향하는 연속된 간선들의 Sequence를 말합니다. Path 중에서 한 번 방문한 정점은 다시 방문하지 않는 경로를 Simple Path라고 합니다.
- 도달 가능(Reachable): 정점 V 에서 정점 W 로의 경로가 존재하는 경우 정점 W 는 정점 V 에서 도달 가능하다라고 합니다.
- Connected Graph: 모든 정점 사이의 경로가 존재하는 그래프를 말합니다. 유향 그래프에서 모든 정점 사이의 경로가 존재하는 그래프는 특별히 Strongly Connected Graph라고 합니다.
- Cycle: 출발 정점과 도착 정점이 같은 경로를 Cycle이라고 합니다. Cycle이 없는 그래프는 Acyclic Graph라고 합니다.
그래프의 구현

인접 리스트

인접 리스트는 각 정점에 인접한 정점들을 리스트에 저장하여 그래프를 구현하는 방식입니다.
인접 행렬

인접 행렬은 2차원 배열로 그래프를 구현하는 방식입니다. 2차원 배열의 각 원소는 두 정점이 인접한지 여부 혹은 두 정점을 연결하는 간선의 가중치를 나타냅니다.
비교
| 인접 리스트 | 인접 행렬 |
---|
메모리 | O(E) | O(V^2) |
areAdjacent(x, y) | O(min(degree(x), degree(y)) | O(1) |
incidentEdges(x) | O(degree(x)) | O(V) |
그래프 순회

그래프의 순회란 어떤 한 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문하는 것을 말합니다.
DFS (Depht First Search)
- A -> B -> D -> G -> E -> H -> C -> F
- 모든 정점과 간선의 방문 여부 초기화
- 그래프 속 한 정점 V에 대해 DFS 호출
- DFS의 대상이 된 정점 방문
- V와 연결된 간선을 찾고 각 간선의 flag가 unexplored인지 확인
- unexplored라면 건너편 정점 W의 flag 확인
- W를 방문하지 않았다면 정점 W에 대해 DFS 호출
- W를 이미 방문했다면 해당 간선의 flag를 back으로 변경
- 그래프의 모든 정점이 처리될 때까지 3번부터 위 과정 반복
BFS (Breath First Search)
- A -> B -> C -> D -> E -> F -> G -> H
- 모든 정점과 간선의 방문 여부 초기화
- 그래프 속 한 정점을 queue에 삽입하면서 방문 처리
- queue의 front에 있는 정점 V를 꺼내 V와 연결된 간선을 찾음
- 각 간선의 flag가 unexplored인지 확인 후 건너편 정점 W의 방문 여부 확인
- 방문하지 않았다면 queue에 삽입하면서 방문 처리
- 이미 방문했다면 해당 간선의 flag를 back으로 변경
- 그래프의 모든 정점이 처리될 때까지 3번부터 위 과정 반복
시간복잡도
DFS와 BFS 모두 인접 리스트로 구현한 경우엔 O(V + E) 시간복잡도를 갖고 인접 행렬로 구현한 경우엔 O(V^2) 시간복잡도를 갖습니다.