1
2
3
4
5
matrix2list = lambda mat: [{v2 for v2, con in enumerate(graph[i]) if con} for v1 in range(len(mat))]
adj_mat = [[0, 1, 0],
           [1, 0, 1],
           [0, 1, 0]]
adj_list = matrix2list(adj_mat)

1
2
3
4
5
6
7
8
9
10
11
12
13
def dfs(graph, src):
  s         = [src]
  visited   = {src}
  traversal = [src]
  while s:
    cur_v = s.pop()
    for next_v in (v for v in graph[cur_v] if v not in visited):
      s.append(next_v)
      visited.add(next_v)
      traversal.append(next_v)
  return traversal

traversal = dfs(adj_list, src)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import deque

def bfs(graph, src):
  q         = deque([src])
  visited   = {src}
  traversal = [src]
  path      = {src: [src]}
  while q:
    cur_v = q.popleft()
    for next_v in (v for v in graph[cur_v] if v not in visited):
        q.append(next_v)
        visited.add(cur_v)
        traversal.append(cur_v)
        path[next_v] = path[cur_v] + [next_v]
  return traversal, path

traversal, path = bfs(adj_list, src)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from heapq import heappush, heappop
from math import inf

def dijkstra(graph, src):
    dists = {v: inf for v in graph}
    paths = {v: [] for v in graph}
    q     = []
    heappush(q, [0, [src]])  # (dist, [path])

    while q:
        cur_dist, cur_path = heappop(q)
        if cur_dist < dists[cur_path[-1]]:
            dists[cur_path[-1]] = cur_dist
            paths[cur_path[-1]] = cur_path
            for next_v, dist in graph[cur_path[-1]]:
                heappush(q, (cur_dist + dist, cur_path + [next_v]))
    return dists, paths

# graph = {1: [(2, 4)]}  # weight(1 -> 2) = 4
dists, paths = dijkstra(graph, src)

1
2
3
4
5
6
7
8
9
from math import inf

def floyd_warshall(graph):
    dists = [len(graph)*[inf] for _ in len(graph)]  # node should start with 0
    for w in graph:  # v1 -> w -> v2
      for v1, v2 in product(graph, graph):
        dists[v1][v2] = min(dists[v1][v2], dists[v1][w] + dists[w][v2])
    return dists
dists = floyd_warshall(graph)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def kruskal(graph):
    def find_parent(parents, x):
        if parents[x] != x:
            parents[x] = find_parent(parents, parents[x])
        return parents[x]
    def union_parents(parents, a, b):
        pa, pb = find_parent(parents, a), find_parent(parents, b)
        parents[pb] = pa if pa < pb else parents[pb]
        parents[pa] = pb if pa > pb else parents[pa]

    edges = []
    for v1 in graph:
        for v2, w in graph[v1]:
            edges.append((w, v1, v2))

    parents = list(range(len(graph)))
    dist = 0
    for w, v1, v2 in sorted(edges):
        if find_parent(parents, v1) != find_parent(parents, v2):
            union_parents(parents, v1, v2)
            dist += w
    return dist

dist = kruskal(graph)

1
2
3
4
def selection_sort(arr):
  for sel in range(len(arr)):
    argmin = min(range(sel, len(arr)), key=lambda i: arr[i])
    arr[sel], arr[argmin] = arr[argmin], arr[sel]

1
2
3
4
5
6
7
def insertion_sort(arr):
  for sel in range(1, len(arr)):
    for i in range(sel, 0, -1):
        if arr[i-1] > arr[i]:
            arr[i-1], arr[i] = arr[i], arr[i-1]
        else:
            break

1
2
3
4
5
6
7
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot, *tail = arr
    left  = [x for x in tail if x <= pivot]
    right = [x for x in tail if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

1
2
3
4
5
6
7
8
def count_sort(arr):
    cnt = (max(arr)+1)*[0]
    for x in arr:
        cnt[x] += 1
    rst = []
    for x, cnt in enumerate(cnt):
        rst += cnt*[x]
    return rst

1
2
3
4
5
6
7
8
9
10
11
def binary_search(arr, target):
    s, e = 0, len(arr)-1
    while s <= e:
        mid = (s+e)//2
        if arr[mid] == target:
            return mid
        elif target < arr[mid]:
            e = mid-1
        elif arr[mid] < target:
            s = mid+1
    return -1

1
2
3
4
5
6
7
8
cache = 100*[None]

def fibo(x):
    if x <= 2:
        cache[x] = 1
    elif cache[x] is None:
        cache[x] = fibo(x-1) + fibo(x-2)
    return cache[x]

1
2
3
4
5
6
7
cache = 100*[None]

def fibo(x):
    cache[1] = cache[2] = 1
    for i in range(3, x+1):
        cache[i] = cache[i-1] + cache[i-2]
    return cache[x]

1
2
3
4
5
6
def solution(arr):
    cache = len(arr)*[None]
    cache[1] = cache[2] = 1
    for i in range(3, len(arr)):
        cache[i] = max(cache[i-1], cache[i-2] + arr[i])
    return cache[len(arr)-1]