10-并查集、图相关算法介绍.md

[TOC]
# 1 并查集、图相关算法

## 1.1 并查集

### 1.1.1 并查集基本结构和操作

1、有若干个样本a、b、c、d...类型假设是V

2、在并查集中一开始认为每个样本都在单独的集合里

3、用户可以在任何时候调用如下两个方法：

boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合

void union(V x, V y)：把x和y各自所在集合的所有样本合并成一个集合

4、isSameSet和union方法的代价越低越好，最好O(1)

> 思路：isSameSet方法，我们设计为每个元素有一个指向自己的指针，成为代表点。判断两个元素是否在一个集合中，分别调用这两个元素的向上指针，两个元素最上方的指针如果内存地址相同，那么两个元素在一个集合中，反之不在

> 思路：union方法，例如将a所在的集合和e所在的集合合并成一个大的集合union(a,e)。a的代表点指针是a，e的代表点指针是e，我们拿较小的集合挂在大的集合下面，比如e小，那么e放在a的下面。链接的方式为小集合e头结点本来指向自己的代表节点，现在要指向a节点

> 并查集的优化点主要有两个，一个是合并的时候小的集合挂在大的集合下面，第二个优化是找某节点最上方的代表节点，把沿途节点全部拍平，下次再找该沿途节点，都变为O(1)。两种优化的目的都是为了更少的遍历节点。

> 由于我们加入了优化，如果N个节点，我们调用findFather越频繁，我们的时间复杂度越低，因为第一次调用我们加入了优化。如果findFather调用接近N次或者远远超过N次，我们并查集的时间复杂度就是O(1)。该证明从1964年一直研究到1989年，整整25年，算法导论23章，英文版接近50页。

```Go
package main

// Node 并查集结构中的节点类型
type Node struct {
	V int
}

type UnionSet struct {
	// 记录样本到样本代表点的关系。值到代表该值的Node节点的关系映射
	Nodes map[int]*Node
	// 记录某节点到父亲节点的关系。
	// 比如b指向a，c指向a，d指向a，a指向自身
	// map中保存的a->a b->a c->a d->a
	Parents map[*Node]*Node
	// 只有当前点，他是代表点，会在sizeMap中记录该代表点的连通个数
	SizeMap map[*Node]int
}

// FindFather 在并查集结构中找一个节点的父亲根节点
// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
// 通过把路径上所有节点指向最上方的代表节点，目的是把findFather优化成O(1)的
func (set *UnionSet) FindFather(cur *Node) *Node {
	// 在找father的过程中，沿途所有节点加入当前容器，便于后面扁平化处理
	path := make([]*Node, 0)
	// 当前节点的父亲不是指向自己，进行循环
	for cur != set.Parents[cur] {
		path = append(path, cur)
		// 向上移动
		cur = set.Parents[cur]
	}
	// 循环结束，cur此时是最上的代表节点
	// 把沿途所有节点拍平，都指向当前最上方的代表节点
	for len(path) != 0 {
		for i := len(path) - 1; i >= 0; i-- {
			set.Parents[path[i]] = cur
			path = path[:len(path) - 1] // 模拟栈的弹出
		}
	}
	return cur
}

// IsSameSet 判断两个元素是否在同一个并查集中
func (set *UnionSet) IsSameSet(a, b int) bool {
	// 先检查a和b有没有登记
	if _, ok := set.Nodes[a]; !ok {
		return false
	}
	if _, ok := set.Nodes[b]; !ok {
		return false
	}

	// 比较a的最上的代表点和b最上的代表点
	return set.FindFather(set.Nodes[a]) == set.FindFather(set.Nodes[b])
}

// Union 合并两个元素
func (set *UnionSet) Union(a, b int) {
	// 先检查a和b有没有都登记过
	if _, ok := set.Nodes[a]; !ok {
		return
	}
	if _, ok := set.Nodes[b]; !ok {
		return
	}

	// 找到a的最上面的代表点
	aHead := set.FindFather(set.Nodes[a])
	// 找到b的最上面的代表点
	bHead := set.FindFather(set.Nodes[b])
	// 只有两个最上代表点内存地址不相同，需要union
	if aHead != bHead {
		// 由于aHead和bHead都是最上面的代表点，那么在sizeMap里可以拿到大小
		aSetSize := set.SizeMap[aHead]
		bSetSize := set.SizeMap[bHead]
		var big *Node
		var small *Node
		// 哪个小，哪个挂在下面
		if aSetSize >= bSetSize {
			big = aHead
			small = bHead
		} else {
			big = bHead
			small = aHead
		}

		// 把小集合直接挂到大集合的最上面的代表节点下面
		set.Parents[small] = big
		// 大集合的代表节点的size要吸收掉小集合的size
		set.SizeMap[big] = aSetSize + bSetSize
		// 把被吸收掉的小set删除掉
		delete(set.SizeMap, small)
	}
}
```
> 并查集用来处理连通性的问题特别方便

