[자료구조 Java] 비선형 자료구조 ① 그래프

비선형 자료구조란?

: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미

1. 그래프

: 정점과 간선으로 이루어진 자료 구조

- 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 할 때, '어떠한 곳'은 정점(Vertex)이고 '무언가'는 간선(Edge)가 됨

1-1. 관련 용어

- 방향 그래프, Directed Graph(Digraph): 간선에 방향성이 포함되어 있는 그래프

- 무방향 그래프, Undirected Graph: 간선에 방향성이 없는 그래프
- 인접 정점(adjacent vertext): 간선에 의해 직접 연결된 정점

- 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수(연결된 간선의 수)
                                         ▶︎ 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프 간선 수의 2배

- 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수라고도 함)

- 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외차수라고도 함)

                                      ▶︎ 방향 그래프에 있는 정점의 진입 차수와 진출 차수의 합 = 그래프 간선의 수

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

- 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경로

- 사이클(cycle): 단순 경로에서 시작 정점과 종료 정점이 동일한 경우를 의미

1-2. 그래프의 종류

1-2-1. 무방향 그래프와 방향 그래프

	무방향 그래프	방향 그래프
설명	간선을 통해 양방향으로 갈 수 있는 그래프	간선에 방향성이 존재하는 그래프

1-2-2. 가중치 그래프 (Weighted Graph)

- 간선에 비용이나 가중치가 할당된 그래프

- '네트워크'라고도 표현 (ex. 도시-도시간 연결, 도로의 길이, 회로 소자의 용량, 통신망 사용료 등)

1-2-3. 연결 그래프 VS 비연결 그래프

	연결 그래프(Connected Graph)	비연결 그래프(Disconnected Graph)
설명	무방향 그래프의 모든 정점쌍에 대해 항상 경로가 존재	무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않음

1-2-4. 순환 VS 비순환 그래프

	순환 그래프(Cycle Graph)	비순환 그래프(Acyclic Graph)
설명	단순 경로의 시작 정점과 종료 정점이 동일	사이클이 없는 그래프

1-2-5. 완전 그래프

- 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프

참고 사이트: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

1-3. 그래프의 구현

1-3-1. 인접 행렬(Adjacent matrix): 정방 행렬을 사용하는 방법

- 인접 행렬은 V*V Boolean Matrix로써 matrix[i][j] == true 라면 i -> j로 간선이 존재한다는 의미

  ▶︎ 해당하는 위치의 value 값을 통해 vertex 간의 연결 관계를 O(1)로 파악
- Edge 개수와 무관하게 V^2의 공간복잡도를 가짐

- 무방향 그래프를 인접 행렬료 표현하면 대칭행렬(Symmetric Matrix)가 됨

 

1-3-2. 인접 리스트(Adjacent list): 연결 리스트를 사용하는 방법

- 모든 정점을 인접 리스트에 저장, 즉 각각의 정점에 인접한 정점을 리스트로 모두 표시하는 것
-  Vertex간 연결을 확인하기 위해 모든 리스트를 확인해야 하므로 시간복잡도 증가

	인접 행렬	인접 리스트
장점	- 두 정점을 연결하는 간선 존재 여부를 즉시 알 수 있음 - 정점의 차수를 O(N) 안에 확인 가능	- 어떤 정점에 대한 인접 정점을 쉽게 찾을 수 있음 - 모든 간선의 수를 O(N+E) 안에 알 수 있음
단점	- 특정 인접 점점을 찾기 위해 모든 노드를 순회해야 함 - 그래프에 존재하는 모든 간선의 수를 찾는데 전체 행렬을 조사해야 하므로 O(N^2)의 시간 복잡도를 가짐	- 간선의 존재 여부와 정점 차수를 찾는 데 정점 차수만큼의 시간이 더 걸림
사용시 유리한 그래프	간선이 많이 존재하는 밀집 그래프(Dense Graph)	적은 숫자의 간선을 가지는 희소 그래프(Sparse Graph)

1-4. 그래프의 탐색

1-4-1. 깊이 우선 탐색 (DFS, Depth-First Search)

- 그래프 상에 존재하는 임의의 한 정점을 기준으로 하나의 인접 정점으로만 우선 나아감
- 연결할 수 있는 정점이 있을 때까지 진행하다가, 더 이상 연결되지 않으면 그 전 단계의 정점으로 돌아가 다른 인접정점을 탐색

- Stack을 활용하여 구현 가능하며, 모든 정점을 방문하고자 하는 경우 해당 방법 선택

 

1-4-2. 너비 우선 탐색 (BFS, Breadth-First Search)

- 그래프 상에 존재하는 임의의 한 정점을 기준으로 해당 정점(1차)에 연결 되어 있는 모든 정점(2차)을 우선 탐색
- 첫 번째 정점과 연결된 모든 정점(2차)을 하나씩 순회하며 이들과 연결된 인접 정점(3차)을 차례로 탐색
- Queue를 활용하여 정점의 순서를 기록하며, 두 정점 사이의 최단 경로 혹은 임의 경로를 찾고 싶을 때 사용