算法-图论

1 定义

图G=（V，E）：由顶点集V和边集E组成。 边（v，w）：一幅点对组成，有时也称为弧（arc） 有向图（digraph）：点对是有向的图 无向图：要求边是互异的 邻接(adjacent): w和v邻接，当且仅当（v，w）属于E。无向图中w、v相互邻接。

路径（path）：是一个顶点序列，w1，w2,w3,w4,…..wN使得（wi,wi+1）属于E，1<=i<N. 路径的长等于该路径上边的数量N-1. 环(loop):从一个顶点到它自身的边（v,v). 简单路径: 一条路径上面的顶点都是互异的。第一个顶点和最后一个顶点可能相同。

有向图的圈（cycle）：w1=wN&&长至少为1的路径；如果为简单路径则为简单圈。 有向无圈图（DAG）：一个有向图没有圈，成为acyclic

连通（connected）：无向图中从每一个顶点到每个其他顶点都存在一条路径 基础图（underlying graph）：有向图去掉方向后形成的图 强连通（strongly connected）：具有连通特性的有向图。 弱联通（weakly connected）：基础图是连通的有向图 完全图（complete graph）：每一对顶点都存在一条边

表示图有两种方式

• 邻接矩阵： 适合稠密图。空间复杂度 O（V2）
• 邻接表：适合稀疏图。空间复杂度 O（E+V）

拓扑排序（topsort）：是针对有向无圈图的顶点的一种排序

• 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
• 从图中删除该顶点和所有以它为起点的有向边。
• 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

2 涉及算法

2.1 拓扑排序

• Kahn算法
• 基于DFS的算法 O(E+V)

2.2 最短路径算法

2.2.1 实现

• 无权最短路径-BFS 广度优先搜索
• 赋权最短路径-Dijkstra算法（Greedy算法）

2.2.2 应用

应用原则，高能到低能转变。

• 下坡滑雪问题。重力势能
• 化学反应问题。化学能

应用知道方法论-关键路径分析法 无圈图中，所有节点执行完毕, 每个节点最早完成时间计算：找出从第一个事件到最后一个事件的最长路径。 EC（Early Complete time） EC1=0 ECw=max(ECv+Cv,w)

每个事件能够完成而又不影响最后完成时间的最晚时间 LC（lastest complete time） LCn=ECn LCv=min(LCw-Cv,w)

WordLadder

2.3 网络流

最大流算法，有一篇博文讲的比较清晰 最大流

2.4 最小生成树

针对无向图的,最小生成树存在当且仅当G是连通的。 最小生成树