Post

🦊 6. Graphs

6. Graphs

κ·Έλž˜ν”„

νŠΈλ¦¬λŠ” κ·Έλž˜ν”„μ˜ ν•œ μ’…λ₯˜μ΄λ‹€.

ν•˜μ§€λ§Œ λͺ¨λ“  κ·Έλž˜ν”„κ°€ νŠΈλ¦¬λŠ” μ•„λ‹ˆλ‹€.

νŠΈλ¦¬λŠ” 사이클이 μ—†λŠ” ν•˜λ‚˜μ˜ μ—°κ²° κ·Έλž˜ν”„μ΄λ‹€.

κ·Έλž˜ν”„λŠ” λ‹¨μˆœνžˆ λ…Έλ“œμ™€ κ·Έ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” κ°„μ„ (edge)λ₯Ό ν•˜λ‚˜λ‘œ λͺ¨μ•„놓은 것과 κ°™λ‹€.

  • κ·Έλž˜ν”„λŠ” λ°©ν–₯성이 μžˆμ„ μˆ˜λ„ 있고 없을 μˆ˜λ„ μžˆλ‹€.
  • κ·Έλž˜ν”„λŠ” μ—¬λŸ¬ 고립된 λΆ€λΆ„ κ·Έλž˜ν”„λ‘œ ꡬ성될 수 μžˆλ‹€. λͺ¨λ“  정점 쌍 간에 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜λŠ” κ·Έλž˜ν”„λŠ” μ—°κ²° κ·Έλž˜ν”„ 라고 λΆ€λ₯Έλ‹€.
  • κ·Έλž˜ν”„μ—λŠ” 사이클이 μžˆμ„ μˆ˜λ„ 있고 없을 μˆ˜λ„ μžˆλ‹€. 사이클이 μ—†λŠ” κ·Έλž˜ν”„λŠ” λΉ„μˆœν™˜ κ·Έλž˜ν”„ 라고 λΆ€λ₯Έλ‹€.

인접 리슀트

인접 리슀트(adjacency list)λŠ” κ·Έλž˜ν”„λ₯Ό ν‘œν˜„ν•  λ•Œ μ‚¬μš©λ˜λŠ” κ°€μž₯ 일반적인 방법이닀.

λͺ¨λ“  정점을 인접 λ¦¬μŠ€νŠΈμ— μ €μž₯ν•œλ‹€.

무방ν–₯ κ·Έλž˜ν”„λŠ” (a, b) 간선이 두 번 μ €μž₯λœλ‹€.

1
2
3
4
5
6
7
8
Class Graph {
	public Node[] nodes;
}

Class Node {
	public String name;
	public Node[] children;
}

κ·Έλž˜ν”„λŠ” νŠΈλ¦¬μ™€ 달리 νŠΉμ • λ…Έλ“œμ—μ„œ λ‹€λ₯Έ λͺ¨λ“  λ…Έλ“œλ‘œ 접근이 κ°€λŠ₯ν•˜μ§€λŠ” μ•Šμ•„ Graph λΌλŠ” 클래슀λ₯Ό μ‚¬μš©ν•œλ‹€.

λ°°μ—΄, ν•΄μ‹œν…Œμ΄λΈ”κ³Ό 각 μΈλ±μŠ€λ§ˆλ‹€ μ‘΄μž¬ν•˜λŠ” 또 λ‹€λ₯Έ 리슀트λ₯Ό μ΄μš©ν•΄ 인접 리슀트λ₯Ό ν‘œν˜„ν•  수 μžˆλ‹€.

1
2
3
4
5
6
7
0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5

인접 ν–‰λ ¬

인접 행렬은 NxN 뢈린 ν–‰λ ¬λ‘œμ¨ matrix[i][j] == true 이면 i -> j 간선이 μžˆλ‹€λŠ” 것이닀.

인접 행렬은 쑰금 νš¨μœ¨μ„±μ΄ 떨어진닀.

μ–΄λ–€ λ…Έλ“œμ— μΈμ ‘ν•œ λ…Έλ“œλ₯Ό μ°ΎκΈ° μœ„ν•΄μ„œ λͺ¨λ“  λ…Έλ“œλ₯Ό μ „λΆ€ μˆœνšŒν•΄μ•Ό ν•  수 μžˆλ‹€.

κ·Έλž˜ν”„ 탐색

깊이 μš°μ„  탐색(DFS)λŠ” 루트 λ…Έλ“œμ—μ„œ μ‹œμž‘ν•΄μ„œ λ‹€μŒ λΆ„κΈ°λ‘œ λ„˜κ±°κ°€κΈ° 전에 ν•΄λ‹Ή λΆ„κΈ°λ₯Ό μ™„λ²½ν•˜κ²Œ νƒμƒ‰ν•˜λŠ” 방법이닀.

λ„ˆλΉ„ μš°μ„  탐색(BFS)λŠ” 루트 λ…Έλ“œμ—μ„œ μ‹œμž‘ν•΄μ„œ μΈμ ‘ν•œ λ…Έλ“œλ₯Ό λ¨Όμ € νƒμƒ‰ν•˜λŠ” 방법이닀.

