Paris on the chair

Tree algorithms

• Tree center(s) - O(V+E)   - - - - - - - - - - - - - - - - > Here !
• Tree diameter - O(V+E) 
•  Rooting an undirected tree - O(V+E)
• Lowest Common Ancestor (LCA, Euler tour) - O(1) queries, O(nlogn) preprocessing

Tree Center(s) 개요 

Graph 에서 Center를 찾는 알고리즘이다. 다만, 제한조건이 존재하는데 그래프는 Undirected 하고 asyclic 해야한다. 

그래프에서는 Undirected & asyclic 조건을 만족하면 'Tree'라 정의하기 때문에 Tree Center(s)라 불린다. 

아래 예시를 보자.

=> Graph에서 가장 긴 Path의 중점이 Center(s) 이다.

How to Solve ?

Tree의 Center를 찾기 위한 방법이 상당히 재밌는데,

Leaf 노드들을 bfs로 쳐냄으로써 Center(s)를 찾아낸다.

다시말해, degree가 1인 leaf들을 bfs로 쳐냈을 때, 마지막에 잔재했던 leaf node(s)가 Center가 된다. 

### pseudo code 


def findTreeCenters(n: int, graph: dict[List[]]) -> List:
	"""
    	@param n : the size of vertexes.
    	@param graph : adjacency list.
        			   graph는 asyclic, undirected 해야함.
        	e.g. 
            	graph[1] = [0,2,3]
                
                    0 --- 1 --- 2
                          |
                          |
                          3
             
    """
	
    degree = [0] * n
    for i in range(n):
    	degree[i] = len(graph[i])
    
    ## 쳐내고자 하는 leaf들을 찾는다.
    leaves = []
    for node in range(n):
    	if degree[node] == 1:
        	leaves.append(node)
    
     ## center를 찾기 위한 반복문. 
     ## 지속해서 leaf를 쳐낸다.
     count = len(leaves)
     while count < n:
     	new_leaves = []
        for leave in leaves:
	        ## leave를 쳐냈으므로 degree는 0이 돼야함.
        	degree[leave] = 0 
            for neighbor in graph[leave]:
            	degree[neighbor] -= 1
    			if degree[neighbor] == 1:
                	new_leaves.append(neighbor)
       	leaves = new_leaves
     	count += len(leaves)
        
     return leaves

어디에 사용될까 ?

Identifying Critical Nodes: The center(s) of a tree often represent the most critical or central nodes in the network, which may play crucial roles in maintaining the connectivity of the graph.

Rooting Trees: In computer science and data structures, you might need to root a tree at a specific node. The center of the tree can be used as a good root that balances the tree.

Network Design: Finding the center(s) of a network can help in designing efficient communication networks or transportation systems.

 Tree Center는 특히 네트워크에 유용하게 사용될 수 있을 듯 하다. 

추천 문제 

https://leetcode.com/problems/minimum-height-trees/

• Topological sort (acyclic graph, adjacency list) - O(V+E)

Topological Sort (위상정렬)

그래프는 정점들을 간선을 통해 모든 관계를 표현한다.

 위상 정렬은 그래프에서 정점을 정렬함을 의미한다.

위상정렬이 Optimal 을 만족하기 위해서는 

아래 제약조건을 만족해야한다.

1. 방향성이 존재 (Directed)

2. Cycle이 존재하지 않아야 한다. (Asyclic)

How to solve ?

핵심은 'In degree'가 0인 정점을 출력하는 것.

구현은 아래  1 -> 2 패턴을 반복한다.

1. In degree가 0인 정점들을 우선 정렬한다.

(In degree  == 0 : 다른 정점의 Dependency가 없기 때문에 출력해도 괜찮은 상태를 의미.)

2. In degree를 갱신한다.

(이미 정렬한 정점 관련 Dependency 갱신)

Data Structure는 Stack이든 Queue든 차이가 없다.

In degree 가 0인 정점을 우선적으로 채택한다는 단순성에서

