Description
Compute a minimum spanning tree (MST) of a weighted graph. Sort all edges by weight. Initialize MST empty, each vertex in its own component. For each edge (u,v) in sorted order: if u and v are in different components, add edge to MST and union components. Greedy. Time O(E log E) with sort; O(E α(V)) with union-find.
Algorithm Flowchart
graph TD
A1["Weighted graph G\nV vertices E edges"]
B1["Sort edges by weight\nMST = empty; init union-find"]
D1{"More edges?"}
C1["Take smallest edge u v"]
D2{"u and v in\nsame component?"}
E1["Add edge to MST\nUnion u v"]
E2["Skip edge"]
F1["Return MST"]
A1 --> B1
B1 --> D1
D1 -->|No| F1
D1 -->|Yes| C1
C1 --> D2
D2 -->|No: sequential AND| E1
D2 -->|Yes: sequential AND| E2
E1 --> D1
E2 --> D1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1 yellow
class C1,E1,E2 green
class F1 violet
class D1,D2 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds
Decision diamonds
Process Statistics
- Nodes: 8
- Edges: 9
- OR gates: 2
- Loops: 2
- AND gates: 2
- Complexity: O(E log E) or O(E α(V))
Keywords
- Kruskal
- minimum spanning tree
- MST
- graph algorithm
- NIST DADS
- greedy