그래프
그래프
그래프는 정점과 간선으로 이루어진 객체 사이의 연결성을 표시하는 비선형 자료구조이다. 그래프 G는 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선의 집합을 의미한다.
그래프 용어
정점(Vertex)
객체를 의미한다. V(G)는 그래프의 정점의 집합을 의미한다.
간선(Edge)
객체를 연결하는 선이다. E(G)는 그래프의 간선의 집합을 의미한다.
인접(Adjacent)
정점 V1과 V2가 간선으로 연결되어 있으면 두 정점은 인접해 있다고 한다.
부속(Incident)
V1과 V2를 잇는 간선은 V1과 V2에 부속되어 있다고 한다.
차수(Degree)
정점에 부속되어 있는 간선의 수.
진입 차수(Indegree)
방향 그래프에서 특정 정점에 대해서 다른 정점에서 들어오는 간선의 개수.
진출 차수(Outdegree)
방향 그래프에서 특정 정점에서 다른 정점으로 나가는 간선의 개수.
그래프의 종류
무방향 그래프
무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.
방향 그래프
방향 그래프는 간선에 방향이 있는 그래프이다.
완전 그래프
완전 그래프는 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프이다. 정점이 N개인 방향이 없는 완전 그래프는 $N(N-1) / 2$개의 간선을 가지고, 방향이 있는 완전 그래프는 $N(N-1)$개의 간선을 가진다.
부분 그래프
원래 그래프에서 정점이나 간선을 일부 제외하여 만든 그래프이다.
가중 그래프
간선에 가중치를 할당한 그래프이다.
그래프 구현
인접 행렬
인접 행렬은 2차원 배열을 이용해서 그래프를 구현하는 방법이다. 그래프에 N개의 정점이 존재할 때, $N*N$ 크기의 배열로 그래프를 표현할 수 있다. N개의 행과 열에 각각 정점의 번호를 대입하고, 정점 u에서 정점 v로 가는 간선이 있다면 matrix[u][v] = true, 정점 v에서 정점 u로 가는 간선이 있다면 matrix[v][u] = true로 표현해준다.
인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 $O(1)$에 알아낼 수 있다. 하지만 $N^2$개의 메모리를 사용하게 되므로 간선의 개수가 적은 희소 그래프를 표현할 때는 메모리의 효율이 낮아지게 된다.
인접 행렬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Graph {
private boolean[][] graph;
private static final int MAX_VERTEX = 100;
private int vertexCnt = 0;
public void init() {
graph = new boolean[MAX_VERTEX][MAX_VERTEX];
}
public void insertVertex() {
if(vertexCnt + 1 > MAX_VERTEX) {
throw new ArrayIndexOutOfBoundsException();
}
else {
vertexCnt++;
}
}
public void insertEdge(int u, int v) {
if(u < 0 || u >= vertexCnt || v < 0 || v >= vertexCnt) {
throw new ArrayIndexOutOfBoundsException();
}
else {
graph[u][v] = graph[v][u] = true;
}
}
public void printGraph() {
for(int i = 0; i < vertexCnt; i++) {
for(int j = 0; j < vertexCnt; j++) {
if(graph[i][j]) {
System.out.print("1 ");
}
else {
System.out.print("0 ");
}
}
System.out.println();
}
}
}
인접 리스트
인접 리스트는 연결 리스트를 이용하여 그래프를 구현하는 방법이다. 헤더 노드들을 저장하는 배열을 만들고, 각 정점에 대응하는 연결 리스트의 헤더 노드들을 만든다. 그 후 헤더 노드의 인접 정점들을 연결 리스트에 저장하면 된다.
두 정점을 연결하는 간선의 존재 여부를 알기 위해서는 해당 노드의 차수만큼 탐색을 진행해야 하지만, 노드의 개수만큼만 메모리를 할당하면 되므로 메모리 효율이 좋다.
인접 리스트 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Graph {
private ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
private static final int MAX_VERTEX = 100;
private int vertexCnt = 0;
public void init() {
for(int i = 0; i < MAX_VERTEX - 1; i++) {
graph.add(new ArrayList<Integer>());
}
}
public void insertVertex() {
if(vertexCnt + 1 > MAX_VERTEX) {
throw new ArrayIndexOutOfBoundsException();
}
else {
vertexCnt++;
}
}
public void insertEdge(int u, int v) {
if(u < 0 || u >= vertexCnt || v < 0 || v >= vertexCnt) {
throw new ArrayIndexOutOfBoundsException();
}
else {
graph.get(u).add(v);
graph.get(v).add(u);
}
}
public void printGraph() {
for(int i = 0; i < vertexCnt; i++) {
System.out.print(i + "-> ");
for(int j = 0; j < graph.get(i).size() - 1; j++) {
System.out.print(graph.get(i).get(j) + ", ");
}
System.out.println(graph.get(i).getLast());
}
}
}
그래프는 문제의 요구 사항에 따라 설계 방식이 많이 달라져서 최대한 기본적인 메소드들만 구현.
그래프 순회
깊이 우선 탐색(DFS: Depth First Search)
DFS는 깊이를 우선적으로 탐색하는 알고리즘으로 그래프 뿐만 아니라 트리, 배열 등에서도 사용할 수 있다. 진행 방식은 아래와 같다. 그래프와 트리에서는 정점으로, 배열에서는 칸으로 생각하면 된다.
- 시작 정점을 방문한다.
- 시작 정점과 연결된 정점 중 하나를 방문한다. 방문할 수 있는 정점이 없는 경우 이전 정점으로 되돌아간다.
- 2번에서 방문한 정점을 시작 정점으로 탐색을 진행한다.
모든 정점을 방문할때까지 1~3번 과정을 반복하면 된다. 위 그래프에서 DFS를 진행하면 1->2->3->4->5의 순서대로 그래프를 탐색하게 된다. 2번 정점 대신 5번 정점을 먼저 방문해도 상관없다. DFS는 스택과 재귀 두 방식으로 구현할 수 있다.
깊이 우선 탐색 코드(스택)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Graph {
private ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
private final static int MAX_VERTEX = 6;
public void init() {
for(int i = 0; i < MAX_VERTEX; i++) {
graph.add(new ArrayList<Integer>());
}
graph.get(1).add(2);
graph.get(1).add(5);
graph.get(2).add(3);
graph.get(3).add(4);
}
public void dfs(int start) {
boolean[] visited = new boolean[MAX_VERTEX];
Stack<Integer> s = new Stack<>();
s.push(start);
while(!s.isEmpty()) {
int curNode = s.pop();
if(!visited[curNode]) {
visited[curNode] = true;
System.out.println(curNode + "방문");
for(int i = 0; i < graph.get(curNode).size(); i++) {
int nxtNode = graph.get(curNode).get(i);
if(!visited[nxtNode]) {
s.push(nxtNode);
}
}
}
}
}
}
깊이 우선 탐색 코드(재귀)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Graph {
private ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
private final static int MAX_VERTEX = 6;
public void init() {
for(int i = 0; i < MAX_VERTEX; i++) {
graph.add(new ArrayList<Integer>());
}
graph.get(1).add(2);
graph.get(1).add(5);
graph.get(2).add(3);
graph.get(3).add(4);
}
public void dfs(int start) {
boolean[] visited = new boolean[MAX_VERTEX];
recursion(visited, start);
}
private void recursion(boolean[] visited, int curNode) {
visited[curNode] = true;
System.out.println(curNode + "방문");
for(int i = 0; i < graph.get(curNode).size(); i++) {
int nxtNode = graph.get(curNode).get(i);
if(!visited[nxtNode]) {
recursion(visited, nxtNode);
}
}
}
}
너비 우선 탐색(BFS: Breadth First Search)
BFS는 너비를 우선적으로 탐색하는 알고리즘으로 그래프 뿐만 아니라 트리, 배열 등에서도 사용할 수 있다. 진행 방식은 아래와 같다. 그래프와 트리에서는 정점으로, 배열에서는 칸으로 생각하면 된다.
- 시작 정점을 방문한다.
- 시작 정점과 연결된 정점을 전부 방문한다.
- 2번에서 방문한 정점들을 시작 정점으로 탐색을 진행한다.
모든 정점을 방문할때까지 1~3번 과정을 반복하면 된다. 위 그래프에서 BFS를 진행하면 1->2->5->3->4의 순서대로 그래프를 탐색하게 된다. 2번 정점 대신 5번 정점을 먼저 방문해도 상관없다. BFS는 큐를 사용하여 구현할 수 있다.
너비 우선 탐색 코드(큐)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Graph {
private ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
private final static int MAX_VERTEX = 6;
public void init() {
for(int i = 0; i < MAX_VERTEX; i++) {
graph.add(new ArrayList<Integer>());
}
graph.get(1).add(2);
graph.get(1).add(5);
graph.get(2).add(3);
graph.get(3).add(4);
}
public void bfs(int start) {
boolean[] visited = new boolean[MAX_VERTEX];
Queue<Integer> q = new LinkedList<>();
q.add(start);
visited[start] = true;
System.out.println(start + "방문");
while(!q.isEmpty()) {
int curNode = q.poll();
for(int i = 0 ; i < graph.get(curNode).size(); i++) {
int nxtNode = graph.get(curNode).get(i);
if(!visited[nxtNode]) {
q.add(nxtNode);
visited[nxtNode] = true;
System.out.println(nxtNode + "방문");
}
}
}
}
}