Graphs (2)

공부 기록/자료구조

Graphs (2)

와일 2026. 6. 23. 08:36

Graphs(1)에서는 그래프가 뭔지(vertex, edge, path, cycle, connectedness, subgraph, tree)와 그래프를 어떻게 저장하는지(Edge List / Adjacency List / Adjacency Matrix)를 다뤘다. 이번 (2)에서는 그 그래프 위에서 실제로 무엇을 할 수 있는지를 본다:

그래프 전체를 빠짐없이 둘러보는 탐색 방법 - DFS와 BFS
가중 그래프에서 한 점으로부터 다른 모든 점까지의 최단 경로를 구하는 Dijkstra's Algorithm
모든 vertex를 가장 싸게 연결하는 트리를 찾는 Minimum Spanning Tree(MST) - Prim's, Kruskal's, 그리고 이 둘을 가능하게 하는 Union-Find 자료구조

1. 그래프 탐색 - DFS와 BFS

1.1 DFS - 실과 페인트

DFS(Depth First Search)의 직관은 "실과 페인트"다. 시작 vertex에 실을 묶어두고 페인트 통을 들고 있다고 생각하자.

현재 vertex에서 아직 안 가본 edge를 하나 골라, 실을 풀면서 따라간다
도착한 vertex를 페인트로 칠한다(visited 표시)
더 갈 곳이 없으면(막다른 길) 실을 되감으며 이전 vertex로 돌아간다(backtrack)
돌아간 vertex에 아직 안 가본 edge가 있으면 다시 그 길로 출발

"Depth First"는 매번 "안 가본 edge를 골라 끝까지 가본 뒤에야 다른 선택지를 본다"는 뜻이다.

알고리즘(재귀):

DFS(G, u):
    u는 이미 visited 상태
    for u의 각 outgoing edge e=(u,v):
        if v가 아직 미방문이면:
            e를 discovery edge로 표시
            v를 visited로 표시
            DFS(G, v)
        else:
            e를 back edge(또는 cross edge 등)로 표시

여기서 새로 등장하는 용어 둘:

discovery edge: 처음으로 새 vertex를 방문하게 만든 edge. 이 edge들만 모으면 트리(DFS tree)가 된다
back edge: 이미 visited인 vertex로 이어지는 edge (discovery edge는 아님)

1.2 DFS 예제

vertex A,B,C,D,E, edge는 A-B, A-C, A-D, A-E, B-C, C-D, C-E (총 7개). A와 C는 나머지 모든 vertex와 연결되어 있다. A에서 시작, 인접 vertex는 알파벳 순서로 본다.

A 방문. 인접 B,C,D,E 중 첫 미방문 B → discovery A-B
B. 인접 A(부모, 건너뜀), C(미방문) → discovery B-C
C. 인접 A(visited, 부모 아님 → back C-->A), B(부모), D(미방문) → discovery C-D
D. 인접 A(visited, 부모 아님 → back D-->A), C(부모). 더 없음 → backtrack
C로 복귀. E(미방문) → discovery C-E
E. 인접 A(visited, 부모 아님 → back E-->A), C(부모). 더 없음 → backtrack
C, B, A 순서로 backtrack. 종료

최종 DFS tree:

            A
            |
            B
            |
            C
           / \
          D   E

back edge(점선): C-->A, D-->A, E-->A

DFS tree는 "한 줄기로 깊게 들어갔다가, 막히면 가장 가까운 분기점으로 돌아와 다른 가지를 타는" 모양이 된다.

1.3 DFS의 성질

discovery edge들 사이엔 cycle이 없다 (= DFS tree)
undirected graph: DFS(G,u)는 u의 connected component 전체를 방문하고, discovery edge들이 그 component의 spanning tree(DFS tree)를 만든다
directed graph: DFS(G,u)는 u로부터 reachable한 모든 vertex를 방문한다
시간복잡도: adjacency list 기준 O(n+m)

1.4 Cycle Detection - back edge와 cross edge

핵심 규칙: DFS에서 back edge가 존재한다 == cycle이 존재한다. (back edge의 정의: 자신의 ancestor(조상)로 이어지는 edge)