Greedy Algorithm으로 분류하고 싶다.

##########################
###### pseudo code. ######
##########################

def TopologicalSort(graph, V: int) -> List:
""" @param
    graph: adjacency-list. or 2d mat. assumed adjacency-list in this pseudo.
    
           i.e. 
              if you construct graph as adjacency-list -> O(E+V)
              if you construct graph as 2D-Mat -> O(V^2)	

           e.g. graph[0] = [1,2,3] :    3
                                        ^
                                        |
                                        0 -> 1
                                        ↓
                                        2
            

    V: the number of vertexes

"""
    res = [] # sort된 list를 반환한다.
    
    # Edge로부터 Direction을 받는 노드들의 개수를 초기화
    in_degree = [0] * V
    for from, edge in enumerate(graph):
        for to in edge:
            in_degree[to] += 1
    
    visit = [False] * V
    q = Queue() # this can be replaced with 'list', 'stack' ..
    for n in Range(V):
        if in_degree[n] == 0:
            visited[n] = True
            q.push(n)
    
    while !q.empty():
    	cur_node = q.get()
        res.append(cur_node)
        
        for adj_node in graph[cur_node]:
            in_degree[adj_node] -= 1
            if in_degree[adj_node] == 0:
            	q.push(adj_node)
               
    return res

• Bellman-Ford (adjacency list, negative cycles) - O(VE)
• Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

Bellman Ford Algorithm Key Features

1. Start 노드를 규정하고 다른 모든 노드들의 최단 거리를 계산하는 알고리즘이다.

( SSSP Algorithm; Single Source Shortest Path)

2. 음의 간선이 존재해도 동작한다.

Brief Steps for finding shortest Path 

1. src (start) 이외의 모든 노드의 비용을 양의 무한대로 초기화 한다.

2. v-1 회만큼 모든 Edge를 순회하며 아래 조건을 반복한다. (이 단계를 'relaxation' 이라 함)

- if dist[edge.from] + edge.cost <  dist[edge.cost]

             dist[edge.to] = dist[edge.from] + edge.cost

3. (2) 조건을 한번 더 반복하여 relaxation이 가능한 노드를 확인한다.

* relaxation 과정의 outer-loop는 왜 v-1 번 수행하는가 ? 

->  모든 Edge에 대해 한번의 순회의 계산은, Path에서 최소 1번의 Edge를 거치는 Shortest Path의 안정화를 보장한다. 

즉, i번의 순회는 최소 i개의 edge를 거치는 Shorterst Path를 안정화 보장시킨다는 의미이고,

Path는 최대 V-1개의 Edge를 갖을 수 있으므로 outer loop는 v-1 회 반복해야한다.

• Bellman-Ford (adjacency list, negative cycles) - O(VE)

# pseudo code 

def bellmanFord(src: int, edges: List[Edge]) -> list:
    distances = [POSITIVE_INF] * n
    distances[src] = 0
    
    # relaxation
    for _ in range(v-1): # v is the number of vertexies
        for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = distances[edge.from] + edge.cost
     
    # detect negative-cycle.
    for _ in range(v-1): # v is the number of vertexies
        for edge in edges:
            # The node is in negative-cycle if it is possible to relaxation
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = NEGATIVE_INF

    return distances

Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

최적화 아이디어는 굉장히 간단하다. 

앞서 설명했듯, 순회문이 V-1인 이유는 Worst Case를 염두에 두기 때문이다.

이를 감지하는 Boolean을 두면 최적화 여지가 있다.

# pseudo code 

def bellmanFord(src: int, edges: List[Edge]) -> list:
    distances = [POSITIVE_INF] * n
    distances[src] = 0
    bool relaxed # here !
    
    # relaxation
    for _ in range(v-1):
    	relaxed = False # here !
    	for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = distances[edge.from] + edge.cost
                relaxed = True # here ! 
     	
        if relaxed == False: # relaxation 이 없었으면, 순회문을 반복할 이유가 없다.
            break

    # detect negative-cycle.
    for _ in range(v-1):
    	relaxed = False
        for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = NEGATIVE_INF
                relaxed = True # here !
                
        if relaxed == False: # here !
            break

    return distances

