[Algorithm] 그래프(graph)

for tc in range(1, int(input()) + 1):
    N, E = map(int, input().split())  # N은 마지막 정점의 번호, E는 간선의 개수이다.
    G = [[] for _ in range(N + 1)]  # 정점 0번부터 N번까지의 인접리스트 생성한다.
    for _ in range(E):
        u, v, w = map(int, input().split())  # u: 구간 시작지점, v: 구간 끝지점, w: 구간 거리 (가중치)
        # 가중치 유향 그래프
        G[u].append((v, w))  # G[시작 정점 번호] = (도착 정점 번호, 가중치)
 
    # 거리를 저장하는 배열
    D = [0xffffff] * (N + 1)
    D[0] = 0  # 출발점 설정
 
    # 모든 간선에 대해서 (간선 완화)
    while True:
        flag = True
        for u in range(0, N + 1):  # 모든 정점들을 순회
            for v, w in G[u]:     # 정점의 인접 정점을 순회
                if D[v] > D[u] + w:
                    D[v] = D[u] + w
                    flag = False
        # for문을 통해서 D 값의 변경이 없다면 최적해를 찾은 것이다.
        if flag:
            break
    print(f'#{tc} {D[N]}')
복사

def BFS(s, G):
    D = [0xfffff] * (V + 1)           ⭐ D의 각 값을 큰 값으로 초기화
    P = [i for i in range(V + 1)]    
    D[s] = 0                          ⭐ 출발점의 값을 0으로 초기화(부모가 없다는 말)
    Q = [s]
 
    while Q:
        u = Q.pop(0)
        for v, w in G[u]:
            if D[v] > D[u] + w:       ⭐ 최단 거리가 갱신되면 Q에 v를 넣는 것이 중요
                D[v] = D[u] + w
                P[v] = u
                Q.append(v)
    print()
 
# ----------------------------------------------
 
import sys
sys.stdin = open("weighted_graph.txt", "r")
 
 
V, E = map(int, input().split())
G = [[] for _ in range(V + 1)]
 
 
for i in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
 
BFS(1, G)
 
print(D[1:])
print(P[1:])
복사

V, E = map(int, input().split())
G = [[] for _ in range(V+1)]
 
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
# 시작점으로부터의 최단거리 배열 D 만들고 초기화
D = [0xffffff] * (V+1)
# 최단 경로 트리 저장, 노드까지의 최단경로에 이르는 부모노드번호 저장, 필수가 아닌 선택
P = [0] * (V+1)
# 시작점을 1로 가정하고 값을 0으로 설정(시작점~시작점 최단거리 : 0)
D[1] = 0
 
# 시작점 key 값을 Q에 등록
Q = [1]
 
while Q:
    u = Q.pop(0)
 
    # 기준점 u와의 모든 인접정점 v와 u-v간 가중치 w에 대하여
    for v, w in G[u]:
        # 시작점 ~ v의 기존 최단거리보다 시작점 ~ u까지의 최단거리 + u~v 가중치가 더 작으면
        if D[v] > D[u] + w:
            D[v] = D[u] + w       # v까지의 최단거리를 재정의해주고
            P[v] = u              # v의 최단경로 부모노드를 u로 설정
            Q.append(v)           # v를 기준점으로 인접정점 최단거리 재확인해야 함
 
# 0번 인덱스는 의미 X
print(D[1:])
복사

def DFS_SHORTEST(u):
    for v, w in G[u]:
        if D[v] > D[u] + w:
            D[v] = D[u] + w
            P[v] = u
            DFS_SHORTEST(v)
 
 
V, E = map(int, input().split())
G = [[] for _ in range(V + 1)]
 
for i in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
D = [0xfffff for _ in range(V + 1)]
P = [0 for _ in range(V + 1)]
D[1], P[1] = 0, 1
 
DFS_SHORTEST(1)
 
print(D[1: V + 1])
print(P[1: V + 1])
복사

def DIJKSTRA_ARRAY(s):
 
    D = [0xfffff] * (V + 1)
    P = [i for i in range(V + 1)]
    visit = [False] * (V + 1)
    D[s] = 0
 
    cnt = V
    while cnt:                              # 정점의 수 만큼 반복
 
        u, MIN = 0, 0xfffff                 # D[] 가 최소인 정점 찾기
        for i in range(1, V + 1):           # 무식하게 리스트에서 찾기
            if not visit[i] and D[i] < MIN:
                u, MIN = i, D[i]
 
        visit[u] = True
 
        for v, w in G[u]:
            if not visit[v] and D[v] > D[u] + w:
                D[v] = D[u] + w
                P[v] = u
 
        cnt -= 1
 
    print(D[1: V + 1])
    print(P[1: V + 1])
 
 
V, E = map(int, input().split())
G = [[] for _ in range(V + 1)]
for i in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
DIJKSTRA_ARRAY(1)
복사

from heapq import heappop, heappush
 
def DIJKSTRA_PRIORITYQ(s):
 
    D = [0xfffff] * (V + 1)
    P = [i for i in range(V + 1)]
    # 다익스트라는 방문하지 않은 노드 중 D가 최소인 노드를 Q에서 선택하므로 visit 필요
    visit = [False] * (V + 1)
    D[s] = 0
    Q = [[0, s]]
 
    while Q:
        d, u = heappop(Q)
        if visit[u]: continue
 
        visit[u] = True
        for v, w in G[u]:
            if not visit[v] and D[v] > D[u] + w:
                D[v] = D[u] + w
                P[v] = u
                heappush(Q, [D[v], v])
 
    print(D[1:])
    print(P[1:])
 
 
