코드 외워야될거

dfs, bfs, 크루스칼, 프림, 다잌

 

DFS

for i in range(m) :
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

print(f"연결된 간선 정보 \n{arr[1:]}")


def dfs(v):
        visited[v] = True
        print(v, ' ', end = '')
        for i in arr[v]:
            if not visited[i]:
                dfs(i)

 

BFS

 

def bfs(node):
    queue = []
    visited[i] = 1
    queue.append(i)
    while len(queue) != 0:
        v = queue.pop(0)
        print(v)
        for i in adj_list[v]:
            if not visited[i]:
                visited[i] = true
                queue.append(i)

 

크루스칼

 

weight = [(0,1,9), (0,2,10), (1,3,10), (1,4,5),
          (1,6,3), (2,3,9), (2,4,7), (2,5,2),
          (3,5,4), (3,6,8), (4,6,1), (5,6,6)]

weight.sort(key = lambda  t: t[2])
mst = []
N = 7
p = [] * N

for i in range(N):
    p.append(i)

def find(u):
    if u != p[u]:
        p[u] = find(p[u])
    return p[u]

def union(u,v):
    root1 = find(u)
    root2 = find(v)
    p[root2] = root1

tree_edges = (0)
mst_cost = 0

while True:
    if tree_edges == N-1:
        break

    u, v, wt = weight.pop(0)
    if find(u) != find(v):
        union(u,v)
        mst.append((u,v))
        mst_cost += wt
        tree_edges += 1


print('최소 신장 트리: ', end='')
print(mst)
print('최소 신장 트리 가중치: ', mst_cost)

 

프림

 

import sys

N = 8
s = 0
g = [None] * N
g[0] = [(1, 1), (3, 2)]
g[1] = [(0, 1), (2, 4), (3, 3), (4, 1), (5, 6)]
g[2] = [(1, 4), (5, 1), (6, 1), (7, 2)]
g[3] = [(0, 2), (1, 3), (4, 5)]
g[4] = [(1, 1), (3, 5), (6, 2)]
g[5] = [(1, 6), (2, 1), (7, 9)]
g[6] = [(2, 1), (4, 2), (7, 1)]
g[7] = [(2, 2), (5, 9), (6, 1)]

visited = [False] * N
D = [sys.maxsize] * N
D[s] = 0
previous = [None] * N
previous[s] = s

for k in range(N):
    m = -1
    min_value = sys.maxsize
    for j in range(N):
        if not visited[j] and D[j] < min_value:
            min_value = D[j]
            m = j

    visited[m] = True

    print(f"\nIteration {k + 1}: Selected vertex {m}")
    for w, wt in list(g[m]):
        if not visited[w]:
            if wt < D[w]:
                D[w] = wt
                previous[w] = m

    print("Visited:", visited)
    print("D:", D)
    print("Previous:", previous)

print('\n최소신장트리: ', end='')
mst_cost = 0
for i in range(1, N):
    print('(%d, %d)' % (i, previous[i]), end='')
    mst_cost += D[i]
print('\n최소신장트리 가중치 : ', mst_cost)

 

 

다잌

 

import sys
N = 8
s = 0
g = [None] * N
g[0] = [(1,1), (3,2)]
g[1] = [(0,1), (2,4), (3,3), (4,1), (5,6)]
g[2] = [(1,4), (5,1), (6,1), (7,2)]
g[3] = [(0,2), (1,3), (4,5)]
g[4] = [(1,1), (3,5), (6,2)]
g[5] = [(1,6), (2,1), (7,9)]
g[6] = [(2,1), (4,2), (7,1)]
g[7] = [(2,2), (5,9), (6,1)]

visited = [False] * N
D = [sys.maxsize] * N
D[s] = 0
previous = [None] * N
previous[s] = s

for k in range(N):
    m = -1
    min_value = sys.maxsize
    for j in range(N):
        if not visited[j] and D[j] < min_value:
            min_value = D[j]
            m = j
    visited[m] = True
    for v, wt in list(g[m]):
        if not visited[v]:
            if D[m] + wt < D[v]:
                D[v] = D[m] + wt
                previous[v] = m


print('정점', s, '으로 부터 최단 거리 :')
for i in range(N):
    if D[i] == sys.maxsize:
        print(s, '와 ', i, '사이에 경로 없음')
    else:
        print('[%d, %d]' % (s, i), '=', D[i])

print('정점', s, '으로 부터 최단 경로 :')
for i in range(N):
    back = i
    print(back, end = '')
    while back != s:
        print(' <-', previous[back], end = '')
        back = previous[back]
    print()