• Dijkstra Shortest Path (Just use priority queue + 2d Matrix) - O(V^2 * log(V)) => stay here !
• Dijkstra Shortest Path (Just use priority queue + adjancylist) - O(Elog(V)) - - - -  basic way => stay here !
• Dijkstra shortest Path (Indexed Priority Queue + adjancylist + D-arr heap) - O(ElogE/V(V))
• Dijkstra shortest Path (fibonacci heap) - O(E+Vlog(V))

Dijkstra Key Features

1. Start 노드 규정하고 다른 모든 노드들의 최단 거리를 계산하는 알고리즘이다.

2. 다익스트라는 Greedy에 기반한 알고리즘으로 모든 그래프 Edge는 음수가 되어서는 안된다. 

Dijkstra Shortest Path (priority queue + 2D Matrix)

# pseudo code

# graph[A][B] means the distance from A to B.
def dijkstra(start, graph: List[List[]]) -> Float:
    distance = [INF] * n # n is the size of node [INF,INF,INF ...]
    distance[start] = 0
    
    # you should implement pq with key-value pair
    # key is the node index (unique)
    # value is the given distance 
    # pq should build min-heap based on value.
    # then, the pq tell you which node to visit next (greedy!)
    pq = priority_queue()
    pq.insert((start,0)) 
    
    while !pq.empty():
    	cur_node, dist = pq.get()
        pq.pop() # the get() of python implicitly runs pop(), but most aren't.
        
        if distance[cur_node] < dist: # the better path is already calculated
            continue
            
        for (int adj_node_idx=0; adj_node_idx < n; adj_node_idx++):
            if graph[cur_node][adj_node_idx] == INF:
                continue
    
            new_cost = dist + graph[cur_node][adj_node_idx]
            if new_cost < distance[adj_node_idx]:# unnecessary if not in this caluse, the better path already is in the pq.
                distance[adj_node_idx] = new_cost
                pq.push(adj_node_idx, new_cost)
                
     return distance

만약 반환 값으로 최단 경로[List]가 필요한 경우 아래와 같다.

# pseudo code

# graph[A][B] means the distance from A to B.
def dijkstra(start, graph: List[List[]]) -> list:
    distance = [INF] * n 
    distance[start] = 0
    get_parent = {start: NONE} # here !

    pq = priority_queue()
    pq.insert((start,0)) 
    
    while !pq.empty():
    	cur_node, dist = pq.get()
        pq.pop()
        
        if distance[cur_node] < dist: 
            continue
            
        for (int adj_node_idx=0; adj_node_idx < n; adj_node_idx++):
            if graph[cur_node][adj_node_idx] == INF:
                continue
    
            new_cost = dist + graph[cur_node][adj_node_idx]
            if new_cost < distance[adj_node_idx]:
                distance[adj_node_idx] = new_cost
                get_parent[adj_node_idx] = cur_node # here !
                pq.push(adj_node_idx, new_cost)
                
     return get_parent

# usage example
def main():
    get_parent = dijkstra(start,Graph)
    path = []
    node = target # the target node_index that you want to get path from start
    while node is not NONE:
    	path.append(node)
        node = get_parent[node]
    path = path[:-1]

Dijkstra Shortest Path (priority queue + Adjacency List)

# pseudo code 