undirected graph: 간단하다. 이미 explored된 vertex를 다시 만나면, 그건 항상 자신의 ancestor이므로 무조건 back edge = cycle
directed graph: 덜 간단하다. 이미 explored된 vertex를 다시 만났어도, 그게 ancestor가 아닐 수 있다. 이런 edge를 cross edge라고 부르고, cycle을 의미하지 않는다

예시: vertex U,V,W,X,Y,Z의 directed graph에서 DFS(G,U)가 다음과 같이 진행됐다고 하자.

discovery edges: U->V, V->X, X->Z, X->Y, Y->W
back edges:      W-->V, W-->X
cross edge:      U-->W

W에서 V, X로 가는 edge는 back edge다 (V, X는 W의 ancestor, 즉 U->V->X->Y->W 경로 위에 있다). 이 back edge들로 X,Y,W와 V,X,Y,W가 각각 cycle을 이룬다.

(U,W)는 cross edge다. DFS가 U->V->X->Y->W까지 다 탐색하고 backtrack해서 U로 돌아온 뒤, U의 마지막 edge인 (U,W)를 확인하는 시점에는 W가 이미 "탐색이 끝난(finished)" 상태다. 이때 W는 U의 ancestor가 아니므로 back edge가 아니라 cross edge다.

(U,W)가 cross edge라는 게 왜 cycle을 의미하지 않을까? cycle이 되려면 (U,W) 외에도 W에서 다시 U로 돌아가는 길이 있어야 한다. 그런데 W가 가진 outgoing edge는 W->V, W->X뿐이고 둘 다 V의 서브트리(V,X,Y,Z,W) 안쪽만 가리킨다. U는 그 서브트리 밖에 있으므로, W에서 U로 돌아갈 길이 없다.

정리: back edge는 "지금 밟고 있는 경로 위의 조상으로 되돌아가는 edge"라서 항상 cycle을 만든다. cross edge는 "이미 끝난 다른 가지로 건너가는 edge"인데, 그 가지에서 나에게로 돌아오는 길이 없으므로 cycle을 만들지 않는다.

1.5 Path Finding with DFS

DFS(G,u)의 discovery edge들을 얻었다면, u에서 v까지의 path 찾기:

v에서 시작해서, discovery edge를 따라 거꾸로(부모 방향으로) 올라간다
u에 도달하면, 지금까지의 경로를 역순으로 뒤집은 게 u에서 v까지의 path
u에 도달하지 못하면 path 없음

1.2의 DFS tree에서 A에서 D로 가는 path: D -> C -> B -> A로 거꾸로 올라간 뒤 뒤집으면 A -> B -> C -> D.

1.6 BFS - 물결처럼 퍼지기

BFS(Breadth First Search)는 DFS와 정반대다. 시작 vertex에서 물결이 동심원처럼 퍼져나가듯, 가까운 vertex부터 레벨 단위로 넓게 탐색한다.

Level 0: 시작 vertex
Level 1: 시작 vertex와 직접 연결된(1-hop) vertex들
Level 2: Level 1의 vertex들과 연결된, 아직 안 본 vertex들 (시작점에서 2-hop)
큐(queue)를 이용해 레벨을 하나씩 늘려가며 처리

1.7 BFS 예제 - 같은 그래프로 비교

1.2와 같은 그래프(A,B,C,D,E, edges A-B,A-C,A-D,A-E,B-C,C-D,C-E)에 BFS를 적용해보자. A에서 시작, 인접 vertex는 알파벳 순서.

Level 0: A
A의 인접 B,C,D,E 전부 미방문 → 전부 Level 1, discovery edge A-B, A-C, A-D, A-E
B 처리: A(부모), C(이미 Level1) → cross edge B-C
C 처리: A(부모), B,D,E(이미 Level1) → cross edge C-D, C-E
D, E: 더 볼 것 없음

            A                (Level 0)
        /  |  |  \
       B   C  D   E          (Level 1)
        \ / \  \ /
        B-C C-D C-E  : cross edge

DFS는 A-B-C-D-E가 한 줄로 이어진 트리였는데, BFS는 A를 중심으로 B,C,D,E가 모두 Level 1에 모이는 별(star) 모양이 된다. 같은 그래프인데 탐색 순서만 바뀌었을 뿐인데 트리 모양이 완전히 달라진다.