## 1.2 图相关算法
### 1.2.1 图的概念

1、由点的集合和边的集合构成

2、虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达，无向图可以理解为两个联通点互相指向的有向图

3、边上可能带有权值

### 1.2.2 图的表示方法

对于下面一张无向图，可以改为有向图：

```
graph LR;
A-->C
C-->A
C-->B
B-->C
B-->D
D-->B
D-->A
A-->D
```

#### 1.2.2.1 邻接表表示法

记录某个节点，直接到达的邻居节点：

A:  C,D

B:  C,D

C:  A,B

D:  B,A

A可以直接到达C和D, B可以直接到大C和D, C可以直接到达A和B, D可以直接到达B和A。图的邻接表表示法

如果是带有权重的边，可以封装我们的结构，例如A到C的权重是3,那么我们可以表示为A: C(3),D

#### 1.2.2.2 邻接矩阵表示法

我们把不存在路径的用正无穷表示，这里用'-'表示，例如A到C的边权重是3，可把上图表示为：

```
  A  B  C  D
A 0  0  3  -
B -  0  0  0
C 3  0  0  -
D 0  0  -  0
```

> 图算法并不难，难点在于图有很多种表示方式，表达一张图的篇幅比较大，coding容易出错。熟悉一种结构，遇到不同的表达方式，尝试转化成为我们熟悉的结构，进行操作。

点结构的描述：

```Go
// Node 图中的点元素表示
type Node struct {
	// 点的身份标识
	value int
	// 入度，表示有多少个点连向该点
	in int
	// 出度，表示从该点出发连向别的节点多少
	out int
	// 直接邻居：表示由自己出发，直接指向哪些节点。指向节点的总数等于out
	nexts []*Node
	// 直接下级边：表示由自己出发的边有多少
	edges []*Edge
}
```

边结构的描述：

```Go
// Edge 图中的边元素表示
type Edge struct {
	// 边的权重信息
	weight int
	// 出发的节点
	from *Node
	// 指向的节点
	to *Node
}
```

图结构的描述：

```Go
type Graph struct {
	// 点的集合，编号为1的点是什么，用map
	nodes map[int]*Node
	// 边的集合(用hash实现set)
	edges map[*Edge]string
}
```

任意图结构的描述，通过解析向上述的图结构进行转化。

### 1.2.3 图的遍历

例如该图：

```
graph LR;
A-->B
A-->C
A-->D
B-->C
B-->E
C-->A
C-->B
C-->D
C-->E
```

#### 1.2.3.1 宽度优先遍历

1、利用队列实现

2、从源节点开始依次按照宽度进队列，然后弹出

3、每弹出一个点，把该节点所有没有进过队列的邻接点放入队列

4、直到队列变空

> 宽度优先的思路：实质先遍历自己，再遍历自己的下一跳节点(同一层节点的顺序无需关心)，再下下跳节点......


我们从A点开始遍历：

1、A进队列--> Q[A]；A进入Set--> S[A]

2、A出队：Q[] , **打印A**；A直接邻居为BCD,都不在Set中，进入队列Q[D,C,B] , 进入S[A,B,C,D]

3、B出队：Q[D,C], B有CDE三个邻居，C已经在Set中, 放入E, S[A,B,C,D,E]，队列放E, Q[E,D,C]

4、 C出队，周而复始

```Go
// 从node出发，对图进行宽度优先遍历
func (node *Node) bfs() {
	if node == nil {
		return
	}
	Queue := make([]*Node, 0)
	// 图需要用set结构，因为图相比于二叉树有可能存在环
	// 即有可能存在某个点多次进入队列的情况。使用Set可以防止相同节点重复进入队列
	Set := make(map[*Node]string, 0)
	Queue = append(Queue, node)
	Set[node] = ""
	for len(Queue) != 0 {
		// 出队列
		cur := Queue[0]
		Queue = Queue[1:]
		fmt.Println(cur.value)
		for _, next := range cur.nexts {
			// 直接邻居，没有进入过Set的进入Set和队列
			// 用set限制队列的元素，防止有环队列一直会加入元素
			if _, ok := Set[next]; !ok { // Set中不存在, 则加入队列
				Set[next] = ""
				Queue = append(Queue, next)
			}
		}
	}
}
```

