[비선형 자료구조] 그래프
그래프(Heap)
- 정점과 간선으로 이루어진 자료 구조(Cyclic)
- 연결된 정점간의 관계를 표현할 수 있는 자료구조
- 그래프의 용도 : 지하철 노선도, 통신 네트워크 등등…
그래프의 구조
- 정점(Vertex): 각 노드
- 간선(Edge): 노드와 노드를 연결하는 선 (link, branch)
- 인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점
- 정점의 차수(Degree):
- 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
- 진입 차수(In-degree): 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수(Out-degree): 방향 그래프에서 외부로 나가는 간선의 수
- 경로 길이(Path length): 경로를 구성하는데 사용된 간선의 수
- 단순 경로(Simple path): 경로 중에서 반복되는 정점이 없는 경우
- 사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우
그래프와 트리의 차이
그래프의 종류
-
무방향 그래프
-
간선에 방향이 없는 그래프 (양방향 이동 가능)
-
정점 A - B 간선의 표현: (A, B) = (B, A)
-
-
방향 그래프
-
간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능)
-
정점 A → B 간선의 표현: <A, B> ≠ <B, A>
-
- 가중치 그래프
- 간선에 값이 있는 그래프 (이동 비용)
- 완전 그래프
- 모든 정점이 서로 연결되어 있는 그래프
- 정점이 N개일 경우, 간선의 수는 n(n-1)/2 개
그래프 탐색 - DFS
- 깊이 우선 탐색(Depth First Search)
- 각 노드에 방문했는지 여부를 체크할 배열과 스택 이용하여 구현
그래프 탐색 - BFS
- 너비 우선 탐색(Breath First Search)
- 각 노드에 방문했는지 여부를 체크할 배열과 큐를 이용하여 구현
그래프의 구현
-
인접 행렬(Adjacency Matrix) : 2차원 배열 이용
-
인접 행렬의 장단점
- 간선 정보의 확인과 업데이트가 빠름
- 인접 행렬을 위한 메모리 공간 차지
- 인접 리스트(Adjacency List) : 연결 리스트 이용
- 인접 리스트의 장단점
- 메모리 사용량이 상대적으로 적고 노드의 추가 삭제가 빠름
- 간선 정보 확인이 상대적으로 오래 걸림
인접 행렬 vs 인접 리스트
- 인접 행렬 : 노드의 수가 적고 간선의 수가 많을 때 유리
- 인접 리스트 : 노드의 수가 많고 간선의 수가 적을 때 유리
인접 행렬 구현
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class MyGraphMatrix {
char[] vertices;
int[][] adjMat;
int elemCnt;
public MyGraphMatrix() {
}
public MyGraphMatrix(int size) {
this.vertices = new char[size];
this.adjMat = new int[size][size];
this.elemCnt = 0;
}
public boolean isFull() {
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data) {
if (isFull()) {
System.out.println("Graph is full!");
return;
}
this.vertices[this.elemCnt++] = data;
}
//무방향 그래프
public void addEdge(int x, int y) {
this.adjMat[x][y] = 1;
this.adjMat[y][x] = 1;
}
public void deleteEdge(int x, int y) {
this.adjMat[x][y] = 0;
this.adjMat[y][x] = 0;
}
//방향 그래프
public void addDirectEdge(int x, int y) {
this.adjMat[x][y] = 1;
}
public void deleteDirectEdge(int x, int y) {
this.adjMat[x][y] = 0;
}
public void printAdjacentMatrix() {
System.out.print(" ");
for (char item : this.vertices) {
System.out.print(item + " ");
}
System.out.println();
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + " ");
for (int j = 0; j < this.elemCnt; j++) {
System.out.print(this.adjMat[i][j] + " ");
}
System.out.println();
}
}
public void dfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
//순회를 시작하려는 대상부터 스택에 추가
stack.push(id);
visited[id] = true;
//스택에서 하나씩 꺼내서 인접 정점확인 후 방문이없으면 다시 넣기
while (!stack.isEmpty()) {
int curId = stack.pop();
System.out.print(this.vertices[curId] + " ");
//교환 순서대로 탐색하기 위해서 거꾸로 탐색
for (int i = this.elemCnt - 1; i >= 0; i--) {
if (this.adjMat[curId][i] == 1 && visited[i] == false) {
stack.push(i);
visited[i] = true;
}
}
}
System.out.println();
}
public void bfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while (!queue.isEmpty()) {
int curId = queue.poll();
System.out.print(this.vertices[curId] + " ");
for (int i = this.elemCnt - 1; i >= 0; i--) {
if (this.adjMat[curId][i] == 1 && visited[i] == false) {
queue.offer(i);
visited[i] = true;
}
}
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class Node {
int id;
Node next;
public Node(int id, Node next) {
this.id = id;
this.next = next;
}
}
class MyGraphList {
char[] vertices;
Node[] adjList;
int elemCnt;
public MyGraphList() {
}
public MyGraphList(int size) {
this.vertices = new char[size];
this.adjList = new Node[size];
this.elemCnt = 0;
}
public boolean isFull() {
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data) {
if (isFull()) {
System.out.println("Graph is full!");
return;
}
this.vertices[elemCnt++] = data;
}
//무방향 그래프
public void addEdge(int x, int y) {
this.adjList[x] = new Node(y, this.adjList[x]);
this.adjList[y] = new Node(x, this.adjList[y]);
}
//방향 그래프
public void addDirectEdge(int x, int y) {
this.adjList[x] = new Node(y, this.adjList[x]);
}
public void printAdjacentList() {
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + ": ");
Node cur = this.adjList[i];
while (cur != null) {
System.out.print(this.vertices[cur.id] + " ");
cur = cur.next;
}
System.out.println();
}
}
public void dfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while (!stack.isEmpty()) {
int curId = stack.pop();
System.out.print(this.vertices[curId] + " ");
Node cur = this.adjList[curId];
while (cur != null) {
if (visited[cur.id] == false) {
stack.push(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
System.out.println();
}
public void bfs(int id) {
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while (!queue.isEmpty()) {
int curId = queue.poll();
System.out.print(this.vertices[curId] + " ");
Node cur = this.adjList[curId];
while (cur != null) {
if (visited[cur.id] == false) {
queue.offer(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
System.out.println();
}
}
댓글남기기