def dijkstra(start: int, adjacency_node: List[List[]], adjacency_dist: List[List[]]):
    """
    e.g.
        adjacency_node[0] = [1,5]
        adjacency_cost[0] = [12,23]

        node idx 0 -> 1 , 0 -> 5 로 갈 수 있으며 각각의 distance는 12,23
    """
    distance = [INF] * n # n is the size of the node
    distance[start] = 0
    
    # key (node idx) - value (distance) 
    # min_heap adhered to value
    pq = priority_queue() 
    pq.insert((start,0))
    
    while !pq.empty():
    	cur_node, cur_dist = pq.get()
        pq.pop()
        
        # neat optimization 
        if distance[cur_node] < cur_dist:
            continue
 
        for idx, adj_node in enumerate(adjacency_list[cur_node]):
            adj_cost = adjacency_dist[cur_node][idx]
            new_cost = cur_dist + adj_cost
            if distance[adj_node] > new_cost: 
                distance[adj_node] = new_cost
                pq.insert((adj_node,new_cost))
                
     return distance

포스팅 목적

- heapify 이해하기

- siftup , siftdown 이해하기

- build Heap Time Complexity : O(n) 이해하기

Heap 을 구성하는데 O(n)의 시간복잡도를 갖음을 이해하는데 앞서 가장 간단한 방법을 생각해봅시다.

힙 아키텍쳐에 임의의 순서로 나열된 n개의 데이터 셋을 저장하기 위해서

우리는 데이터 셋을 순차적으로 힙에 삽입하는 방법을 생각할 수 있을 것입니다.

1. 힙에 순차적인 데이터 삽입 시간복잡도  : O(nlogn)

결론적으로 n 개의 데이터를 힙 자료구조에 순차적으로 삽입할 경우 O(nlogn) 시간복잡도를 갖습니다. 

직관적으로 볼때 힙의 삽입은 O(logn) 의 시간복잡도를 갖고 , n 개의 데이터를 순회하며 삽입하기 때문에

총 시간복잡도는 O(nlogn)를 갖는다고 여길 수 있지만, 이는 옳바른 접근이 아닙니다.

힙의 시간복잡도 n은 힙을 구성하는 size를 의미하기 때문에 n개의 데이터를 순차적으로 삽입함에 따라

힙을 구성하는 n은 1~n 까지 순차적으로 증가해야 합니다.

결론적으로 O(log1 +log2 + log3 + ....  + logn) 의 시간복잡도를 갖게될 것 입니다.

이는 Stirling's approximation 에 의해 O(nlogn)로 계산됩니다.

2. Heapify(Sift Down) 를 이용한 시간복잡도 : O(n) 

임의의 n개 데이터를 heap 아키텍쳐로 바꾸는 과정은 2가지로 접근할 수 있습니다.

1. Sift Up Operation

2. Sift Down Operation 

해당 글을 이해하기 전에 용어를 살펴봅시다. 

- Sift up

Sift up은 heap에 데이터를 삽입하는 과정에서 발견할 수 있습니다.

heap에 데이터를 삽입하는 경우, 삽입된 데이터는 최초로 완전이진트리의 leaf 부분에 위치할 것 이며,

이후, 삽입 노드의 부모 노드 값과 비교연산을 수행하며 Swap이 발생할 것 입니다.

위에서 발견할 수 있듯이 Sift Up 은

주어진 노드의 부모 노드와의 비교연산을 수행하여 이를 만족시키거나, 그렇지 않으면 root에 도착할 때 까지 Swap하는 방법을 의미합니다.

- Sift down

반대로 Sift down은 heap에서 데이터를 삭제하는 과정에서 발견할 수 있습니다.

heap에서 데이터를 삭제하는 경우, 완전이진트리(힙)의 leaf 노드를 root로 이동시켜 child's의 노드와 비교연산을 수행하여, heap property를 만족하지 않으면 swap할 것 입니다.

Sift Down은 

주어진 노드의 child node's 중 key가 큰 값(or 작은 값) 과 비교연산을 수행해 property를 만족하거나, 그렇지 않으면 leaf에 도착할 때 까지 swap 하는 과정을 의미합니다.

1. Sift Up 을 이용한 build heap 예시

이 방법은 힙에 순차적으로 데이터를 삽입하는 방법과 거의 유사합니다.

