๋ฐ˜์‘ํ˜•
๊ตญ๋ฏผ๋Œ€ํ•™๊ต์—์„œ "์‰ฝ๊ฒŒ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜" ๊ต์žฌ๋ฅผ ์ด์šฉํ•œ
 ๋ฐ•ํ•˜๋ช… ๊ต์ˆ˜๋‹˜์˜ ๊ฐ•์˜ ๊ต์•ˆ์„ ์ด์šฉํ•˜์—ฌ ์ˆ˜์—… ๋‚ด์šฉ์„ ์ •๋ฆฌํ•˜์˜€์Šต๋‹ˆ๋‹ค

 

 

Minimum Spanning Trees

 

 

 

Spanning Tree๋ž€ ๊ทธ๋ž˜ํ”„ G = (V, E)์—์„œ ๊ฐ„์„ ์„ |V| - 1 ๊ฐœ๋งŒ ๋‚จ๊ฒจ ํŠธ๋ฆฌ๊ฐ€ ๋˜๋„๋ก ๋งŒ๋“  ๊ฒƒ

 

Minimm Spanning Tree๋ž€ Spanning Tree ์ค‘์—์„œ edge weight์˜ ํ•ฉ์ด ๊ฐ€์žฅ ์ž‘์€ ๊ฒƒ

=> ํ•œ ๊ทธ๋ž˜ํ”„์— ์—ฌ๋Ÿฌ๊ฐœ์˜ MST๊ฐ€ ์กด์žฌํ•  ์ˆ˜ ์žˆ์Œ

 

์–ด๋–ป๊ฒŒ MST๋ฅผ ๊ตฌํ• ๊นŒ..?

 

Naive Solution์„ ์ƒ๊ฐํ•ด๋ณด๋ฉด

 

๋ชจ๋“  subgraph๋ฅผ ์‚ดํŽด๋ณด๊ณ , ๊ทธ ์ค‘์—์„œ spanning tree์ด๋ฉด์„œ weight์˜ ํ•ฉ์ด ๊ฐ€์žฅ ์ž‘์€ ๊ฒƒ์„ ์ฐพ์œผ๋ฉด๋จ

 

=> subgraph์˜ ์ˆ˜๋Š” ๊ฐ๊ฐ์˜ edge๊ฐ€ ์žˆ๋ƒ ์—†๋ƒ์— ๋”ฐ๋ผ ๊ฒฐ์ •๋˜๋ฏ€๋กœ 2^|E| ์ž„
(ํฐ ๊ทธ๋ž˜ํ”„๋Š” ์‚ฌ์‹ค์ƒ ์ฒ˜๋ฆฌ ๋ถˆ๊ฐ€)

 

์ด์— ๋Œ€ํ•ด ํšจ์œจ์ ์ธ ํฌ๋ฃจ์Šค์นผ, ํ”„๋ฆผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•จ
(๋‘˜๋‹ค Greedy Algorithm)

 

Kruskal's Algorithm

 

Cycle์„ ๋งŒ๋“ค์ง€ ์•Š๋Š” ์ตœ์†Œ ๊ฐ„์„ ์„ MST์— ๋ฐ˜๋ณตํ•˜์—ฌ ์ถ”๊ฐ€ํ•˜๋Š” ๊ฒƒ์ž„

 

Kruskal's Algorithm

 

์ˆœ์„œ๋Š”

 

1. ๊ฐ„์„ ์„ weight๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ

 

2. weight๊ฐ€ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ„์„ ์„ ์„ ํƒํ•˜๊ณ  ์ด๋ฏธ MST์— ์ถ”๊ฐ€๋œ ๊ฐ„์„ ๋“ค๊ณผ cycle์„ ์ด๋ฃจ๋Š”์ง€ ํ™•์ธ

 

=> cycle์„ ์ด๋ฃจ๋Š” ๊ฒฝ์šฐ ๊ฐ„์„ ์„ ์ œ์™ธํ•˜๊ณ  ์ด๋ฃจ์ง€ ์•Š๋Š” ๊ฒฝ์šฐ ๊ฐ„์„ ์„ MST์— ์ถ”๊ฐ€

 

3. |V| - 1 ๊ฐœ์˜ ๊ฐ„์„ ์ด ์„ ํƒ๋  ๋•Œ ๊นŒ์ง€ Step 2๋ฅผ ๋ฐ˜๋ณต

 

Cycle์„ ํšจ์œจ์ ์œผ๋กœ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด Disjoint Set์„ ํ™œ์šฉ

 

 

Disjoint Set์ด ๊ธฐ์–ต์ด ์•ˆ๋‚˜๋ฉด

 

https://hanjungyo.tistory.com/96

 

L10 - Disjoint Sets

