1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
package graph
import (
"math/rand"
"testing"
)
func TestMST(t *testing.T) {
g := New(0)
if mess, diff := diff(MST(g), []int{}); diff {
t.Errorf("MST: %s", mess)
}
g = New(10)
g.AddBothCost(0, 1, 4)
g.AddBothCost(0, 7, 8)
g.AddBothCost(1, 2, 8)
g.AddBothCost(1, 7, 11)
g.AddBothCost(2, 3, 7)
g.AddBothCost(2, 8, 2)
g.AddBothCost(2, 5, 4)
g.AddBothCost(3, 4, 9)
g.AddBothCost(3, 5, 14)
g.AddBothCost(4, 5, 10)
g.AddBothCost(5, 6, 2)
g.AddBothCost(6, 7, 1)
g.AddBothCost(6, 8, 6)
g.AddBothCost(7, 8, 7)
exp := []int{-1, 0, 5, 2, 3, 6, 7, 0, 2, -1}
if mess, diff := diff(MST(g), exp); diff {
t.Errorf("MST: %s", mess)
}
}
func BenchmarkMST(b *testing.B) {
n := 1000
b.StopTimer()
g := New(n)
for i := 0; i < 2*n; i++ {
g.AddCost(rand.Intn(n), rand.Intn(n), int64(rand.Int()))
}
b.StartTimer()
for i := 0; i < b.N; i++ {
_ = MST(g)
}
}
|