BFS에서의 edge 분류:

undirected graph: BFS에서는 back edge가 절대 생기지 않는다. 이미 visited인 vertex로 가는 edge는 항상 cross edge다
directed graph: BFS에서는 back edge와 cross edge가 둘 다 생길 수 있다

1.8 BFS의 성질 - 최단 경로

undirected graph: BFS(G,u)도 u의 connected component 전체를 방문하고, discovery edge들이 spanning tree(BFS tree)를 만든다
시간복잡도: O(n+m)

가장 핵심적인 성질: Level i에 있는 vertex v에 대해, BFS tree에서 시작점 s부터 v까지의 경로는 정확히 i개의 edge를 거친다. 그리고 G 안의 어떤 path로도 s에서 v까지 가려면 최소 i개의 edge가 필요하다.

즉, BFS tree에서 v까지의 거리(edge 개수)가 실제 그래프에서의 최단 거리와 정확히 같다. BFS는 (가중치 없는 그래프에서) 최단 경로를 찾는 방법이기도 하다.

1.9 DFS와 BFS 비교

새 vertex F를 추가하고 D-F edge 하나만 연결했다고 하자. 각 vertex의 인접 목록:

A: B, C, D, E
B: A, C
C: A, B, D, E
D: A, C, F
E: A, C
F: D

DFS(A) tree:

A
|
B
|
C
|\
D E
|
F

A-B-C-D-F가 한 줄로 길게 이어지고, C에서 E로 가지 하나가 뻗어나온다.

BFS(A) tree:

        A
    /   |  |  \
   B    C  D   E
              |
              F

F는 Level 2가 되고, A에서 F까지는 정확히 2개의 edge(A-D-F)를 거친다.

정리:

DFS: 길고 깊은 트리. 거리 정보는 보장 안 되지만(DFS tree에서 A-D 거리는 3인데 실제 최단은 1), 연결 여부 확인, cycle 탐지, 경로 존재 여부 확인 등에 적합
BFS: 넓고 얕은 트리. Level = 시작점부터의 최소 거리(edge 개수)이므로, 가중치 없는 그래프에서 최단 경로/최단 거리를 구할 때 사용

2. 가중 그래프와 최단 경로 - Dijkstra's Algorithm

2.1 Weighted Graph와 Shortest Path

weighted graph는 각 edge e=(u,v)에 숫자 weight w(e)=w(u,v)가 붙은 그래프(거리, 비용 등). path의 length는 그 path를 이루는 edge들의 weight 합이고, shortest path는 두 vertex 사이에서 length가 최소인 path다.

Dijkstra's Algorithm은 weight가 음수가 아니라는 가정에 크게 의존한다.

2.2 Dijkstra - cloud와 edge relaxation

Dijkstra는 greedy algorithm이다: 매 순간 "지금 보기에 가장 좋은 선택"을 한다.

cloud란 "이미 시작점으로부터의 최단거리가 확정되어서, 앞으로 절대 안 바뀔 vertex들의 집합"이다. 다이어그램에서 이 영역을 구름 모양으로 감싸서 그리기 때문에 그렇게 부른다.

처음엔 cloud = {시작 vertex s}뿐이다. D(s)=0은 더 줄어들 수 없으므로 확정
매 단계: cloud 밖에서 D값이 가장 작은 vertex를 골라 cloud에 추가한다 - "이 vertex의 D값은 이제부터 영원히 안 바뀐다"는 선언
방금 들어온 vertex를 거쳐서, 아직 cloud 밖인 인접 vertex들의 D값이 더 줄어들 수 있는지 확인한다 (edge relaxation)

edge relaxation 공식: D(v) = min(D(v), D(u) + w(u,v)) (u는 방금 cloud에 들어온 vertex)

이 공식이 의미하는 건 "v까지 가는 두 가지 방법 중 더 짧은 걸 택하자"다 - 지금까지 알던 최선의 값 D(v)와, 방금 확정된 u를 거쳐서 가는 값 D(u)+w(u,v) 중 더 작은 쪽.

2.3 예제

vertex A,B,C,D,E,F. edges = A-B(8), A-C(2), A-D(4), B-C(7), B-E(2), C-D(1), C-E(3), C-F(9), D-F(5). A에서 시작.

