10주차

기말에 힙, 퀵, avl

 

59, 78, 65, 23, 7, 25, 52, 49, 99, 80 10개를 순차적으로 넣을 때 avl 트리 만드는 과정

 

 

• DFS

 

인접 리스트를 이용한 dfs 탐색

adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1], [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]
n = len(adj_list)
visited = [0] * n


def dfs(v):
    visited[v] = 1
    print(v,' ', end = ' ')
    for i in adj_list[v]:
        if visited[i] == 0:
            dfs(i)

print("dfs")
for i in range(n):
    if visited[i] == 0:
        dfs(i)

0~9 번까지 차례로 dfs(i)를 호출하고 호출된 dfs(i)는 adj[i]에 있는 리스트 원소를 쭉 탐색한다

방문 안한 곳이면 계속 이어서 탐색하고 이미 탐색한 곳이면 넘어간다