图算法概论

超、凢脫俗 2022-07-16 00:46 148阅读 0赞

1. 图的表示

> 图的表示法有两种，邻接表和邻接矩阵法，这两种方法既可以表示有向图也可以用于表示无向图。邻接表方法在稀疏的图中比较节省资源，但是邻接矩阵法在密度比较高的情况下比较好。

2. 搜索算法

> 搜索一个图示有序地沿着图的边访问所有的定点，图的搜索技术是图算法领域的核心
> 
> a. 广度优先搜索（Breadth-first search,BFS）
> 
> 过程：
> 
> 对于无向图来说，广度优先搜索也是获得最短路径的算法之一。
> 
> 广度优先搜索会产生广度优先树。
> 
> b. 深度优先搜索（Depth-first search, DFS）
> 
> 过程：
> 
> 深度优先搜索会产生深度优先森林。

3. 最小生成树

> 将所有的顶点连接，并且所有边权值之和最小的树。 最小生成树并不是唯一的，但是权值之和是唯一的。最小生成树，两种贪心方法，Kruskal(/kru:ska:/ 克鲁卡尔)和Prim(普利姆)。
> 
> a. Kruskal算法
> 
> 算法的主要思想是：
> 
>       I. 将所有边的权值排序，
> 
>       II. 在未选过的边中，选择其中权值最小的边，如果该边是安全边（连接两个不同的树），就将选择该边，否则丢弃。
> 
> b. Prim算法

>      I.随意选择一个顶点，从该顶点开始，构造树，每次选与该树临近的并且权值最小的顶点。

4. 最短路径

> 路径，就是从一个顶点到另一个顶点的所有边。一个顶点到另一个顶点的路径有多种，其中路径中边和最小的那个路径叫最短路径。
> 
> 最短路径有几种情况：
> 
> 1. 单源最短路径
> 
> 单源表示单个源节点，单源最短路径就是计算单个源节点到其他各个节点的最短路径。计算方法有 Bellman-ford算法（广泛，可以在存在负权边的情况下）和Dijkstra（/jikstra:/迪杰斯特拉，在不存在负权边的情况下，比bellman-ford有更好的表现）。
> 
> 2. 一对顶点间的最短路径
> 
> 可以有单源最短路径计算。
> 
> 2. 每对顶点间的最短路径
> 
> 按理来说，单源最短路径可以直接用来计算每对顶点间最短路径，但是在每对顶点间最短路径上是有特殊优化的。计算方法有Floyd-warshall算法（属于动态规划算法）和稀疏图上的Johnson算法。

5. 最大流

> 什么叫最大流？ 举一个简单的例子，假设每条有向边认为是传输物质的管道，每个管道的最大物质通过速度是固定的，管道相互连接，最大流就是物质从入口到出口流动的最大速率。
> 
> 最大流里面有几个概念，流网络G=(V，E)是一个有向图，每条边(u,v)的权重都是非负的，源点s是入口点，汇点t是出口点。多源点和多汇点的流网络可以简化为单源点，单汇点的问题。
> 
> 解决最大流的算法有Ford-Fulkerson方法。一些组合问题可以很容易的转换为最大流问题，如最大二分匹配问题。

6. 欧拉路

> 欧拉路概念：
> 
> 欧拉回路概念：
> 
>

7. 哈密顿路

> 哈密顿路概念：

8. 匹配与覆盖

9. 网络流

> 残量网络概念：
> 
> 增广路径概念：
> 
> 最小费用流：

10. 独立集、团与支配集

> 独立集：