最小生成树(MST)

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 [1] 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

Kruskal算法

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止.

Kruskal算法的基本思想为：初始时隐去所有的边，这样图中每个顶点都自成一个连通块。之后执行下面的步骤：

1.对所有的边按照从小到大排序。
2.按照边权从小到大测试所有的边，如果当前测试的边所连接的两个顶点不在一个连通块中，则把这条测试边加入当前最小生成树中；否则，将边舍去。
3.执行步骤2，直到最小生成树的边数等于总顶点的数目减一或是测试完所有边结束。当结束时最小生成树的边数小于总顶点数减一，则该图不连通。

poj.1637.Sightseeing tour

欧拉图

• 欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。
• 欧拉通路：即可以不回到起点，但是必须经过每一条边，且只能一次。也叫”一笔画”问题。
• 基图：基图是针对有向图的说法，是忽略有向图的方向得到的无向图。
• 欧拉图:存在欧拉回路的图。

性质与定理：

定理1:无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。
定理2:有向图G为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。

欧拉回路

判断是否存在欧拉回路

• 1.是否连通
  并查集
• 2.连通度
  奇度的点称为奇点，反之偶点
  有向图 入度和出度
  无向图 入出度

查找欧拉回路路径

• 1.查找结点路径
• 2.查找边路径

欧拉通路

欧拉回路

回溯法

弗罗莱(Fluery)算法

Hierholzer算法(插入回路法)