的完美匹配
最小生成树
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最小生成树
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最小生成树
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最小生成树
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最短路问题
在加权图中找到两点之间的最短路径 （权值和最小）
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
11 10 c 1 MAX
2 5 f 3 1 e
1 5 MAX
d
终点
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
11 10 c 1 MAX
2 5 f 3 1 e
1 5tra求解过程
最短路问题
1 b 1 0 a
图论
蒋威 2008-12-25
图论
基本概念 最小生成树 最短路问题 二部图匹配 *网络流
图论
基本概念 最小生成树 最短路问题 二部图匹配 *网络流
基本概念
图的数学定义：二元组G：<V，E>
V≠ ：点集；
E：边集。
无向图，有向图 (混合图)。 无向图
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最小生成树
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
最小生成树
Kruskal方法：
连通图性； 点割集（割点，块），点连通度； 边割集（桥），边连通度； 弱连通，单向连通，强连通；
有向图
基本概念
图的表示法
邻接表/邻接矩阵
基本概念
欧拉图
欧拉通路：经过图中所有边一次且仅一次的通路 欧拉回路：经过图中所有边一次且仅一次的回路 半欧拉图/欧拉图
哈密顿图
图论
基本概念 最小生成树 最短路问题 二部图匹配 *网络流
最小生成树
边带权值 找到无向图G=(V，E)的 最小生成树T Prim方法：
点集V初始为空，每次选
b 4 a 8 f 11 7
8 2 g 6 1
c 9 14 d 10 e
择距离V最近的点加入 时间复杂度O(ElogV)
最小生成树
找到图G=(V，E)的 最小生成树T。
4
b
8 2
c 9 14 6 d 10 e
Prim方法：
点集V初始为空，每次选
a 8
11 7 f
g
择距离V最近的点加入
1
最小生成树
找到图G=(V，E)的 最小生成树T。
4
b
8 2
c 9 14 6 d 10 e
Prim方法：
点集V初始为空，每次选
哈密顿通路：经过图中所有顶点一次且仅一次的通路 哈密顿回路：经过图中所有顶点一次且仅一次的回路 半哈密顿图/哈密顿图
基本概念
树
连通 无回路
有向图->有向树 无向图->无向树 子图/生成子图/生成树
G’=(V’,E’)是G=(V,E)的子图，如果G’ G,
V’ V G’是无向图G的生成子图，如果G’是G的子图，且V’ = V T是无向图G的生成树，如果T是G的生成子图，且T是树
Prim方法：
点集V初始为空，每次选
a 8
11 7 f
g
择距离V最近的点加入
1
最小生成树
找到图G=(V，E)的 最小生成树T。
4
b
8 2
c 9 14 6 d 10 e
Prim方法：
点集V初始为空，每次选
a 8
11 7 f
g
择距离V最近的点加入
1
最小生成树
找到图G=(V，E)的 最小生成树T。
Dijkstra算法
Bellman-ford算法 Floyd-Warshall算法
最短路问题
Dijkstra算法
E.W.Dijkstra，1959 算法描述：
1）根据起始结点，为每一个结点标号 2）寻找标号最小的新结点，并更新其它结点的标号 3）重复上一步，直到找到目标结点
4
b
8 2
c 9 14 6 d 10 e
Prim方法：
点集V初始为空，每次选
a 8
11 7 f
g
择距离V最近的点加入
1
最小生成树
Kruskal方法：
每次选择两个端点不在
同一连通分量的边加入 时间复杂度O(ElogE)
a
b 4 11 8 f 7
8 2 g 6 1
c 9 14 d 10 e
a 8
11 7 f
g
择距离V最近的点加入
1
最小生成树
找到图G=(V，E)的 最小生成树T。
4
b
8 2
c 9 14 6 d 10 e
Prim方法：
点集V初始为空，每次选
a 8
11 7 f
g
择距离V最近的点加入
1
最小生成树
找到图G=(V，E)的 最小生成树T。
4
b
8 2
c 9 14 6 d 10 e
只适用于处理非负权图
时间复杂度O(ElogV)，O(V^2)
最短路问题
1 b 1 0 a
起点
MAX 10 c 1 MAX
2 5 f 5 1 e
1 5 MAX
d
终点
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
MAX 10 c 1 MAX
2 5 f 5 1 e
1 5 MAX
d
终点
起点
11 10 c 1 MAX
2 5 f 3 1 e
1 5 4
d
终点
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
11 10 c 1 MAX
2 5 f 3 1 e
1 5 4
d
终点
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
5 10 c 1 9
2 5 f 3 1 e
1 5 4
d
终点
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
5 10 c 1 9
2 5 f 3 1 e
1 5 4
d
终点
Dijkstra求解过程
最短路问题
1 b 1 0 a
起点
5 10 c 1 6
2 5 f 3 1 e
1 5 4
d
终点
Dijkstra求解过程
