Description
Compute a minimum spanning tree (MST) by growing from a start vertex. Initialize MST with start; add edges from MST to non-MST vertices to a priority queue. Repeatedly extract minimum edge (u,v); if v not in MST, add edge and v to MST, add v's edges to queue. Greedy. Time O(E log V) with binary heap; O(E + V log V) with Fibonacci heap.
Algorithm Flowchart
graph TD
A1["Weighted graph G\nStart vertex s"]
B1["MST = s\nQ = edges from s to others"]
D1{"Q empty?"}
C1["u v w = extract-min Q"]
D2{"v in MST?"}
E1["Add u v to MST\nAdd v edges to Q"]
E2["Skip edge"]
F1["Return MST"]
A1 --> B1
B1 --> D1
D1 -->|Yes| F1
D1 -->|No| 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 V) or O(E + V log V)
Keywords
- Prim
- minimum spanning tree
- MST
- graph algorithm
- NIST DADS
- greedy