단계	cloud에 새로 추가	D(B)	D(C)	D(D)	D(E)	D(F)
초기	-	8	2	4	무한	무한
1	C (D=2)	8	2	3	5	11
2	D (D=3)	8	2	3	5	8
3	E (D=5)	7	2	3	5	8
4	B (D=7)	7	2	3	5	8
5	F (D=8)	7	2	3	5	8

각 단계 설명:

1단계: cloud={A}에서 가장 작은 C(=2)를 추가. C를 거쳐가는 게 더 짧은지 확인 → D(D)=min(4, 2+1)=3, D(E)=min(무한,2+3)=5, D(F)=min(무한,2+9)=11
2단계: D(=3)를 추가. D를 거치면 D(F)=min(11,3+5)=8로 줄어듦
3단계: E(=5) 추가. E를 거치면 D(B)=min(8,5+2)=7로 줄어듦
4단계: B(=7) 추가. B의 인접(A,C,E) 모두 이미 cloud → 변화 없음
5단계: F(=8) 추가. 끝

edge relaxation을 직접 적용해보는 예: 2단계에서 D가 cloud에 들어온 직후, D-F(weight5) edge로 relaxation을 적용하면 D(F) = min(D(F), D(D)+w(D,F)) = min(11, 3+5) = min(11,8) = 8. "원래 11이라고 알던 D(F)가, D를 통해 가는 길(3+5=8)이 더 짧다는 걸 발견해서 8로 줄어든다"는 게 이 단계의 의미다.

최종 결과: A에서 각 vertex까지의 최단거리는 A=0, B=7, C=2, D=3, E=5, F=8.

2.4 왜 동작할까

핵심은 weight가 음수가 아니라는 가정이다. cloud 안의 vertex들은 이미 확정된 최단거리인데, cloud 밖으로 나가는 어떤 경로든 cloud 경계를 넘는 순간 거리가 늘어날 수밖에 없다(weight가 0 이상이므로). 그래서 "지금 cloud 밖에서 가장 가까운 vertex"를 골라도, 나중에 다른 경로를 거쳐서 그보다 더 짧아질 일이 없다.

만약 weight가 음수라면, 나중에 "지름길"이 생겨서 이미 확정한 D값이 사실은 최단이 아니었던 게 될 수 있다. 즉 "cloud에 넣어서 확정한다"는 행위 자체가 의미를 잃어버려서 알고리즘이 깨진다.

2.5 시간복잡도

n개 vertex, m개 edge, adjacency list + priority queue(연산당 O(log n)) 기준:

각 vertex는 PQ에 한 번 삽입, 한 번 제거 → O(n log n)
각 edge는 relaxation으로 인한 D값 업데이트가 최대 한 번씩 일어날 수 있음 → O(m log n)
합쳐서 O((n+m) log n)

3. Minimum Spanning Tree - Prim's, Kruskal's, Union-Find

3.1 MST란

spanning tree는 그래프의 모든 vertex를 포함하면서 cycle 없이 전부 연결한 부분그래프였다. 한 그래프에는 spanning tree가 여러 개 있을 수 있다. 각 edge에 weight(비용)가 있다면, 각 spanning tree마다 "포함된 edge들의 weight 합"(총 비용)이 정해진다. 이 총 비용이 가장 작은 spanning tree를 Minimum Spanning Tree(MST)라고 한다.

비유: 여러 도시 사이에 도로를 놓을 때, 모든 도시가 연결되어야 하고 굳이 cycle은 필요 없다. "도로 건설 총 비용을 최소화하는 도로망"이 MST다.

3.2 Cut(Partition) Property

Prim's와 Kruskal's 둘 다 다음 사실에 기댄다:

전체 vertex 집합을 두 그룹 V1, V2로 나눈다고 하자(어떻게 나누든 둘 다 비어있지 않으면 됨). V1과 V2 사이를 잇는 edge들 중 weight가 가장 작은 edge를 e라고 하면, e를 포함하는 MST가 반드시 존재한다.

