Function TestPrimMST

graph/prim_test.go:9–143

(t *testing.T)

)

func TestPrimMST(t *testing.T) {

	var testCases = []struct {
		edges    []Edge
		vertices int
		start    int
		cost     int
		mst      []Edge
	}{
		{
			edges: []Edge{
				{Start: 0, End: 1, Weight: 4},
				{Start: 0, End: 2, Weight: 13},
				{Start: 0, End: 3, Weight: 7},
				{Start: 0, End: 4, Weight: 7},
				{Start: 1, End: 2, Weight: 9},
				{Start: 1, End: 3, Weight: 3},
				{Start: 1, End: 4, Weight: 7},
				{Start: 2, End: 3, Weight: 10},
				{Start: 2, End: 4, Weight: 14},
				{Start: 3, End: 4, Weight: 4},
			},
			vertices: 5,
			start:    0,
			cost:     20,
			mst: []Edge{
				{Start: 0, End: 1, Weight: 4},
				{Start: 1, End: 3, Weight: 3},
				{Start: 3, End: 4, Weight: 4},
				{Start: 1, End: 2, Weight: 9},
			},
		},
		{
			edges: []Edge{
				{Start: 0, End: 1, Weight: 4},
				{Start: 0, End: 7, Weight: 8},
				{Start: 1, End: 2, Weight: 8},
				{Start: 1, End: 7, Weight: 11},
				{Start: 2, End: 3, Weight: 7},
				{Start: 2, End: 5, Weight: 4},
				{Start: 2, End: 8, Weight: 2},
				{Start: 3, End: 4, Weight: 9},
				{Start: 3, End: 5, Weight: 14},
				{Start: 4, End: 5, Weight: 10},
				{Start: 5, End: 6, Weight: 2},
				{Start: 6, End: 7, Weight: 1},
				{Start: 6, End: 8, Weight: 6},
				{Start: 7, End: 8, Weight: 7},
			},
			vertices: 9,
			start:    3,
			cost:     37,
			mst: []Edge{
				{Start: 3, End: 2, Weight: 7},
				{Start: 2, End: 8, Weight: 2},
				{Start: 2, End: 5, Weight: 4},
				{Start: 5, End: 6, Weight: 2},
				{Start: 6, End: 7, Weight: 1},