package Graphimport ("Algorithm/Container""sort""testing"
)//最小生成树算法 Kruskal
//跑无向图 会少一侧 少n条边 a->b  b->a的少了
/*1.总是从权值最小的边开始考虑，一次考察权值一次变大的边2.当前的边要么进入最小生成树的集合，要么丢弃3.如果当前的边进入最小生成树的集合中不会形成环，就要当前边4.如果当前的边进入最小生成树的集合中会形成环，就不要当前边5.考察完所有边之后，最小生成树的集合也得到了理解了并查集的概念非常简单最小生成树 有向图和无向图都可以用整体权重最小的边连起来所有的点可以适当的删掉某些边，只要不破坏连通性Kruskal算法流程：所有的边根据权值由小到大排序找出最小的边，看他连的两个点是不是在同一个集合不是在一个集合则要该条边，并连同两点
*/type EdgeSet []*Edgefunc (this *EdgeSet) Less(i, j int) bool {//fmt.Println((*this)[i].Weight , (*this)[j].Weight)return (*this)[i].Weight < (*this)[j].Weight
}func (this *EdgeSet) Len() int {return len(*this)
}func (this *EdgeSet) Swap(i, j int) {//fmt.Println("交换",(*this)[i].Weight , (*this)[j].Weight)(*this)[i], (*this)[j] = (*this)[j], (*this)[i]
}func KrasKalMST(graph *Graph) *EdgeSet {edgesQueue := new(EdgeSet)for edge, _ := range graph.Edges {*edgesQueue = append(*edgesQueue, edge)}sort.Sort(edgesQueue)unionFind := Container.NewUnionFind()res := new(EdgeSet)for k, _ := range *edgesQueue {if !unionFind.IsConnected((*edgesQueue)[k].From, (*edgesQueue)[k].To) {*res = append(*res, (*edgesQueue)[k])unionFind.Union((*edgesQueue)[k].From, (*edgesQueue)[k].To)}}return res
}func TestKrasKalMST(t *testing.T) {matrix := [][]int{{2, 1, 4},{2, 2, 6},{5, 1, 2},{3, 1, 5},{3, 4, 3},{8, 4, 5},{9, 5, 6},{5, 3, 7},{6, 3, 2},{7, 2, 7},{6, 6, 7},}g := CreateGraph(matrix)for k, v := range *KrasKalMST(g) {t.Log("顺序", k+1, "-- 权重:", v.Weight, "从:", v.From.Value, "到:", v.To.Value)}//old:=*KrasKalMST(g)//i:=0//go func() {//	for range time.Tick(time.Second*10){//		fmt.Println("current i is",i)//	}//}()//for ;i<=100000000;i++ {//	if len(*KrasKalMST(g))==len(old){//		continue//	}else {//		fmt.Println(len(*KrasKalMST(g)),len(old))//		break//	}//}//fmt.Println("ok")
}