왜 그럴까? spanning tree는 모든 vertex를 연결해야 하므로 V1과 V2를 잇는 "다리" 역할의 edge가 최소 하나는 있어야 한다. 그 다리들 중 가장 싼 걸 안 쓰고 더 비싼 다리를 썼다면, 그 비싼 다리를 떼고 가장 싼 다리로 바꿔도 여전히 모든 vertex가 연결되고 cycle도 안 생기며 총 비용은 같거나 줄어든다. 그러니 가장 싼 다리를 쓰는 게 항상 이득이다.

이 사실을 반복 적용하는 게 두 알고리즘의 본질이고, "V1, V2를 어떻게 나누느냐"의 방식이 둘 사이에서 다르다.

3.3 Prim's Algorithm

Prim's는 Dijkstra와 구조가 거의 같다. cloud를 하나씩 키워나가는 그 패턴 그대로인데, 딱 한 가지가 다르다:

Dijkstra의 D(v) = "시작점 s부터 v까지 가는 전체 경로의 길이"(여러 edge weight의 합)
Prim's의 D(v) = "v를 지금의 cloud에 직접 연결하는 edge 하나의 weight"(cloud에 연결되는 가장 싼 edge가 뭔지)

알고리즘:

아무 vertex나 하나 골라 cloud에 넣는다(D=0)
나머지 vertex들의 D는 무한대로 시작
반복: cloud 밖에서 D가 가장 작은 vertex를 cloud에 추가한다 - 이때 그 vertex를 cloud에 연결시킨 edge가 MST edge가 된다
방금 들어온 vertex와 연결된, 아직 cloud 밖인 vertex들에 대해: 그 edge의 weight가 지금의 D보다 작으면 D를 그 edge weight로 갱신
모든 vertex가 cloud에 들어가면 종료

예제: vertex A,B,C,D,E,F, edges = A-B(2), A-C(8), A-E(7), B-C(5), B-D(7), C-D(9), C-E(8), D-F(4), E-F(3). A에서 시작.

단계	cloud에 추가	사용된 edge	D(B)	D(C)	D(D)	D(E)	D(F)
초기	-	-	무한	무한	무한	무한	무한
1	A	(시작점)	2	8	무한	7	무한
2	B (D=2)	A-B	2	5	7	7	무한
3	C (D=5)	B-C	2	5	7	7	무한
4	D (D=7)	B-D	2	5	7	7	4
5	F (D=4)	D-F	2	5	7	3	4
6	E (D=3)	F-E	2	5	7	3	4

4단계에서 D(D)=7과 D(E)=7이 tie인데, D를 먼저 추가한다고 했다.

최종 MST edges: A-B(2), B-C(5), B-D(7), D-F(4), F-E(3). 총 weight = 2+5+7+4+3 = 21

3.4 Kruskal's Algorithm

Kruskal's는 Prim's와 완전히 다른 접근이다.

처음엔 각 vertex를 자기 혼자만의 작은 그룹(cluster)으로 본다. 전체 edge들을 weight가 작은 순서대로 하나씩 살펴보면서, 그 edge가 서로 다른 두 그룹을 연결해주면 추가하고 두 그룹을 합친다(merge). 같은 그룹끼리 잇는 edge라면(이미 연결돼있으니 cycle만 생기므로) 버린다. 결국 그룹이 하나만 남으면 끝.

알고리즘:

각 vertex를 자기만의 클러스터로 만든다(n개의 클러스터)
모든 edge를 weight가 작은 순서로 정렬(또는 priority queue)
반복: 가장 작은 weight의 edge (u,v)를 꺼낸다
- u와 v가 다른 클러스터에 속하면 → MST에 추가, 두 클러스터를 합친다
- 같은 클러스터에 속하면 → 버린다
MST가 n-1개의 edge를 가지면(클러스터가 1개로 합쳐짐) 종료

같은 그래프로 추적: weight 순서 정렬 - A-B(2), E-F(3), D-F(4), B-C(5), A-E(7), B-D(7), A-C(8), C-E(8), C-D(9)

순서	edge(weight)	같은 클러스터?	결과	클러스터 상태
1	A-B(2)	다름(각자 혼자)	추가	{A,B}, {C}, {D}, {E}, {F}
2	E-F(3)	다름	추가	{A,B}, {C}, {D}, {E,F}
3	D-F(4)	다름(D 혼자, F는 {E,F})	추가	{A,B}, {C}, {D,E,F}
4	B-C(5)	다름(B는 {A,B}, C 혼자)	추가	{A,B,C}, {D,E,F}
5	A-E(7)	다름(A는 {A,B,C}, E는 {D,E,F})	추가, n-1=5개 됨, 종료	{A,B,C,D,E,F}

