<commit_before>---
layout: post
title: 几个图算法的总结归纳
---


![](http://7vzrt9.com1.z0.glb.clouddn.com/graph.png)

*上图是图里的一棵最小生成树，也是让自己练习算时，输出不再是数字或者矩阵， 而做了一点多余的工作。借此契机，重新审视了几个图算法。*


### 写在最前面
图，挺好玩的。一个二维数组可以表示一张图，几乎是实现起来最简单的数据结构了。但是，图与其他数据结构不同，它并不强调，为程序员提供高效的接口，来完成一些特定的事物，而是，提供一些算法或者思路来，如何探索，如果将图里隐藏的信息显示出来.......

### 最小生成树
树是没有回路的图，所以，图的探索方法也适用于树。比如，如何得到一棵树的高度？我想大概可以这么实现。
![](http://7vzrt9.com1.z0.glb.clouddn.com/code1.png)
得到树的高度，有深度优先搜索的样子，为了优雅选择了漂亮的写法。也有不精致的写法，比如以前写求解数独游戏的程序。就不贴了。接下来，谈谈广度优先。

Prim算法采用了广度优先的思想。将图的所有节点划分为两个集合，一个是已经找到的，一个是还没找到的，分别设为s1，s2。算法将要实现的一件事情，在s2中找到一个节点，使它到s1的距离最小。于是需要遍历s1到s2的所有边，选出最短的一条。

深度和广度优先都将划分两个集合，它们只是找下一个节点的方式不同。

Prim算法还有一个重要的特点，贪婪思想。每次都找最短的，意味着最短的就是最好的。很遗憾，我能体会，但无法证明它。另一个使用贪婪思想的算法，Kruskal算法。Kruskal算法实现的一个细节，如何判断回路。简单来说，两个节点在同一棵树上，可以判断新加入的节点构成回路。然后，再实现，将两个树合并成一棵树的操作。好吧。其实，事实上，我只记录的每棵树的节点，没有记录节点之间的关系，所以实现起来简单了许多。判断是否构成回路还有其他的方法。需要用到一点线代代数的知识，回路矩阵和判断是否线性相关。

### 最短路径
Dijkstra算法，有时候我感觉很像Prim算法。因为我认为"标记-更新"并不是什么了不起的技术，只是需要一个值来记录，已经发现的节点中，到该节点的距离。而每做一次探索，就会确定一个节点，而这个它们的路径是，探索出来的部分图中，最短的一条。好吧。我能理解又无法证明了。这个关系到算法要求每条边的权重为什么不能为负。想强行用反证法证明一下，想想还是算了。所以，我认为理解了Prim算法也就理解了Dijkstra算法。

上面是单源最短路径，接下来是所有点间最短路径问题。

我不得不摘抄两段《算法导论》上的话了（为了表述完整，修改了一部分）。

+ 朴实的最短路径的最短路径结构
	
    	考虑从节点 i 到节点 j 的一条最短路径 p，假设 p 至多包含 m 条边，还假设没有权重的负值环路，且 m 为有限值。如果 i = j，则 p 的权重为0且不包含任何边。如果节点 i 和节点 j 不同，则将路径 p 分解为路径 q (i -> k) -> j，其中路径q至多包含m - 1 条边。根据引理（最短路径的子路径也是最短路径），q 是 i 到 k 的一条最短路径。
 






















<commit_msg>check<commit_after>---
layout: post
title: 几个图算法的总结归纳
---


![](http://7vzrt9.com1.z0.glb.clouddn.com/graph.png)

*上图是图里的一棵最小生成树，也是让自己练习算时，输出不再是数字或者矩阵， 而做了一点多余的工作。借此契机，重新审视了几个图算法。*


### 写在最前面
图，挺好玩的。一个二维数组可以表示一张图，几乎是实现起来最简单的数据结构了。但是，图与其他数据结构不同，它并不强调，为程序员提供高效的接口，来完成一些特定的事物，而是，提供一些算法或者思路来，如何探索，如果将图里隐藏的信息显示出来.......

### 最小生成树
树是没有回路的图，所以，图的探索方法也适用于树。比如，如何得到一棵树的高度？我想大概可以这么实现。
![](http://7vzrt9.com1.z0.glb.clouddn.com/code1.png)
得到树的高度，有深度优先搜索的样子，为了优雅选择了漂亮的写法。也有不精致的写法，比如以前写求解数独游戏的程序。就不贴了。接下来，谈谈广度优先。

Prim算法采用了广度优先的思想。将图的所有节点划分为两个集合，一个是已经找到的，一个是还没找到的，分别设为s1，s2。算法将要实现的一件事情，在s2中找到一个节点，使它到s1的距离最小。于是需要遍历s1到s2的所有边，选出最短的一条。

深度和广度优先都将划分两个集合，它们只是找下一个节点的方式不同。

Prim算法还有一个重要的特点，贪婪思想。每次都找最短的，意味着最短的就是最好的。很遗憾，我能体会，但无法证明它。另一个使用贪婪思想的算法，Kruskal算法。Kruskal算法实现的一个细节，如何判断回路。简单来说，两个节点在同一棵树上，可以判断新加入的节点构成回路。然后，再实现，将两个树合并成一棵树的操作。好吧。其实，事实上，我只记录的每棵树的节点，没有记录节点之间的关系，所以实现起来简单了许多。判断是否构成回路还有其他的方法。需要用到一点线代代数的知识，回路矩阵和判断是否线性相关。

### 最短路径
Dijkstra算法，有时候我感觉很像Prim算法。因为我认为"标记-更新"并不是什么了不起的技术，只是需要一个值来记录，已经发现的节点中，到该节点的距离。而每做一次探索，就会确定一个节点，而这个它们的路径是，探索出来的部分图中，最短的一条。好吧。我能理解又无法证明了。这个关系到算法要求每条边的权重为什么不能为负。想强行用反证法证明一下，想想还是算了。所以，我认为理解了Prim算法也就理解了Dijkstra算法。

上面是单源最短路径，接下来是所有点间最短路径问题。

我不得不摘抄两段《算法导论》上的话了（为了表述完整，修改了一部分）。

+ 朴实的最短路径的最短路径结构
	
```
考虑从节点 i 到节点 j 的一条最短路径 p，假设 p 至多包含 m 条边，还假设没有权重的负值环路，且 m 为有限值。如果 i = j，则 p 的权重为0且不包含任何边。如果节点 i 和节点 j 不同，则将路径 p 分解为路径 q (i -> k) -> j，其中路径q至多包含m - 1 条边。根据引理（最短路径的子路径也是最短路径），q 是 i 到 k 的一条最短路径。
 ```























{'fraction_non_alphanumeric': 0.12867132867132866, 'fraction_numerical': 0.011888111888111888, 'mean_word_length': 9.109540636042404, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4147604', 'n_tokens_mistral': 2586, 'n_tokens_neox': 3001, 'n_words': 110}