图论算法

1 图的遍历

• 树的遍历实际上也可视为一种特殊的图的遍历。
• 因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visited[]来标记顶点是否被访问过。

1 BFS

• BFS类似于树的层序遍历
• BFS的遍历过程可以得到一颗广度优先生成树

BFS的应用

• 使用BFS，我们可以求解 非带权图的单源最短路径问题

2 DFS

• DFS类似于树的先序遍历
• DFS的遍历过程可以得到一颗深度优先生成树

2 最小生成树

• 一个连通图的（DF/BF）生成树包含图的所有顶点，并且只包含最少的边，若看起一条边，则会使生成树变成非连通图，若增加一条边，则会形成一条回路。

• 对于带权连通无向图G，生成树不同，树的权（树中所有边上权值的集合）也可能不同。对于图G的所有生成树，其中树的权值最小的树称为最小生成树。

• 最小生成树的特征

  • 不唯一
  • 权值之和唯一
  • 边数等于顶点数减1

• 构造最小生成树的算法基本都利用了最小生成树的以下性质

  • 假设G=(V, E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一颗包含边(u, v)的最小生成树。

Prim算法和Kruskal算法都利用了上述性质，基于贪心算法的策略。

1 Prim算法

• Prim算法的执行非常类似于寻找图的最短路径的Dijkstra算法
• Prim算法构造最小生成树的过程如下图所示

初始时从图中任取一顶点加入最小生成树T，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，以此类推，每次操作后T中的顶点和边数都增1，直至图中所有的顶点都并入T

2 Kruskal算法

• 与Prim算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法
• Kruskal算法构造最小生成树的过程如下图所示

3 最短路径

• BFS查找最短路径只是对无权图而言的，当图是带权图时就不能使用BFS求解了。

• 求解最短路径的算法通常都依赖于以下性质

  • 两点之间的最短路径也包含了路径上其他顶点间的最短路径

• 带权有向图的最短路径问题可分为两类

  • 单源最短路径

即求图中某一顶点到其他各顶点的最短路径，可通过Dijkstra算法求解

• 多源最短路径

求每对顶点间的最短路径，可通过Floyd算法求解