Kruskal's가 찾은 MST: A-B(2), E-F(3), D-F(4), B-C(5), A-E(7). 총 weight = 2+3+4+5+7 = 21

3.5 MST may not be unique

Prim's에서는 4단계에서 D(D)=7과 D(E)=7이 tie였고 B-D(weight7)를 선택했다. Kruskal's는 weight7짜리 edge 중 A-E를 먼저 선택했다(B-D는 정렬 순서상 A-E 다음인데, A-E를 추가한 순간 이미 클러스터가 1개로 합쳐져서 B-D는 볼 필요도 없이 끝났다).

두 알고리즘이 고른 MST의 구체적인 edge 집합은 다르지만(B-D vs A-E), 총 weight는 똑같이 21이다. weight가 같은 edge가 여러 개 있을 때 어떤 걸 고르느냐에 따라 트리의 모양은 달라질 수 있지만, 최소 총 비용 자체는 항상 같다 - 이게 "MST may not be unique"의 실제 의미다.

3.6 Union-Find(Partition) 자료구조

Kruskal's에서 매 edge (u,v)마다 빠르게 해야 하는 두 가지:

"u와 v가 같은 클러스터에 있는가?"(확인)
다른 클러스터라면 두 클러스터를 합쳐라(병합)

이걸 효율적으로 해주는 자료구조가 Union-Find다. 제공하는 연산:

make_group(e): 새 원소 e 하나로 이루어진 클러스터를 만든다(처음에 각 vertex마다 한 번씩 호출)
find(p): p가 속한 클러스터의 대표(leader/root)가 누구인지 알려준다. find(p) == find(q)이면 p와 q는 같은 클러스터
union(p,q): p가 속한 클러스터와 q가 속한 클러스터를 하나로 합친다

Tree 기반 구현

각 원소는 자기 "부모"를 가리키는 포인터 하나만 들고 있다. 자기 자신을 가리키는 원소가 그 클러스터의 root(대표)다.

find(p): p에서 시작해서 부모, 부모의 부모, ...를 따라가다가 자기 자신을 가리키는 원소(root)를 찾으면 그게 답
union(p,q): 한 트리의 root를 다른 트리의 root의 자식으로 만든다

3.4의 Kruskal's 진행을 Union-Find 관점에서 보면:

초기: A B C D E F     (전부 자기 자신을 가리킴, 전부 root)

union(A,B): B의 root를 A로
union(E,F): F의 root를 E로
union(D,F): D(크기1)가 더 작으므로, D의 root를 E로 (F의 root는 이미 E)
union(B,C): C(크기1)가 더 작으므로, C의 root를 A로 (B의 root는 이미 A)
union(A,E): 둘 다 크기3으로 같음 -> E의 root를 A로

최종 구조:
        A
      / | \
     B  C  E
          / \
         D   F

Union-by-size

union할 때 항상 더 작은(원소 개수가 적은) 트리의 root를 더 큰 트리의 root 밑에 붙인다. 이렇게 하면 트리의 높이가 잘 안 늘어나서 find()가 부모를 따라 올라가는 횟수가 대략 O(log n)을 넘지 않는다. 크기가 같은 경우에는 루트로 아무거나 골라도 상관 없다.

직관: 어떤 원소의 "부모를 한 번 따라간다"는 건, 그 부모가 한때 어떤 트리의 root였다는 뜻이고, 그 트리는 합쳐질 때마다 최소 2배씩 커졌어야 한다. n개 원소로는 이런 일이 최대 log n번만 반복될 수 있다. 결과적으로 n번의 union-find 연산을 합쳐서 O(n log n) 시간이 걸린다.

Kruskal's 전체 시간복잡도

edge들을 weight 순으로 정렬/PQ: O(m log m)
union-find 연산들(클러스터 확인+병합): O(n log n)
합쳐서 대략 O(m log n) (단순 그래프에서는 m이 O(n^2)이지만 log m과 log n은 같은 차수)

마무리

