π’ λ°©ν₯κ·Έλν
- λ°©ν₯κ·Έλν(Digraph) : λͺ¨λ κ°μ μ΄ λ°©ν₯κ°μ μΈ κ·Έλν
π’ λ°©ν₯κ·Έλν μμ±
- λͺ¨λ κ°μ μ΄ ν λ°©ν₯μΌλ‘ μ§ννλ κ·Έλν G = (V,E)μμ
π κ°μ (a,b)λ a -> b λ‘λ κ°μ§λ§, b -> a λ‘λ κ°μ§ μλλ€. - κ·Έλν Gκ° λ¨μνλ€λ©΄ ( μ¦, λ³λ ¬κ°μ μ΄λ, 루νκ° μμΌλ©΄ )
π M <= N(N-1) μ΄λ€. ( 무방ν₯κ·Έλνμμ M <= (N(N-1)/2 μλ€. )
( μ¬κΈ°μ M = κ°μ μ, N = μ μ μ μ΄λ€. ) - μ§μ
κ°μ λ€(in-edges)κ³Ό μ§μΆκ°μ λ€(out-edges)μ κ°κ° λ³λμ μΈμ 리μ€νΈλ‘ 보κ΄νλ€λ©΄, μ§μ
κ°μ λ€μ μ§ν©κ³Ό
μ§μΆκ°μ λ€μ μ§ν©μ κ°κ°μ ν¬κΈ°μ λΉλ‘ν μκ°μ μ‘°μ¬ κ°λ₯νλ€.


π’ λ°©ν₯ DFS
- κ°μ λ€μ μ£Όμ΄μ§ λ°©ν₯λ§μ λ°λΌ μννλλ‘ νλ©΄, DFS λ° BFS μν μκ³ λ¦¬μ¦λ€μ λ°©ν₯κ·Έλνμ νΉν κ°λ₯νλ€.
- λ°©ν₯ DFS μκ³ λ¦¬μ¦μμ λ€ μ’
λ₯μ κ°μ μ΄ λ°μνλ€.
π νΈλ¦¬κ°μ (tree edges) : νΈλ¦¬μμ, DFSκ²½λ‘μ ν΄λΉνλ κ°μ
π νν₯κ°μ (back edges) : νΈλ¦¬μμ λμ μ‘°μλ°©ν₯μΌλ‘ κ·Έλ €μ§ κ°μ
π μ ν₯κ°μ (forward edges) : νΈλ¦¬μμ λμ μμμ΄ μλ, λ μλ μμ μ μ μ κ²½μ° κ·Έλ €μ§ κ°μ
π κ΅μ°¨κ°μ (cross edges) : κ°μ λ 벨μ΄λ νμλ 벨 μ μ λΌλ¦¬μ μ°κ²° κ°μ - μ μ sμμ μΆλ°νλ λ°©ν₯ DFS π sλ‘λΆν° λλ¬ κ°λ₯ν μ μ λ€μ κ²°μ νλ€.


- λλ¬ κ°λ₯μ±μ΄λ ?
π λ°©ν₯κ·Έλν Gμ λ μ μ vμ uμ λν΄, λ§μ½ Gμ vμμ uλ‘μ λ°©ν₯ κ²½λ‘κ° μ‘΄μ¬νλ€λ©΄, "vλ uμ λλ¬νλ€" λλ "uλ vλ‘λΆν° λλ¬ κ°λ₯νλ€" λ₯Ό μλ―Ένλ€.
π sλ₯Ό 루νΈλ‘ νλ DFS νΈλ¦¬ : sλ‘λΆν° λ°©ν₯κ²½λ‘λ₯Ό ν΅ν΄ λλ¬ κ°λ₯ν μ μ λ€μ νμν κ²

π’ κ°μ°κ²°μ±
- λ°©ν₯κ·Έλν Gμ μ΄λ λ μ μ uμ vμ λν΄μλ uλ vμ λλ¬νλ©° vλ uμ λλ¬νλ©΄
π Gλ₯Ό κ°μ°κ²°(strongly connected)μ΄λΌκ³ λ§νλ€. μ¦, μ΄λ μ μ μμλ μ§ λ€λ₯Έ λͺ¨λ μ μ μ λλ¬ κ°λ₯νλ€.

- κ°μ°κ²° κ²μ¬ μκ³ λ¦¬μ¦
π 1. κ·Έλν Gμ μμμ μ μ vλ₯Ό μ ννλ€.
π 2. κ·Έλν Gμ vλ‘λΆν° DFSλ₯Ό μννλ€. ( λ°©λ¬Έλμ§ μμ μ μ wκ° μλ€λ©΄, Falseλ₯Ό λ°ννλ€. )
π 3. κ·Έλν Gμ κ°μ λ€μ λͺ¨λ μνμν¨ κ·Έλν G` λ₯Ό μ»λλ€.
π 4. G`μ vλ‘λΆν° DFSλ₯Ό μννλ€. ( λ°©λ¬Έλμ§ μμ μ μ wκ° μλ€λ©΄, Falseλ₯Ό λ°ν. κ·Έλ μ§ μμΌλ©΄, True λ°ν)
μ€νμκ° = O(N + M)

- κ°μ°κ²°μμ
π λ°©ν₯κ·Έλνμ κ° μ μ μΌλ‘ λ€λ₯Έ λͺ¨λ μ μ μΌλ‘ λλ¬ν μ μλ μ΅λμ λΆ κ·Έλν
π DFSλ₯Ό μ¬μ©νμ¬ O(N + M)μκ°μ κ³μ° κ°λ₯νλ€.

π’ μ΄νμ νμ
- μ£Όμ΄μ§ λ°©ν₯κ·Έλν Gμ λν΄, κ·Έλν Gμ μ΄νμ νμ(Transitive Closure)λ λ€μμ λ§μ‘±νλ λ°©ν₯κ·Έλν G*
π G* λ Gμ λμΌν μ μ λ€λ‘ ꡬμ±
π Gμ uλ‘λΆν° v β u λ‘μ λ°©ν₯κ²½λ‘κ° μ‘΄μ¬νλ€λ©΄, G*μ uλ‘λΆν° vλ‘μ λ°©ν₯κ°μ μ΄ μ‘΄μ¬νλ€.
π λ μ½κ², μνμ μΌλ‘, "A -> B , B -> C μ΄λ©΄, A -> C" λ₯Ό μλ―Ένλ κ² - μ΄νμ νμλ λ°©ν₯κ·Έλνμ κ΄ν λλ¬ κ°λ₯μ± μ 보λ₯Ό μ 곡νλ€.

- μ΄νμ νμ κ³μ°
π κ° μ μ μμ μΆλ°νμ¬ DFSλ₯Ό μνν μ μλ€.
μ€νμκ° : O(N(N + M))) π Nκ°μ κ° μ μ μ λν΄ * DFS - λμμΌλ‘, λμ νλ‘κ·Έλλ°(DP, Dynamic Programming)μ μ¬μ©ν μ μλ€.
π Floyed-Warshall μκ³ λ¦¬μ¦ : μμμ μ€λͺ ν, "A -> B , B -> C μ΄λ©΄, A -> C"
π’ Floyed-Warshall μ΄νμ νμ
- μ μ λ€μ 1,2,....nμΌλ‘ λ²νΈλ₯Ό λ§€κΈ΄λ€.
- 1,2,....,kλ‘ λ²νΈ λ§€κ²¨μ§ μ μ λ€λ§ κ²½μ μ μ μΌλ‘ μ¬μ©νλ κ²½λ‘λ€μ κ³ λ €ν΄λ³Έλ€.