V, E = map(int, input().split())
G = [[] for _ in range(V + 1)]
for i in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
DIJKSTRA_PRIORITYQ(1)
복사

# 입력 처리
V, E = map(int, input().split())
G = [[] for _ in range(V+1)]
 
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
# 시작점으로부터의 최단거리 배열 D 만들고 초기화
D = [0xffffff] * (V+1)
# 최단 경로 트리 저장, 노드까지의 최단경로에 이르는 부모노드번호 저장, 필수가 아닌 선택
P = [0] * (V+1)
# 시작점을 1로 가정하고 값을 0으로 설정(시작점~시작점 최단거리 : 0)
D[1] = 0
 
# 다익스트라는 방문하지 않은 노드 중 D가 최소인 노드를 Q에서 선택하므로 visit 필요
visit = [0]*(V+1)
 
for _ in range(V):
    # u는 임의의 0으로 정의, min_val는 INF로 정의
    u, min_val = 0, 0xffffff
    # D가 가장 작은 노드를 찾는 과정
    # 1부터 V까지의 노드 번호 i 에 대하여
    # 방문하지 않았고, D[i]가 더 작으면 i와 D[i] 갱신
    for i in range(1, V+1):
        # i번 노드가 방문하지 않았고, 
        if not visit[i] and min_val > D[i]:
            u, min_val = i, D[i]
    # 방문 표시
    visit[u] = 1
 
    # 위에서 구한 u의 인접정점에 대해 최단거리 확인
    for v, w in G[u]:
        if not visit[v] and D[v] > D[u]+w:
            D[v] = D[u]+w
 
# 0번 인덱스는 의미 X
print(D[1:])
복사

# 다익스트라 알고리즘과 유사
# 입력 처리
from heapq import heappop, heappush
 
V, E = map(int, input().split())
G = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))
 
key = [0xffffff] * (V+1)    # 큰 수를 넣어 초기화한 가중치 배열
p = list(range(V+1))        # 부모 정보(간선 정보)
tree = [0] * (V+1)          # 트리에 포함된 정점들의 집합
 
# 시작점은 임의의 값 4, queue는 시작정보와 함께 초기화
key[4] = 0
Q = [(0, 4)]
 
while Q:
    val, v = heappop(Q)       # queue에서 정보 가져오기
    if tree[u]: continue      # 방문했던 정점은 패스 
    tree[u] = 1               # 선택해서 다시 넣지 않도록
    ans += val                # 현재 간선을 선택할 거니까 ans에 val 누적
 
    # 인접정점들의 key 값 조사해서 갱신
    # u의 인접정점들에 대하여
    for v, w in G[u]:
        # 방문하지 않았고, key 값을 더 작게 갱신할 수 있다면
        if not tree[v] and key[v] > w:
            key[v] = w                     # v의 key 값을 w로 갱신
            p[v] = u                       # v의 부모노드를 u로 갱신
            heappush(Q, (w, v))            # v를 기준으로 하여 heap에 추가
 
print(ans)
print(p)
print(key)
복사

# 가. 원소(정점) 수 만큼 부모를 저장하는 배열
V = 7
# 자기 자신의 인덱스를 값으로 가리키는 배열
p = [i for i in range(V+1)]  # 모든 원소에 대해 make_set() 실행
# x만 포함하는 집합을 생성  -> x만 있는 트리(x가 루트)
# def make_set(x):
#     p[x] = x
 
p[2], p[3], p[4] = 1, 2, 3
print(p)
 
 
# 나. 이어지는 노드들과 루트노드를 연결
def find_set(x):        # x가 속하는 집합의 식별값 --> x가 속한 트리의 루트 노드 번호
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]
 
 
# 다. x, y가 각각 속한 집합을 합치기 : 2개의 트리를 하나로 합치는 것
def union(x, y):
    # x, y의 루트 노드를 a, b에 저장
    a = find_set(x)
    b = find_set(y)
    
    p[a] = b        # p[b] = a도 무관. 그냥 부모를 바꿔서 이식하는 개념
복사

# 입력처리 ......................
V, E = map(int, input().split())
# 연결노드, 가중치를 튜플로 저장할 리스트 초기화
edges = []
for _ in range(E):
    # edges에 입력을 튜플로 처리해 삽입
    edges.append(tuple(map(int, input().split())))
 
# 간선들을 가중치 순으로 정렬 ......................
edges.sort(key=lambda x:x[2])
 
# disjoint_set ......................
# 자기 인덱스를 값으로 하는, 즉 자기를 루트로 하는 set 생성
p = [i for i in range(V+1)]
def find_set(x):
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]
 
# 싸이클이 생기지 않도록 V-1개의 간선 선택 ..............
cnt = 0               # V-1개 까지 선택하기 위한 카운트 변수
ans = 0               # 누적값 변수
mst = []              # 선택한 정보 저장. 필수는 아님
for edge in edges:
    u, v, w = edge
    # u와 v가 연결된 상태인지 확인
    a = find_set(u)
    b = find_set(v)
 
    # 같은 루트 노드 공유하는 경우 다음 edge 확인
    if a==b: continue
    mst.append(edge)
    p[a] = b                # union 함수 별도로 안 만들고 바로 루트 이식
    cnt += 1                # cnt 1 추가
    ans += w                # ans에 이번 간선의 가중치 누적
    if cnt == V:            # V개의 정점, V-1개의 간선을 선택한 경우
        break
 
print(ans, mst)
복사