๊ตญ๋ฏผ๋Œ€ํ•™๊ต์—์„œ "์‰ฝ๊ฒŒ ๋ฐฐ์šฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜" ๊ต์žฌ๋ฅผ ์ด์šฉํ•œ ๋ฐ•ํ•˜๋ช… ๊ต์ˆ˜๋‹˜์˜ ๊ฐ•์˜ ๊ต์•ˆ์„ ์ด์šฉํ•˜์—ฌ ์ˆ˜์—… ๋‚ด์šฉ์„ ์ •๋ฆฌํ•˜์˜€์Šต๋‹ˆ๋‹ค  Disjoint Sets Disjoint Sets๋ž€ ์„œ๋กœ ๊ฒน์น˜์ง€ ์•Š๋Š” ์ง‘ํ•ฉ๋“ค์„ ์˜๋ฏธํ•จ =>

hanjungyo.tistory.com

 

 

๊ทธ๋ž˜์„œ ๊ฒฐ๋ก ์ ์œผ๋กœ Disjoint Set์„ ํ™œ์šฉํ•ด Cycle์„ ํ™•์ธํ•˜๋Š” ๋ฐฉ๋ฒ•์€

 

์œ„ ๊ทธ๋ž˜ํ”„์—์„œ ๊ฐ„์„ ์ด (1, 2), (3, 4), (1, 3), (2, 4) ์ˆœ์„œ๋กœ ์ถ”๊ฐ€๋  ๋•Œ

 

  • ๊ฐ ์ •์ ์ด ๋…๋ฆฝ๋œ ์ง‘ํ•ฉ์„ ์ด๋ฃจ๋„๋ก ์ดˆ๊ธฐํ™” (make-set)

  • ๊ฐ„์„  (u, v)๊ฐ€ MST์— ์ถ”๊ฐ€๋  ๋•Œ union(u, v) ์‹คํ–‰

  • ๊ฐ„์„  (u, v)๊ฐ€ cycle์„ ์ด๋ฃฌ๋‹ค๋Š”๊ฑด u์™€ v๊ฐ€ ๊ฐ™์€ ์ง‘ํ•ฉ์— ์žˆ๋‹ค๋Š” ๋œป

    => ์ฆ‰, find-set(u) = find-set(v)์ธ ๊ฒฝ์šฐ cycle์„ ์ด๋ฃธ

 

Complexity Analysis

 

pseudo code๋ฅผ ์‚ดํŽด๋ณด๋ฉด

 

mst = [] # edges of MST

for u in range(n + 1) :
	make_set(u)
   
#sort by weight
edges.sort(lambda x: x[2])

for u, v in edges :
	if find_set(u) != find_set(v) :
    	mst.append((u, v))
        union(u, v)

 

Space Complexity

 

  • Edges : O(|E|)

    => edge๋งŒ ์ž…๋ ฅ์œผ๋กœ ์ฃผ๋ฉด ๋˜๋ฏ€๋กœ
    (edge๋งŒ ์ •๋ ฌ, ์ˆœํšŒํ•จ)

  • Disjoint sets : O(|V|)

    => ๊ฐ ๋…ธ๋“œ๊ฐ€ ๋ถ€๋ชจ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๋ฏ€๋กœ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜์™€ ๋™์ผ

  • Total : O(|V| + |E|)

 

Time Complexity

 

  • Sorting : O(|E|log|E|)

    => ์—ฌ๊ธฐ์„œ E๋Š” ์ตœ๋Œ€ V^2 ์ด๋ฏ€๋กœ |E|log|V|^2 = 2|E|log|V| = O(|E|log|V|)๋กœ ๋ณผ ์ˆ˜ ์žˆ์Œ

  • Disjoint sets : O(|E|log*|V|)

    => log*์€ ์‚ฌ์‹ค์ƒ ์ƒ์ˆ˜์ด๋ฏ€๋กœ Sorting์ด ์šฐ์„ธํ•ญ์œผ๋กœ ์ž‘์šฉ

  • Total : O(|E|log|V|)

 

Prim's Algorithm

 

MST์— ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์ •์ ์„ ๋ฐ˜๋ณตํ•˜์—ฌ ์ถ”๊ฐ€ํ•˜๋Š” ๊ฒƒ์ž„

 

๋น„์šฉ ์ค‘์‹ฌ์œผ๋กœ ๋ดค์„ ๋•Œ ๊ฐ€์žฅ ๋น„์šฉ์ด ๋‚ฎ์€ ์ •์  ์„ฑํƒ

 

๊ฐ„์„  ์ค‘์‹ฌ์œผ๋กœ ๋ดค์„ ๋•Œ ํ›„๋ณด ๊ฐ„์„ฑ ์ค‘ ๋น„์šฉ์ด ๋‚ฎ์€ ๊ฒƒ ์„ ํƒ

 

์ˆœ์„œ๋Š”

 

1. ์•„๋ฌด ์ •์  ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•˜์—ฌ MST์— ์ถ”๊ฐ€

 

2. MST์™€ ์ง์ ‘ ์—ฐ๊ฒฐ๋œ ์™ธ๋ถ€์˜ ์ •์  ์ค‘ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์ •์ ์„ MST์— ์ถ”๊ฐ€

 

