π¦ 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λ°° λ κΈ΄ κ²½λ‘κΉμ§ μ°Ύμ μ μλ€!