이번 글의 흐름: 그래프 탐색(DFS의 깊은 트리, BFS의 넓은 트리와 최단거리) -> 가중 그래프에서의 최단경로(Dijkstra, cloud와 edge relaxation) -> 모든 vertex를 가장 싸게 연결하는 트리(MST, Prim's와 Kruskal's, 그리고 Kruskal's를 가능하게 하는 Union-Find).

핵심 정리:

DFS: back edge=cycle, cross edge != cycle (directed graph에서만 구분 필요). Path finding은 discovery edge를 거꾸로 따라가서 뒤집기
BFS: Level = 시작점부터의 최소 거리. 같은 그래프라도 DFS는 길고 좁은 트리, BFS는 넓고 얕은 트리가 된다
Dijkstra: cloud = 확정된 최단거리 집합. edge relaxation D(v)=min(D(v), D(u)+w(u,v)). nonnegative weight 가정이 핵심
Prim's: Dijkstra와 같은 구조지만, D(v)는 "cloud에 연결되는 가장 싼 edge의 weight"
Kruskal's: 작은 클러스터들을 weight가 작은 edge부터 합쳐나간다. MST may not be unique(총 weight는 같지만 구체적 edge 구성은 다를 수 있음)
Union-Find: find(p)==find(q)로 같은 클러스터 확인, union-by-size로 트리 높이를 O(log n) 수준으로 유지

'공부 기록 > 자료구조' 카테고리의 다른 글

Sorting (2) (0)	2026.06.26
Sorting (1) (0)	2026.06.25
Graphs (1) (0)	2026.06.22
Search Trees (2) (0)	2026.06.21
Search Trees (1) (0)	2026.06.19

현재글Graphs (2)

미완성의 기록

Graphs (2)

1. 그래프 탐색 - DFS와 BFS

1.1 DFS - 실과 페인트

1.2 DFS 예제

1.3 DFS의 성질

1.4 Cycle Detection - back edge와 cross edge

1.5 Path Finding with DFS

1.6 BFS - 물결처럼 퍼지기

1.7 BFS 예제 - 같은 그래프로 비교

1.8 BFS의 성질 - 최단 경로

1.9 DFS와 BFS 비교

2. 가중 그래프와 최단 경로 - Dijkstra's Algorithm

2.1 Weighted Graph와 Shortest Path

2.2 Dijkstra - cloud와 edge relaxation

2.3 예제

2.4 왜 동작할까

2.5 시간복잡도

3. Minimum Spanning Tree - Prim's, Kruskal's, Union-Find

3.1 MST란

3.2 Cut(Partition) Property

3.3 Prim's Algorithm

3.4 Kruskal's Algorithm

3.5 MST may not be unique

3.6 Union-Find(Partition) 자료구조

Tree 기반 구현

Union-by-size

Kruskal's 전체 시간복잡도

마무리

'공부 기록 > 자료구조' 카테고리의 다른 글

'공부 기록/자료구조'의 다른글

티스토리툴바

Graphs (2)

1. 그래프 탐색 - DFS와 BFS

1.1 DFS - 실과 페인트

1.2 DFS 예제

1.3 DFS의 성질

1.4 Cycle Detection - back edge와 cross edge

1.5 Path Finding with DFS

1.6 BFS - 물결처럼 퍼지기

1.7 BFS 예제 - 같은 그래프로 비교

1.8 BFS의 성질 - 최단 경로

1.9 DFS와 BFS 비교

2. 가중 그래프와 최단 경로 - Dijkstra's Algorithm

2.1 Weighted Graph와 Shortest Path

2.2 Dijkstra - cloud와 edge relaxation

2.3 예제

2.4 왜 동작할까

2.5 시간복잡도

3. Minimum Spanning Tree - Prim's, Kruskal's, Union-Find

3.1 MST란

3.2 Cut(Partition) Property

3.3 Prim's Algorithm

3.4 Kruskal's Algorithm

3.5 MST may not be unique

3.6 Union-Find(Partition) 자료구조

Tree 기반 구현

Union-by-size

Kruskal's 전체 시간복잡도

마무리

'공부 기록 > 자료구조' 카테고리의 다른 글

'공부 기록/자료구조'의 다른글

관련글

티스토리툴바