[알고리즘] 10주차 2차시

dkswlgus00·2021년 11월 25일
0

알고리즘

목록 보기
17/23

Chap08. Graph Optimization Problems and Greedy Algorithms

Graph Optimization Problems

Prim's Algorithm

Greedy를 이용하여 minimum spanning tree를 찾는 알고리즘1

  1. 임의의 vertex를 starting vertex로 선택(minimum spanning tree의 root)
  2. 각 iteration마다 edge를 추가, edge의 반대편 vertex를 트리에 추가
    이때 edge는 minimum weight의 edge를 선택함 - greedy algorithm
  3. 각 vertex마다 disjoint categories로 상태 표시
  • Tree vertices: 그래프에서 생성할 minimum spanning tree에 포함되는 vertex
  • Fringe vertices: tree vertex가 될 수 있는 후보. 즉, minimum spanning tree에 인접한 vertices
  • Unseen vertices: tree도 fringe도 아닌 vertices

Example :: The Algorithm in Action

O(n)회 삽입, 삭제 발생

PrimMST(G,n) // OUTLINE
	Initialize all vertices as unseen.		// O(n) time
	Select an arbitrary vertex s to start the tree; reclassify it as tree.
	Reclassify all vertices adjacent to s as fringe.
    
	While there are fringe vertices;		// O(n)번 수행
		Select an edge of minimum weight between
			a tree vertex t and a fringe vertex v;	// O(n) time
		Reclassify v as tree; add edge tv to the tree;
		Reclassify all unseen vertices adjacent to v as fringe.	// deg(v)

*min-priority queue

sorted sequenceunsorted sequenceheap
insert()O(n)O(1)O(lg n)
removeMin()O(1)O(n)O(lg n)
decreasekey()O(n)O(1)O(lg n)


일반적으로 heap을 이용하여 구현하는 것이 더 효율적
Example1 :: unsorted sequence를 이용하여 계산

size=n인 두 개의 array를 이용 - status, distance
1. status는 모두 unseen vertex로, distance는 모두 infinite로 초기화 - O(n) time
2. status와 distance 업데이트, 각 iteration마다 O(n) time

PrimMST(G,n) // OUTLINE
	Initialize all vertices as unseen.		// O(n) time
	Select an arbitrary vertex s to start the tree; reclassify it as tree.
	Reclassify all vertices adjacent to s as fringe.
    
	While there are fringe vertices;		// O(n)번 수행
		Select an edge of minimum weight between
			a tree vertex t and a fringe vertex v;	// O(n) time
		Reclassify v as tree; add edge tv to the tree;
		Reclassify all unseen vertices adjacent to v as fringe.	// deg(v)

O(n2n^2) time using the unsorted sequence

Example2 :: heap를 이용하여 계산

PrimMST(G,n) // OUTLINE
	Initialize all vertices as unseen.		// O(n) time
	Select an arbitrary vertex s to start the tree; reclassify it as tree.
	Reclassify all vertices adjacent to s as fringe.
    
	While there are fringe vertices;		// O(n)번 삽입, 삭제
		Select an edge of minimum weight between
			a tree vertex t and a fringe vertex v;	// O(n) time
		Reclassify v as tree; add edge tv to the tree;
		Reclassify all unseen vertices adjacent to v as fringe.	// deg(v)

삽입과 삭제에 의해 O(nlgn) time
하나의 edge마다 두 번의 decreasekey() 수행 - O(m)번
따라서 O(nlgn + mlgn) <= O(mlgn) time

O(n2n^2) time using the unsorted sequence
O(mlgn) time using a heap

입력으로 주어진 그래프의 m의 size가 O(n)에 가까운 sparse graph일 때는 heap이,
m의 size가 O(n2n^2)에 가까운 dense graph일 때는 unsorted sequence가 효율적

Kruskal's Algorithm

Greedy를 이용하여 minimum spanning tree를 찾는 알고리즘2

KruskalMST(G,n) // outline
	R = E // R is remaining edges
	F = none // F is forest edges
	while (R is not empty)
		Remove the lightest (shortest) edge, vw, from R;
        
       		// cycle이 발생하지 않을 때만 MST 추가
            	// union-find ADT(disjoint set)
		if (vw does not make a cycle in F)	
			Add vw to F;
	return F ;

O(nlgn) time에 수행

edge의 weight를 기준으로 작은 edge부터 MST에 추가

  1. sorting을 이용하여 계산
    edge에 대해 정렬
KruskalMST(G,n) // outline
	R = E	// sorting: O(mlgm) time
	F = none 
	while (R is not empty)
		Remove the lightest (shortest) edge, vw, from R;
		if (vw does not make a cycle in F)	
			Add vw to F;
	return F ;

O(mlgm) time

  1. min-heap을 이용하여 계산
    edge의 정보를 모두 heap에 삽입하여 관리
KruskalMST(G,n) // outline
	R = E	// m개 edges, O(m) time (bottom-up heap construction)
	F = none 
	while (R is not empty)	// O(m) 번
		Remove the lightest (shortest) edge, vw, from R;	// O(lgm) time
		if (vw does not make a cycle in F)	
			Add vw to F;
	return F ;

O(mlgm) time
* m=O(n2n^2), O(mlgm) = O(mlgn2n^2) = O(2mlgn) = O(mlgn)

Data Structure for Kruskal's Algorithm

O(nlgn) time보다 빠르게 수행

  • find(u): set id(leader) 반환
  • union(u,v): u를 포함하는 집합과 v를 포함하는 집합이 서로 다르면 하나의 집합으로 union, 두 key값(u,v) 중 작은 값을 set id로 설정


mMSTm_{MST} = n-1이 될 때까지 수행

profile
콤퓨타공학과

0개의 댓글