#### 1.2.3.2 深度优先遍历

1、利用栈实现

2、从源节点开始把节点按照深度放入栈，然后弹出

3、每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈

4、直到栈变空

> 深度优先思路：表示从某个节点一直往下深入，直到没有路了，返回。我们的栈实质记录的是我们深度优先遍历的路径

我们从A点开始遍历：

1、A进栈，Stack[A] **打印A**。弹出A，当前弹出的节点A去枚举它的后代BCD，B没加入过栈中。压入A再压入B,Stack[B,A]。**打印B**

2、弹出B,B的直接后代邻居为CE,C再栈中而E不在栈中。重新压B,压E，Stack[E,B,A]。**打印E**

3、弹出E,E有邻居D,D不在栈中。压回E，再压D,此时Stack[D,E,B,A]。**打印D**

4、 弹出D,D的直接邻居是A,A已经在栈中了。说明A-B-E-D这条路径走到了尽头。弹出D之后，当前循环结束。继续while栈不为空，重复操作

```Go
// 从node出发，对图进行深度优先遍历。借助栈
func (node *Node) dfs() {
	if node == nil {
		return
	}

	stack := make([]*Node, 0)
	// Set的作用和宽度优先遍历类似，保证重复的点不要进栈
	set := make(map[*Node]string, 0)
	// 进栈
	stack = append(stack, node)
	set[node] = ""
	// 打印时机是在进栈的时候
	// 同理该步可以换成其他处理逻辑，表示深度遍历处理某件事情
	fmt.Println(node.value)

	for len(stack) != 0 {
		cur := stack[len(stack) - 1]
		stack = stack[:len(stack) - 1]
		// 枚举当前弹出节点的后代
		for _, next := range cur.nexts {
			// 只要某个后代没进入过栈，进栈
			if _, ok := set[next]; !ok {
				// 把该节点的父亲节点重新压回栈中
				stack = append(stack, cur)
				// 再把自己压入栈中
				stack = append(stack, next)
				set[next] = ""
				// 打印当前节点的值
				fmt.Println(next.value)
				// 直接break，此时栈顶是当前next节点，达到深度优先的目的
				break
			}
		}
	}
}
```

### 1.2.4 图的拓扑排序

1、在图中找到所有入度为0的点输出

2、把所有入度为0的点在图中删掉，切消除这些点的影响边。继续找入度为0的点输出，删除，消边，周而复始

3、图的所有点都被删除后，依次输出的顺序就是图的拓扑排序

**要求：有向图且其中没有环**

**应用：事件安排，编译顺序**

> 在我们的项目中，项目之间互相依赖，就是拓扑排序的一个应用，从最底层依赖的包往上层编译，最终把总的项目编译通过。所以项目中循环依赖是编译不通过的

例如下列的有向无环图：

```
graph LR;
A-->B
B-->C
A-->C
C-->E
E-->F
C-->T
F-->T
```

图中的字母代表事情，做事情的先后顺序就是按照有向图的描述，请安排事情的先后顺序（拓扑排序）。

拓扑排序为：A B C E F T

```Go
// sortTopology 图的拓扑排序。返回拓扑排序的顺序list
func (graph *Graph) sortTopology() []*Node {
	// key：某一个node, value：该节点剩余的入度
	inMap := make(map[*Node]int)
	// 剩余入度为0的点，才能进这个队列
	zeroInQueue := make([]*Node, 0)
	// 拿到该图中所有的点集
	for _, node := range graph.nodes {
		// 初始化每个点，每个点的入度是原始节点的入度信息
		// 加入inMap
		inMap[node] = node.in
		// 由于是有向无环图，则必定有入度为0的起始点。放入到zeroInQueue
		if node.in == 0 {
			zeroInQueue = append(zeroInQueue, node)
		}
	}

	// 拓扑排序的结果，依次加入result
	result := make([]*Node, 0)

	for len(zeroInQueue) != 0 {
		// 该有向无环图初始入度为0的点，直接弹出放入结果集中
		cur := zeroInQueue[0]
		zeroInQueue = zeroInQueue[1:]
		result = append(result, cur)
		// 该节点的下一层邻居节点，入度减一且加入到入度的map中
		for _,next := range cur.nexts {
			inMap[next] = inMap[next] - 1
			// 如果下一层存在入度变为0的节点，加入到0入度的队列中
			if inMap[next] == 0 {
				zeroInQueue = append(zeroInQueue, next)
			}
		}
	}
	return result
}
```

