🐳Dev/Algorithm

[μ•Œκ³ λ¦¬μ¦˜] 06. Topological Sort

fortune.00 2021. 11. 24. 18:38

Topological Sort

μœ„μƒμ •λ ¬

: μˆœμ„œκ°€ μžˆλŠ” μž‘μ—…μ„ μ°¨λ‘€λ‘œ μˆ˜ν–‰ν•΄μ•Ό ν•  λ•Œ, μˆœμ„œλ₯Ό κ²°μ •ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜

: 사이클이 μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ” κ·Έλž˜ν”„μ—μ„œλ§Œ 적용 κ°€λŠ₯ν•˜λ‹€
: ν•˜λ‚˜μ˜ λ°©ν–₯ κ·Έλž˜ν”„(DAG = Directed Acyclic Graph)μ—μ„œ μ—¬λŸ¬ μœ„μƒ 정렬이 λ§Œλ“€μ–΄ 질 수 μžˆλ‹€
: μœ„μƒ μ •λ ¬μ˜ κ³Όμ •μ—μ„œ κ·Έλž˜ν”„μ— λ‚¨μ•„μžˆλŠ” 정점 쀑에 μ§„μž…μ°¨μˆ˜κ°€ 0인 정점이 μ—†λ‹€λ©΄ 정렬이 μ€‘λ‹¨λ˜κ³ , ν•΄λ‹Ή λ¬Έμ œλŠ” 싀행이 λΆˆκ°€λŠ₯ν•œ λ¬Έμ œκ°€ λœλ‹€

 

  • Queue

 

  1. μ§„μž… μ°¨μˆ˜κ°€ 0인 정점을 큐에 μ‚½μž…
  2. νμ—μ„œ μ„ νƒλœ 정점과 여기에 λΆ€μ†λœ λͺ¨λ“  간선을 μ‚­μ œ
  3. μœ„μ˜ 과정을 λ°˜λ³΅ν•΄μ„œ λͺ¨λ“  정점이 선택, μ‚­μ œλ˜λ©΄ μ•Œκ³ λ¦¬μ¦˜ μ’…λ£Œ