(sift up operation은 힙에 데이터 삽입에서 발생하기 때문)

예시를 통해 이해해 보겠습니다. (max heap을 가정)

위와 같은 무작위의 데이터 set 이 있을때, 앞에서부터 순차적으로 접근합니다.

(1)

처음 data 4는 sift up의 definition에 따라 부모 노드와 값을 비교해야 합니다. 해당 부모 노드가 존재하지 않으므로 연산은 종료됩니다.

(2)

이후 삽입된 2는 sift up 연산에 의해 부모 노드와 비교가 일어나고 주어진 비교연산을 만족하므로 swap이 일어나지 않습니다.

(3)

삽입된 6 node의 데이터와 부모 노드간 비교연산을 수행합니다. heap property를 만족시키기 위해 swap이 발생합니다.

이후 swap된 6 은 root 에 존재하므로 재귀적인 연산을 종료합니다.

(4)

삽입된 8 과 부모 노드 2 간 비교연산을 수행합니다. 여기서 heap property를 만족하기 위해 swap이 발생합니다.

위에 정의했듯이 sift up 연산은 비교연산을 만족하거나, root에 존재할 때 까지 swap이 발생합니다.

(그렇기에 시간복잡도는 O(logn)) 

8 은 부모노드 6과 비교연산을 수행하며 이는 max heap property를 만족시키지 않으므로 또 한번의 swap이 발생할 것 입니다.

8은 root 에 존재하게 되므로 sift up 연산을 종료합니다.

2. Sift Down 을 이용한 build heap 예시

sift down은 위와 같은 방향으로 수행될 수 있습니다. 

(1) 우선 주어진 data set에 대응하는 완전 이진트리를 먼저 그리겠습니다.

(2) 위에서 정의한 정의를 떠올려봅시다.

역방향으로 순차적으로 순회할 때 7,8,6 데이터는 leaf 에 존재하므로 swap을 수행하지 않습니다.

(3)

2의 경우 sift down에 의해 child node 중 큰 값 8과 비교 연산을 수행하고 swap이 발생합니다.

swap 발생 이후, 2는 leaf에 존재하므로 재귀적인 sift down 연산을 종료합니다.

(4) 

마지막으로 4 node는 child 중 값이 큰 8 데이터와 비교 연산을 수행하며 swap이 발생합니다.

이후, 4 데이터는 재귀적으로 다시 child node 중 큰 데이터와 비교연산을 수행하고, swap이 발생합니다.

4는 leaf에 존재하므로 sift down 연산을 종료합니다.

Build Heap 직관 및 결론

결론적으로 말하면 build Heap을 Sift Up 을 통해 구성하면 O(nlogn)의 시간복잡도를 갖으며, 

Sift Down 을 통해 구성하면 O(n)의 시간복잡도를 갖습니다.

수학적 수식을 보기전에 이를 직관으로 이해해 봅시다. 

Sift Up과 Sift Down은 둘 다 O(logn)의 시간 복잡도를 갖습니다. 하지만 그 과정을 좀 더 면밀히 살펴보면

Sift Up의 시간복잡도는 주어진 노드부터 root Node 까지의 높이 로 볼 수 있으며

Sift Down의 시간복잡도는 해당 노드부터 leaf Node 까지의 높이입니다. 

힙을 구성하는 완전이진트리는 그 성질에 의해 약 n/2 개의 노드는 leaf 노드에 존재하게 됩니다.

그러므로, Sift Down Operation으로 Heap을 설계하는 것이 더욱 효율적일 것임을 추론할 수 있습니다.

Sift Down Time Complexity proof

해당 Sift Down의 시간복잡도는 Taylor 급수를 기반으로 증명될 수 있으며 O(n) 의 시간복잡도를 갖습니다.

heap STL의 시간복잡도를 살펴보면 O(n)의 시간복잡도를 갖음을 확인할 수 있으며, 내부적으로 Sift Down으로 구현됨을 추정할 수 있습니다.