### 1.2.5 图的最小生成树算法

> 最小生成树解释，就是在不破坏原有图点与点的连通性基础上，让连通的边的整体权值最小。返回最小权值或者边的集合

#### 1.2.5.1 Kruskal（克鲁斯卡尔）算法

> 连通性借助并查集实现

1、总是从权值最小的边开始考虑，依次考察权值依次变大的边

2、当前的边要么进入最小生成树的集合，要么丢弃

3、如果当前的边进入最小生成树的集合中不会形成环，就要当前边

4、如果当前的边进入最小生成树的集合中会形成环，就不要当前边

5、考察完所有边之后，最小生成树的集合也就得到了

```Go
package main

// kruskaMST 克鲁斯卡尔最小生成树算法。返回set
func kruskaMST(graph *Graph) map[*Edge]string {
	values := make([]int, 0)
	for k := range graph.nodes {
		values = append(values, k)
	}
	// 初始化一个并查集结构
	unitionSet := InitUnionSet(values)
	edgesHeap := make(Edges, 0)
	// 边按照权值从小到大排序，加入到堆
	for edge := range graph.edges {
		edgesHeap.Push(edge)
	}

	resultSet := make(map[*Edge]string)

	// 堆不为空，弹出小根堆的堆顶
	for len(edgesHeap) != 0 {
		// 假设M条边，O(logM)
		edge := edgesHeap.Pop().(*Edge)
		// 如果该边的左右两侧不在同一个集合中
		if !unitionSet.IsSameSet(edge.from.value, edge.to.value) {
			// 要这条边
			resultSet[edge] = ""
			// 联合from和to
			unitionSet.Union(edge.from.value, edge.to.value)
		}
	}
	return resultSet
}

// Edges 边的集合。实现小根堆
type Edges []*Edge

func (es Edges) Less(i, j int) bool {
	return es[i].weight <= es[j].weight
}

func (es Edges) Len() int {
	return len(es)
}

func (es Edges) Swap(i, j int) {
	es[i], es[j] = es[j], es[i]
}

func (es *Edges) Push(v interface{}) {
	*es = append(*es, v.(*Edge))
}

func (es *Edges) Pop() (x interface{}) {
	n := len(*es)
	x = (*es)[n-1]
	*es = (*es)[:n-1]
	return x
}

// UNode 并查集结构中的节点类型
type UNode struct {
	V int
}

type UnionSet struct {
	// 记录样本到样本代表点的关系。值到代表该值的Node节点的关系映射
	Nodes map[int]*UNode
	// 记录某节点到根祖宗节点的关系。
	// 比如b指向a，c指向a，d指向a，a指向自身
	// map中保存的a->a b->a c->a d->a
	RootFatherMap map[*UNode]*UNode
	// 只有当前点，他是代表点，会在sizeMap中记录该代表点的连通个数
	SizeMap map[*UNode]int
}

// InitUnionSet 初始化一个并查集结构
func InitUnionSet(values []int) *UnionSet {
	us := &UnionSet{}
	nodes := make(map[int]*UNode, 0)
	fatherMap := make(map[*UNode]*UNode, 0)
	sizeMap := make(map[*UNode]int, 0)
	for _, v := range values {
		node := &UNode{V: v}
		nodes[v] = node
		fatherMap[node] = node
		sizeMap[node] = 1
	}

	us.Nodes = nodes
	us.RootFatherMap = fatherMap
	us.SizeMap = sizeMap
	return us
}

// FindFather 在并查集结构中找一个节点的父亲根节点
// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
// 通过把路径上所有节点指向最上方的代表节点，目的是把findFather优化成O(1)的
func (set *UnionSet) FindFather(cur *UNode) *UNode {
	// 在找father的过程中，沿途所有节点加入当前容器，便于后面扁平化处理
	path := make([]*UNode, 0)
	// 当前节点的父亲不是指向自己，进行循环
	for cur != set.RootFatherMap[cur] {
		path = append(path, cur)
		// 向上移动
		cur = set.RootFatherMap[cur]
	}
	// 循环结束，cur此时是最上的代表节点
	// 把沿途所有节点拍平，都指向当前最上方的代表节点
	for len(path) != 0 {
		for i := len(path) - 1; i >= 0; i-- {
			set.RootFatherMap[path[i]] = cur
		}
	}
	return cur
}

// IsSameSet 判断两个元素是否在同一个并查集中
func (set *UnionSet) IsSameSet(a, b int) bool {
	// 先检查a和b有没有登记
	if _, ok := set.Nodes[a]; !ok {
		return false
	}
	if _, ok := set.Nodes[b]; !ok {
		return false
	}

	// 比较a的最上的代表点和b最上的代表点
	return set.FindFather(set.Nodes[a]) == set.FindFather(set.Nodes[b])
}

// Union 合并两个元素
func (set *UnionSet) Union(a, b int) {
	// 先检查a和b有没有都登记过
	if _, ok := set.Nodes[a]; !ok {
		return
	}
	if _, ok := set.Nodes[b]; !ok {
		return
	}

	// 找到a的最上面的代表点
	aHead := set.FindFather(set.Nodes[a])
	// 找到b的最上面的代表点
	bHead := set.FindFather(set.Nodes[b])
	// 只有两个最上代表点内存地址不相同，需要union
	if aHead != bHead {
		// 由于aHead和bHead都是最上面的代表点，那么在sizeMap里可以拿到大小
		aSetSize := set.SizeMap[aHead]
		bSetSize := set.SizeMap[bHead]
		var big *UNode
		var small *UNode
		// 哪个小，哪个挂在下面
		if aSetSize >= bSetSize {
			big = aHead
			small = bHead
		} else {
			big = bHead
			small = aHead
		}

		// 把小集合直接挂到大集合的最上面的代表节点下面
		set.RootFatherMap[small] = big
		// 大集合的代表节点的size要吸收掉小集合的size
		set.SizeMap[big] = aSetSize + bSetSize
		// 把被吸收掉的小set删除掉
		delete(set.SizeMap, small)
	}
}
```
> K算法求无向图的最小生成树，求权值是没问题的，如果纠结最小生成树的连通结构，实质是少了一侧，即A指向B, B指向A只会保留其一。可以手动补齐