Alg Floyed-Warshall(G) input a digraph G with n vertexs output transitive closure G* of G Let V(1),V(2),...,V(n) be an arbitrary numbering of the vertexs of G G(0) <- G for k <- 1 to n // Stopover vertex G(k) <- G(k-1) for i <- 1 to n, i β k // start vertex for j <- 1 to n, j β i,k // end vertex if(G(k-1).areAdjacent(V(i),V(k) & G(k-1).areAdjacent(V(k),V(j)) if(!(G(k).areAdjacent(V(i),V(j)) G(k).insertDirectedEdge(V(i),V(j),k) return G(n)
- Floyed-Warshall μκ³ λ¦¬μ¦μ Gμ μ μ λ€μ V(1),....,V(n)μΌλ‘ λ²νΈ λ§€κΈ΄ ν, λ°©ν₯κ·Έλν G(0),....,G(n)μ μλ¬μ κ³μ°
π G(0) = G
π Gμ { V(1),....V(k) } μ§ν© λ΄μ κ²½μ μ μ μ μ¬μ©νλ V(i)μμ V(j)λ‘μ λ°©ν₯κ²½λ‘κ° μ‘΄μ¬νλ©΄ G(k)μ λ°©ν₯κ°μ
(V(i), V(j))λ₯Ό μ½μ - k λ¨κ³μμ, λ°©ν₯κ·Έλν G(k-1)λ‘λΆν° G(k)λ₯Ό κ³μ°
- λ§μ§λ§μ G(n) = G*λ₯Ό μ»μ
- μ€νμκ° : O(n^3)
π μ μ : μΈμ νμ§ μμ보λ areAdjacent( )κ° O(1)μκ°μ μν ( μ¦, μΈμ νλ ¬ λ²μ ΌμΌ κ²½μ° )