3. ๋ชจ๋“  ์ •์ ์ด MST์— ์ถ”๊ฐ€๋  ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณต

 

์–ด๋–ป๊ฒŒ ํ›„๋ณด ๊ฐ„์„ ๋“ค ์ค‘ ๊ฐ€์žฅ ์งง์€ ์• ๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ์„๊นŒ?

 

 

min-heap์„ ํ™œ์šฉํ•˜๋ฉด ๋จ

 

pseudo code๋ฅผ ์‚ดํŽด๋ณด๋ฉด

 

mst = []
Q = min_heap()
Q.enqueue((0, 0, None)) # ์ˆœ์„œ๋Œ€๋กœ weight, node, MST์•ˆ์˜ ๋‚˜์™€ ์—ฐ๊ฒฐ๋œ node
S = {}

while Q is not empty :
	w, u, p = Q.dequeue()
    
    if u in S : continue # ์ด๋ฏธ MST์— ๋“ค์–ด๊ฐ”๋‹ค๋Š” ๋œป
    
    S.add(u)
    mst.append((p, u))
    
    for v, w_uv in neighbors(u) :
    	if v not in S :
        	Q.enqueue((w_uv, v, u))

 

Complexity Analysis

 

Space Complexity

 

  • ์ธ์ ‘๋ฆฌ์ŠคํŠธ ๊ทธ๋ž˜ํ”„ : O(|E| + |V|)

    => neighbors์—์„œ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ์“ฐ๋Š”๊ฒŒ ํšจ์œจ์ ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ์‚ฌ์šฉ

  • min-heap : O(|E|)

    => ๊ฐ„์„ ๋“ค์„ ๋‹ค ๋„ฃ์œผ๋ฏ€๋กœ

  • S : O(|V|)

    => ์ตœ๋Œ€ ํฌ๊ธฐ๊ฐ€ ์ •์ ์˜ ๊ฐœ์ˆ˜์ด๋ฏ€๋กœ

  • Total : O(|V| + |E|)

Time Complexity

 

  • min-heap : O(|E|log|E|)

    => ์œ„์—์„œ ๋‹ค๋ฃฌ ๋‚ด์šฉ๊ณผ ๋™์ผํ•˜๊ฒŒ O(|E|log|V|)๋กœ ๋ณผ ์ˆ˜ ์žˆ์Œ

    (min-heap์— ๊ฐ„์„  ๋„ฃ์„ ๋•Œ ์ตœ๋Œ€ log|E|๋ฅผ edge์ˆ˜์ธ |E| ๋งŒํผ ๋ฐ˜๋ณต)

 

Correctness Analysis

 

Kruskal's, Prim's Algorithm์˜ ์ •๋‹น์„ฑ?

 

 

์ „์ฒด ์ •์  ์ง‘ํ•ฉ V๋ฅผ S, V - S๋กœ ๋‚˜๋ˆด์„ ๋•Œ S์™€ V - S ์‚ฌ์ด๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ๊ฐ€์žฅ ์งง์€ ๊ฐ„์„ ์„ e๋ผ ํ•˜๋ฉด, e๋ฅผ ํฌํ•จํ•˜๋Š” MST๊ฐ€ ๋ฐ˜๋“œ์‹œ ์กด์žฌํ•จ

 

e๋ฅผ ํฌํ•จํ•˜์ง€ ์•Š๋Š” MST์ธ T๊ฐ€ ์กด์žฌํ•œ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž

 

e = (u, v) ์ผ ๋•Œ, MST์—์„œ u์™€ v์‚ฌ์ด์˜ ๊ฒฝ๋กœ P๋Š” ์œ ์ผํ•จ

 

=> P์—์„œ S์™€ V - S ์‚ฌ์ด๋ฅผ ์ง€๋‚˜๋Š” ๊ฐ„์„  e'์€ ์œ ์ผ 
(2๊ฐœ ์žˆ์œผ๋ฉด cycle)

 

e'์„ ์ง€์šฐ๊ณ  e๋ฅผ ์ถ”๊ฐ€ํ•œ T'๋Š” ๋˜๋‹ค๋ฅธ Spanning Tree์ธ๋ฐ

1. w(e') > w(e) ์ธ ๊ฒฝ์šฐ T๋Š” MST๊ฐ€ ์•„๋‹˜ (๋ชจ์ˆœ)
2. w(e') = w(e) ์ธ ๊ฒฝ์šฐ T'๋Š” e๋ฅผ ํฌํ•จํ•œ MST

๋ฐ˜์‘ํ˜•

'๐Ÿ”ฅ Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

L13 - Topological Sorting  (0) 2024.11.29
L12 - Single Source Shortest Paths  (0) 2024.11.28
L10 - Disjoint Sets  (0) 2024.11.22
L09 - Greedy Algorithms  (1) 2024.11.03
L07 - Selection  (4) 2024.10.13