#### 1.2.5.2 Prim算法

> P算法无需并查集结构，普通set即可满足

1、任意指定一个出发点，譬如A, A的直接边被解锁

2、在A解锁的边里选择一个最小的边，该边两侧有没有新节点，如果有选择该边。没有就舍弃该边

3、在被选择的新节点中再解锁该节点的直接边

4、周而复始，直到所有点被解锁

```Go
package main

// primMST prim算法实现图的最小生成树
func (graph *Graph) primMST() map[*Edge]string {
	// 哪些点被解锁出来了
	nodeSet := make(map[*Node]string, 0)
	// 边的小根堆
	edgesHeap := make(Edges, 0)
	// 已经考虑过的边，不要重复考虑
	edgeSet := make(map[*Edge]string, 0)
	// 依次挑选的的边在resultSet里
	resultSet := make(map[*Edge]string, 0)
	// 随便挑了一个点,进入循环处理完后直接break

	for _, node := range graph.nodes {
		// node 是开始点
		if _, ok := nodeSet[node]; !ok {
			// 开始节点保留
			nodeSet[node] = ""
			// 开始节点的所有邻居节点全部放到小根堆
			// 即由一个点，解锁所有相连的边
			for _, edge := range node.edges {
				if _, ok := edgeSet[edge]; !ok {
					edgeSet[edge] = ""
					// 加入小根堆
					edgesHeap.Push(edge)
				}
			}

			for len(edgesHeap) != 0 {
				// 弹出解锁的边中，最小的边
				edge := edgesHeap.Pop().(*Edge)
				// 可能的一个新的点,from已经被考虑了，只需要看to
				toNode := edge.to
				// 不含有的时候，就是新的点
				if _, ok := nodeSet[toNode]; !ok {
					nodeSet[toNode] = ""
					resultSet[edge] = ""
					for _, nextEdge := range toNode.edges {
						// 没加过的，放入小根堆
						if _, ok := edgeSet[nextEdge]; !ok {
							edgeSet[nextEdge] = ""
							edgesHeap.Push(edge)
						}
					}
				}
			}
		}
	}
	// 直接break意味着我们不用考虑森林的情况
	// 如果不加break我们可以兼容多个无向图的森林的生成树
	// break;
	return resultSet
}

// Edges 边的集合。实现小根堆
type Edges []*Edge

func (es Edges) Less(i, j int) bool {
	return es[i].weight <= es[j].weight
}

func (es Edges) Len() int {
	return len(es)
}

func (es Edges) Swap(i, j int) {
	es[i], es[j] = es[j], es[i]
}

func (es *Edges) Push(v interface{}) {
	*es = append(*es, v.(*Edge))
}

func (es *Edges) Pop() (x interface{}) {
	n := len(*es)
	x = (*es)[n-1]
	*es = (*es)[:n-1]
	return x
}
```

