"图算法"

  "算法"

Posted by Xu on June 22, 2018

图可以用G=(V,E)来表示,每个图都包括一个顶点集合V和一个边集合E,顶点总数记为|V|,边总数记为|E|

  • 稀疏图:边数较少的图
  • 密集图:边数较多的图
  • 完全图:包含所有可能边的图
  • 带权图:边上标有权的图
  • 邻接点:一条边所连的两个顶点
  • 简单路径:路径上不包含重复顶点的图
  • 回路:将某个顶点连接到本身,且长度大于等于3的路径
  • 无环图:不带回路的图

图的表示

  • 图有两种常用的表示方法:
    • 邻接矩阵
    • 邻接表

graph_alg

1.邻接矩阵

使用一个二维矩阵来表示图:

  • (i,j)=1,表示顶点i到顶点j之间有一条边(非带权图
  • (i,j)=n,表示顶点i到顶点j之间有一条权重为n的边(带权图

使用邻接矩阵的空间代价总是O(|V|^2)

2.邻接表

邻接表使用一个顶点指针数组来表示:

  • 数组的元素i表示顶点i的指针,它是一个链表的头结点
  • 链表其余的顶点表示与顶点i之间存在边的顶点

邻接表的空间代价与图中边的数目和顶点的数目均有关系。每个顶点要占据一个数组元素的位置,且每条边必须出现在其中某个顶点的边链表中

图的遍历

图的遍历有两种遍历方式:

  1. 广度优先遍历
  2. 深度优先遍历

且这两种遍历的节点路径为两个节点的最短路径:

  • 因为这两种遍历当弹出一个节点时,其 所有邻接(注意:是所有)的节点都被压入,访问,而一个节点 只能被访问一次
  • 所以如果源节点到该节点存在一条为2的路径,广度优先遍历绝对会将该节点归类于第二层次节点集合,深度优先同样如此。

BFS:广度优先遍历

BFS执行过程将产生一棵BFS(广度优先搜索)树graph_alg

  1. 使用一个队列,根节点入队
  2. 弹出根节点,将根节点的邻边节点入队
  3. 不断弹出队列中的节点,每弹出一个节点,都将该节点的邻边节点入队(必须保证每个节点只被访问一次)
  4. 循环3直到队列为空

整个BFS过程:

graph_alg

DFS:深度优先遍历

深度优先搜索使用的结构则不同与广度优先搜索,采用的是栈结构,先进后出。

  1. 先访问定点v,将与v节点相连边的所有节点压入栈中
  2. 弹出栈顶元素,同样压入弹出栈顶的相连边的节点(同样所有的节点只能被访问一次
  3. 循环2直到栈为空

整个DFS过程:

graph_alg

拓扑排序

(DAG)有向无环图可以描述这样一种场景:有一组任务,任务的执行顺序之间具有依赖性,一些任务必须在另一些任务完成之后才开始执行,如下图:

graph_alg

在这种场景下,任务之间的依赖关系不能出现环,否则任何一个都无法开始执行。将一个(DAG)有向无环图中所有顶点在不违反先决条件规定的基础上排成线性序列的过程就是拓扑排序

如:

graph_alg

一个可能的排序为:J6, J7, J5, J4, J2, J3, J1

有两种方法可以进行拓扑排序:

  • 基于DFS的方法(递归)
    • 当访问某个顶点时,不对这个顶点进行任何处理。当递归返回到这个顶点时,打印这个顶点
    • 这将产生一个逆序的拓扑排序。对其进行一次反序操作就可以得到一个拓扑排序的序列。
    • 序列从哪个顶点开始并不重要,只要所有顶点最终都能被访问到
  • 基于BFS的方法(迭代)
    • 首先访问所有的边,计算指向每个顶点的边数(即计算每个顶点的先决条件数目)
    • 将所有没有先决条件(指向该节点的边数为0,说明为根节点,入口)的顶点放入队列,然后开始处理队列。
    • 当从顶点中删除一个顶点时,把它打印出来,同时将其所有相邻顶点的先决条件计数减1(减去该删除节点指向相邻节点边所贡献的先决条件)
    • 当某个相邻顶点的计数为 0时,就将其放入队列。如果还有顶点未被打印,而队列已经为空,则图中必然包含回路

最小生成树

最小生成树(MST)是一个包括图G所有顶点及其部分边的图,包括的边是G的子集,满足下列条件:

  • 这个子集中所有边的权之和为所有子集中最小的
  • 子集中的边能保证图是连通的

下面是一个最小生成树的例子:

graph_alg

生成最小生成树有两种算法:

  1. Kruskal算法
  2. Prim算法

Kruskal算法

思路(贪心策略):

  1. 先将每个节点都视为一棵树,这样所有的节点构成一个森林
  2. 检查当前最小权值的边,是否可以将两棵树合并成一棵树
    • 如果当前最小权值的边在同一棵树上,则不添加到最小生成树中
    • 不在同一棵树上添加到最小生成树
  3. 循环2直到所有的节点连接为一棵树

graph_alg

思考:

  1. 最小生成树中,必含最小权值的边和第二小权值的边?

Prim算法

思路(贪心策略):

  1. 任意一个节点开始,添加到最小生成树的节点集
  2. 找到与节点集中所有相连中可以扩展新节点到节点集中最小权值的边,添加到最小生成树
  3. 循环2直到所有的节点都被添加到节点集中

Prim算法过程:

graph_alg

单源最短路径

Dijkstra算法

该算法解决的是带权重的有向图上单元最短路径问题,且所有的权值为非负值。

思路(贪心策略):

  1. 先将源节点添加到集合S中,更新源节点的邻接节点的距离信息
  2. 根据剩余节点集合U中的距离信息找到一个距离最短的节点添加到S(添加到S就是说明已经确定s到该点的最短距离),同时,以该节点更新它附近的节点距离
  3. 循环操作2,将所有的节点添加到S集合即可

graph_alg