Minimum Spanning Tree

✅ Spanning Tree

all nodes are connected to be part of tree
undirected graph

✅ Spanning Tree Algorithm

When there are several ways to reach a switch, bridge,
looping occurs
spanning tree algorithm is to prevent this looping

✅ Minimum Spanning Tree

type of spanning tree(1️⃣ all nodes are connected)
spanning tree that 2️⃣ has the minimum weight among all the possible spanning trees
spanning tree that has minimum weight possible
그래프 안에서 1️⃣ 모든 노드를 연결하면서, 2️⃣ 가중치 합이 최소인 트리

• used to find way to connect all nodes with minimum weight

• Kruskal’s Algorithm: add edges to growing spanning tree
• Prim’s Algorithm: add vertext to growing spanning tree