### 1.2.6 图的最短路径算法

#### 1.2.6.1 Dijkstra(迪杰特斯拉)算法

> Dijkstra算法必须要求边的权值不为负，且必须指定出发点。则可以求出发点到所有节点的最短距离是多少。如果到达不了，为正无穷

1、Dijkstra算法必须指定一个源点

2、生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都未正无穷大

3、从距离表中拿出没拿过记录里的最小记录，通过这个点出发的边，更新源点到各个点的最小距离表，不断重复这一步

4、源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了

```Go
package main

import "math"

// Node 图中的点元素表示
type Node struct {
	// 点的身份标识
	value int
	// 入度，表示有多少个点连向该点
	in int
	// 出度，表示从该点出发连向别的节点多少
	out int
	// 直接邻居：表示由自己出发，直接指向哪些节点。指向节点的总数等于out
	nexts []*Node
	// 直接下级边：表示由自己出发的边有多少
	edges []*Edge
}

// Edge 图中的边元素表示
type Edge struct {
	// 边的权重信息
	weight int
	// 出发的节点
	from *Node
	// 指向的节点
	to *Node
}

// Graph 图结构
type Graph struct {
	// 点的集合，编号为1的点是什么，用map
	nodes map[int]*Node
	// 边的集合(用hash实现set)
	edges map[*Edge]string
}

// dijkstra算法-图的最短路径算法
// 给定一个图的节点，返回这个节点到图的其他点的最短距离
// 某个点不在map中记录，则from到该点位正无穷
func dijkstra(from *Node) map[*Node]int {
	// 从from出发到所有点的最小距离表
	distanceMap := make(map[*Node]int, 0)
	// from到from距离为0
	distanceMap[from] = 0
	// 已经求过距离的节点，存在selectedNodes中，不会再被选中记录
	selectedNodesSet := make(map[*Node]string)
	// from 0 得到没选择过的点的最小距离
	minNode := getMinDistanceAndUnselectedNode(distanceMap, selectedNodesSet)
	// 得到minNode之后
	for minNode != nil {
		// 把minNode对应的距离取出,此时minNode就是桥连点
		distance := distanceMap[minNode]
		// 把minNode上所有的邻边拿出来
		// 这里就是要拿到例如A到C和A到桥连点B再到C哪个距离小的距离
		for _, edge := range minNode.edges {
			// 某条边对应的下一跳节点toNode
			toNode := edge.to
			// 如果关于from的distencMap中没有去toNode的记录，表示正无穷，直接添加该条
			if _, ok := distanceMap[toNode]; !ok {
				// from到minNode的距离加上个minNode到当前to节点的边距离
				distanceMap[toNode] = distance + edge.weight
			} else { // 如果有，看该距离是否更小，更小就更新
				minDistance := int(math.Min(float64(distanceMap[toNode]), float64(distance + edge.weight)))
				distanceMap[edge.to] = minDistance
			}
		}
		// 锁上minNode，表示from通过minNode到其他节点的最小值已经找到
		// minNode将不再使用
		selectedNodesSet[minNode] = ""
		// 再在没有选择的节点中挑选MinNode当成from的桥接点
		minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodesSet)
	}
	// 最终distanceMap全部更新，返回
	return distanceMap
}

// getMinDistanceAndUnselectedNode 得到没选择过的点的最小距离
func getMinDistanceAndUnselectedNode(distanceMap map[*Node]int, selectedNodesSet map[*Node]string) *Node {
	var minNode *Node = nil
	minDistance := math.MaxInt
	for node,distance := range distanceMap {
		// 没有被选择过，且距离最小
		if _, ok := selectedNodesSet[node]; !ok && distance < minDistance {
			minNode = node
			minDistance = distance
		}
	}
	return minNode
}

// 我们可以借助小根堆来替代之前的distanceMap。达到优化算法的目的
// 原因是之前我们要遍历hash表选出最小距离，现在直接是堆顶元素
// 但是我们找到通过桥节点更小的距离后，需要临时更该堆结构中元素数据
// 所以系统提供的堆我们需要改写。略
```

#### 1.2.6.2 floyd算法

> 图节点的最短路径，处理权值可能为负的情况。三层for循环，比较简单