π’ λ°©ν₯ λΉμΈμ΄ν΄ κ·Έλν
- λ°©ν₯ λΉμΈμ΄ν΄ κ·Έλν(DAG, Directed Acyclic Graph) : λ°©ν₯μΈμ΄ν΄μ΄ μ‘΄μ¬νμ§ μλ λ°©ν₯κ·Έλν
- μμ
π ν΄λμ€ κ° μμ λλ μΈν°νμ΄μ€
π κ΅κ³Ό κ°μ μ μ κ΄κ³ λ±λ± - λ°©ν₯κ·Έλνμ μμμμ(Topological Order)
π λͺ¨λ i < jμΈ κ°μ (V(i),V(j))μ λν΄ μ μ λ€μ λ²νΈλ‘ λμ΄ν κ²μ΄λ€.
π μμ) μμ μ€μΌμ₯΄λ§ λ°©ν₯κ·Έλνμμ μμμμλ μμ λ€μ μ°μ d λ§μ‘±νλ μμ μμ
κ²°λ‘ : λ°©ν₯κ·Έλνκ° DAG μ΄λ©΄ π μμμμλ₯Ό κ°μ§λ©°, κ·Έ μλ μ°Έμ΄λ€.

π’ μμμ λ ¬(Topological Sort)
- μμ μ λ ¬(Topological Sort) : DAGλ‘λΆν° μμμμλ₯Ό μ»λ μ μ°¨
- μκ³ λ¦¬μ¦
π 1. topologicalSort : μ μ μ μ§μ μ°¨μ(in-degree)λ₯Ό μ΄μ©ν λ°©λ²
π 2. topologicalSortDFS : DFSμ νΉνλ λ°©λ² - 1. topologicalSort : μ μ μ μ§μ μ°¨μ(in-degree)λ₯Ό μ΄μ©ν λ°©λ²
Alg topologicalSort(G) input a digraph G with n vertexs output a topological ordering V(1),...,V(n) of G, or an indication that G has a directed cycle Q <- empty queue for each u β G.vertexs() in(u) <- inDegree(u) if(in(u) == 0) Q.enqueue(u) i <- 1 // topological number while(!(Q.isEmpty()) u <- Q.dequeue() Label u with topological number i i <- i + 1 for each e β G.outIncidentEdges(u) w <- G.opposite(u,e) in(w) <- in(w) - 1 if(in(w) == 0) Q.enqueue(w) if(i <= n) // i = n + 1, for DAG write("G has a directed cycle) // DAGκ° μλμ μ리λ λ©μμ§ return // κ° μ μ μ μλ‘μ΄ λΌλ²¨μ μ μ => νμ¬ μ§μ
μ°¨μ(inCount) : in(v) => μ μ vμ νμ¬μ μ§μ
μ°¨μ κ³μ°

- 2. topologicalSortDFS : DFSλ₯Ό νμ©ν μμμ λ ¬
Alg topologicalSortDFS(G) input DAG G output topological ordering of G n <- G.numVertexs() for each u β G.vertexs() l(u) <- Fresh for each v β G.vertexs() if(l(v) == Fresh) rTopologicalSortDFS(G,v) ========================================= Alg rTopologicalSortDFS(G,v) // μ¬κ·μ DFSλ₯Ό νμ©ν μμμ λ ¬ input graph G, and a start vertex v of G output labeling of the vertexs of G in the connected component of v l(v) <- Visited for each e β G.outIncidentEdges(v) w <- opposite(v,e) if(l(w) == Fresh) // κ°μ eλ tree κ°μ rTopologicalSortDFS(G,w) Label v with topological number n n <- n - 1 // μ μ λ³μλ‘ μ μ΄ν κ²μ΄λ€.

- μμ μ λ ¬ μκ³ λ¦¬μ¦ λΉκ΅
1. topologicalSort : μ μ μ μ§μ μ°¨μλ₯Ό μ΄μ©ν λ²μ Ό
π O(N + M) μκ°κ³Ό O(N) κ³΅κ° μμ
π κ·Έλν Gκ° DAGλΌλ©΄ μμμμλ₯Ό κ³μ°
π κ·Έλν Gμ λ°©ν₯μΈμ΄ν΄μ΄ μ‘΄μ¬ν κ²½μ°, μΌλΆ μ μ μ μμλ₯Ό λ§€κΈ°μ§ μμ μ±λ‘ "μ μ§"
2. topologicalSortDFS : DFS νμ©ν λ²μ Ό
π O(N + M) μκ°κ³Ό O(N) κ³΅κ° μμ
π κ·Έλν Gκ° DAGλΌλ©΄ Gμ μμμμλ₯Ό κ³μ°
π κ·Έλν Gμ λ°©ν₯μΈμ΄ν΄μ΄ μ‘΄μ¬ν κ²½μ°, νμμ μμμμλ₯Ό κ³μ° = λ°©ν₯μΈμ΄ν΄μ λ°κ²¬νλλ‘ μμ κ°λ₯ν¨ !!
728x90
λ°μν
'Algorithm Theory' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
μ΅μμ μ₯νΈλ¦¬(Minimum Spanning Tree) (0) | 2020.12.15 |
---|---|
λμ νλ‘κ·Έλλ°(Dynamic Programming) (0) | 2020.12.14 |
κ·Έλν μν(Graph Traversal) (0) | 2020.12.14 |
κ·Έλν(Graph) (0) | 2020.12.13 |
ν΄μν μ΄λΈ(Hash Table) (0) | 2020.12.13 |