Cho đồ thị trọng số G=(V,E) như hình vẽ. Cây khung nhỏ nhất H = (V,T) theo thuật toán Prim có tập cạnh là:

Thuật toán Prim bắt đầu từ một đỉnh ngẫu nhiên và mở rộng cây bằng cách thêm các cạnh có trọng số nhỏ nhất kết nối cây hiện tại với các đỉnh chưa thuộc cây. Ta có thể bắt đầu từ đỉnh 1. 1. Bắt đầu từ đỉnh 1, cạnh có trọng số nhỏ nhất kề với 1 là (1,2) với trọng số 2. Thêm (1,2) vào T. T = {(1,2)}. 2. Các đỉnh đã xét: {1, 2}. Các cạnh kề với {1,2} là (1,8), (2,8), (2,4). Cạnh có trọng số nhỏ nhất là (1,8) với trọng số 4. Thêm (1,8) vào T. T = {(1,2), (1,8)}. 3. Các đỉnh đã xét: {1, 2, 8}. Các cạnh kề với {1, 2, 8} là (2,4), (8,3), (8,5). Cạnh có trọng số nhỏ nhất là (2,4) với trọng số 5. Thêm (2,4) vào T. T = {(1,2), (1,8), (2,4)}. 4. Các đỉnh đã xét: {1, 2, 8, 4}. Các cạnh kề với {1, 2, 8, 4} là (8,3), (8,5), (4,7). Cạnh có trọng số nhỏ nhất là (8,5) với trọng số 6. Thêm (8,5) vào T. T = {(1,2), (1,8), (2,4), (8,5)}. 5. Các đỉnh đã xét: {1, 2, 8, 4, 5}. Các cạnh kề với {1, 2, 8, 4, 5} là (8,3), (4,7), (5,7), (5,6). Cạnh có trọng số nhỏ nhất là (4,7) với trọng số 7. Thêm (4,7) vào T. T = {(1,2), (1,8), (2,4), (8,5), (4,7)}. 6. Các đỉnh đã xét: {1, 2, 8, 4, 5, 7}. Các cạnh kề với {1, 2, 8, 4, 5, 7} là (8,3), (5,6), (7,6). Cạnh có trọng số nhỏ nhất là (5,6) với trọng số 8. Thêm (5,6) vào T. T = {(1,2), (1,8), (2,4), (8,5), (4,7), (5,6)}. 7. Các đỉnh đã xét: {1, 2, 8, 4, 5, 7, 6}. Các cạnh kề là (8,3), (6,3). Cạnh có trọng số nhỏ nhất là (8,3) hoặc (6,3) với trọng số 9. Thêm (8,3) vào T. T = {(1,2), (1,8), (2,4), (8,5), (4,7), (5,6), (8,3)}. Vậy, T = {(1,2), (1,8), (8,5), (8,3), (5,6), (2,4), (4,7)}. Sắp xếp lại ta được T = {(1,2),(3,8),(8,5), (3,6), (6,7), (2,4), (4,7)}.