图论算法中，如何高效求解最小生成树问题？

本文共计6613个文字，预计阅读时间需要27分钟。

预习了一点图论算法，记录一下：分为三部分记录：

1.概念、一笔画问题

2.最短路径、算法

3.最小生成树、算法

1st. 一笔画问题

首先明确以下概念：

1.欧拉通路：图中经过每条边恰好一次的路径

预习了一点图论的算法，记录一下：

我将分为三部分记录：

1.概念&一笔画问题

2.最短路算法

3.最小生成树算法

1st. 一笔画问题

首先明确以下几个概念：

1、欧拉通路：恰好通过图中的每条边仅一次的通路。

2、欧拉回路：是欧拉路径且起点和终点是同一个点。

3、欧拉图：存在欧拉回路的图。

关于一笔画问题的定理：

　　存在欧拉路的条件：图是连通的，且存在0个或2个奇点。如果存在2个奇点，那么这两个奇点一定是这个图的起点和终点。

　　如果存在欧拉回路的话，就不会有奇点。