λͺ©λ‘Depth-First Search (1)

𝘚𝘭𝘰𝘸 𝘣𝘢𝘡 𝘴𝘡𝘦𝘒π˜₯𝘺

[μ•Œκ³ λ¦¬μ¦˜] κ·Έλž˜ν”„ 순회 문제 - 1. 깊이 μš°μ„  탐색(DFS)

'μ½”λ”© ν…ŒμŠ€νŠΈλ₯Ό μœ„ν•œ 자료 ꡬ쑰와 μ•Œκ³ λ¦¬μ¦˜ with C++' λ₯Ό μ°Έκ³ ν•˜μ—¬ μž‘μ„±ν•˜μ˜€μŠ΅λ‹ˆλ‹€. 더보기 1. κ·Έλž˜ν”„ ; Graph 1.1 κ°œλ… κ·Έλž˜ν”„ 순회 문제λ₯Ό λ“€μ–΄κ°€κΈ° μ „ 짧게 κ·Έλž˜ν”„μ— λŒ€ν•΄ μ„€λͺ…ν•˜μžλ©΄, κ·Έλž˜ν”„λŠ” 정점(vertex)의 집합과 정점듀을 μ„œλ‘œ μž‡λŠ” κ°„μ„ (edge)의 μ§‘ν•©μœΌλ‘œ κ΅¬μ„±λœ 자료ꡬ쑰둜 μ—°κ²°λ˜μ–΄ μžˆλŠ” 객체 κ°„μ˜ 관계λ₯Ό ν‘œν˜„ν•  수 μžˆλ‹€. μˆ˜ν•™μ μœΌλ‘œλŠ” G = (vλŠ” 정점, eλŠ” κ°„μ„ μ˜ 집합) ν˜•νƒœλ‘œ ν‘œν˜„ν•  수 μžˆλ‹€. κ°„μ„  λ°©ν–₯의 μœ λ¬΄μ— 따라 λ°©ν–₯ κ·Έλž˜ν”„(directed graph)와 무방ν–₯ κ·Έλž˜ν”„(undirected graph)둜 λ‚˜λˆŒ 수 있고, κ°„μ„ μ˜ κ°€μ€‘μΉ˜ μœ λ¬΄μ— 따라 가쀑 κ·Έλž˜ν”„(weighted graph)와 비가쀑 κ·Έλž˜ν”„(unweighted graph)둜 λ‚˜λˆˆλ‹€. 2. κ·Έλž˜ν”„ 순회 문제..
μ•Œκ³ λ¦¬μ¦˜ 2021. 7. 21. 02:37
Prev 1 Next