DFSλŠ” κ·Έλž˜ν”„μ—μ„œ λͺ¨λ“  λ…Έλ“œλ₯Ό λ°©λ¬Έν•˜κ³ μž ν•  λ•Œ μ„ ν˜Έλ˜λŠ” νŽΈμ΄λ‹€.

BFSλŠ” 두 λ…Έλ“œ μ‚¬μ΄μ˜ μ΅œλ‹¨ 경둜 ν˜Ήμ€ μž„μ˜μ˜ 경둜λ₯Ό μ°Ύκ³  싢을 λ•Œ μΌλ°˜μ μ΄λ‹€.

깊이 μš°μ„  탐색(DFS)

트리의 μˆœνšŒμ™€ κ·Έλž˜ν”„ νƒμƒ‰μ˜ κ°€μž₯ 큰 μ°¨μ΄λŠ” μ–΄λ–€ λ…Έλ“œλ₯Ό λ°©λ¬Έν–ˆμ—ˆλŠ”μ§€ μ—¬λΆ€λ₯Ό λ°˜λ“œμ‹œ 검사해야 ν•œλ‹€λŠ” 것이닀.

그렇지 μ•Šμ„ 경우 λ¬΄ν•œλ£¨ν”„μ— 빠질 μœ„ν—˜μ΄ μžˆλ‹€.

1
2
3
4
5
6
7
8
9
10
void search(Node root) {
	if (root == null) return;
	visit(root);
	root.visited = true;
	for each (Node n in root.adjacent) {
		if (n.visited == false) {
			search(n);
		}
	}
}

λ„ˆλΉ„ μš°μ„  탐색(BFS)

BFS λŠ” μž¬κ·€μ μœΌλ‘œ λ™μž‘ν•˜μ§€ μ•Šκ³  큐λ₯Ό μ‚¬μš©ν•œλ‹€.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void search(Node root) {
	Queue queue = new Queue();
	root.marked = true;
	queue.enqueue(root);

	while (!queue.isEmpty()) {
		Node r = queue.dequeue();
		visit(r);
		foreach (Node n in r.adjacent) {
			if (n.marked == false) {
				n.marked = true;
				queue.enqueue(n);
			}
		}
	}
}

μ–‘λ°©ν–₯ 탐색

μ–‘λ°©ν–₯ 탐색은 μΆœλ°œμ§€μ™€ 도착지 사이에 μ΅œλ‹¨ 경둜λ₯Ό 찾을 λ•Œ μ‚¬μš©λ˜κ³€ ν•œλ‹€.

기본적으둜 μΆœλ°œμ§€μ™€ 도착지 두 λ…Έλ“œμ—μ„œ λ™μ‹œμ— λ„ˆλΉ„ μš°μ„  탐색을 μˆ˜ν–‰ν•œ λ’€, 두 탐색 지점이 μΆ©λŒν•˜λŠ” κ²½μš°μ— 경둜λ₯Ό μ°ΎλŠ” 방식이닀.

λͺ¨λ“  λ…Έλ“œκ°€ 적어도 k개의 이웃 λ…Έλ“œμ™€ μ—°κ²°λ˜μ–΄ 있고 s β†’ t둜의 μ΅œλ‹¨ 거리가 dκ°€ λ˜λŠ” κ·Έλž˜ν”„λ₯Ό μƒκ°ν•΄λ³΄μž.

  • 전톡적인 BFS μ—μ„œλŠ” λ ˆλ²¨λ§ˆλ‹€ k 개의 λ…Έλ“œλ₯Ό 탐색해야 ν•˜λ―€λ‘œ d번 λ°˜λ³΅ν•˜λ©΄ O(K^d) 개의 λ…Έλ“œλ₯Ό νƒμƒ‰ν•œλ‹€.
  • μ–‘λ°©ν–₯ 탐색을 μ‚¬μš©ν•œλ‹€λ©΄ λŒ€λž΅ d/2 λ‹¨κ³„κΉŒμ§€ νƒμƒ‰ν•œ ν›„ μΆ©λŒν•œλ‹€. λ”°λΌμ„œ s 와 t κ°κ°μ—μ„œ λ°©λ¬Έν•  λ…Έλ“œλŠ” k^(d/2) κ°œκ°€ 될 것이고 전체 λ°©λ¬Έν•  λ…Έλ“œλŠ” λŒ€λž΅ 2*k^(d/2) κ°œκ°€ λœλ‹€.

즉, μ–‘λ°©ν–₯ 탐색은 BFS 보닀 적어도 k^(d/2) 만큼 λΉ λ₯΄λ‹€.

λ‹€λ₯Έ λ°©μ‹μœΌλ‘œ λ§ν•˜λ©΄ 2λ°° 더 κΈ΄ κ²½λ‘œκΉŒμ§€ 찾을 수 μžˆλ‹€!

This post is licensed under CC BY 4.0 by the author.