图论基础
阅读数:167 评论数:0
跳转到新版页面分类
算法/数据结构
正文
一、概述
1、图的表示法
图G = (V, E)的表示有邻接表和邻接矩阵两种形式。通常，对于| E |远小于| V | ^ 2的稀疏图，用邻接表比较合适。若图稠密或很小，或必须很快判别给定的两个顶点是否存在连接的边时，通常用邻接矩阵表示法。
2、关键点(Articulation Point)和桥(Bridge)
对于图G = (V, E)，若移除点v可以把图分离，那么v是一个关键点。若移除边e可以把图分离，那么e是桥。
3、回溯(Backtracking)
当顶点v的所有边都被探寻过后，搜索回到发现顶点v有起始点的那些边。这个过程叫做回溯。
4、拓扑排序(Topology Sorting)
拓扑排序说明了如何对一个有向无回路图（DAG）运用DFS进行排序。
当对G = (V, E)进行排序后，结果为该图所有顶点的一个线性序列，使得所有有向边均从左指向右。
这里需要时间戳的概念。建立全局变量time，每当发现一个顶点v, time+1记录在d[v]中; 每结束检查v时（即处理v完毕时），time+1记录在f[v]中。如果根据f[v]的值来逆序排序，那么结果就是处理顶点的先后顺序。
易知，拓扑排序的时间复杂度为O(V + E)。
5、连通图(Connected Graph)
连通图的定义是基于连通的概念。在一个无向图 G 中，若从顶点u到顶点v有路径相连(当然从v到u也一定有路径)，则称u和v是连通的。如果 G 是有向图，那么连接u和v的路径中所有的边都必须同向(若存在双向路径，则为强连通)。如果图中任意两点都是连通的，那么图被称作连通图。
6、支配集
支配集也是图顶点集的一个子集，设S 是图G 的一个支配集，则对于图中的任意一个顶点u，要么属于集合s, 要么与s 中的顶点相邻。 在s中除去任何元素后s不再是支配集，则支配集s是极小支配集。称G的所有支配集中顶点个数最 少的支配集为最小支配集，最小支配集中的顶点个数成为支配数。
二、图的搜索
1、广度优先搜索(Breadth-first-search, BFS)
BFS始终将已发现的和未发现的顶点之间的边界沿其广度方向向外扩展。
BFS的时间分析：所有顶点入队一次，时间总共为O(V)。顶点出队之前需要扫描该顶点的邻接表。扫描所有邻接表的时间为O(E)。于是BFS的总运行时间为O(V + E)，也就是说BFS的运行时间是G的邻接表大小的线性函数。
void BFS( Graph g, vertex s)
{
Enqueue(Q, s)
s.status = discovered;
while (Q != )
{
s = Dequeue(Q);
for each vertex v belongs to the neighbos of s
{
if(v.status == undiscovered)
{
v.status = discovered;
Enqueue(Q, v);
}
}
}
}
2、深度优先搜索(Depth-first-search, DFS)
DFS中，对于新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都被探寻过后，搜索回到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点时为止。与BFS的一个区别是，BFS生成一个广度树，而DFS生成很多深度树。
DFS的时间分析：与BFS类似，对每个未搜索的顶点会调用一次递归算法，所以有O(V)。又会对每个点的邻近边扫描一次，时间为O(E)。于是DFS的总运行时间也为O(V + E)。
int order;
void DFS(Graph g)
{
for each vertex v belongs to g
{
If (v.status == undiscovered)
{
Order = 0;
DFS-Visit (v);
}
}
}
void DFS-Visit(Graph g, vertex s) // DFS has many trees
{
s.status = discovered;
for each vertex v belongs to the neighbos of s
{
if(v.status == undiscovered)
DFS-Visit(g, v);
}
s.status = discovered;
s.order = order;
order++;
}
三、最小生成树(Minimum Spanning Tree, MST)
对于无向连通图G = (V, E)，每条边(u, v)都有一个权值w(u, v)，我们希望找到一个无回路的子集T属于E，它连接所有的顶点，其权之和最小。这样的T必然是一颗树，称为最小生成树。要解决这个问题，有Kruskal和Prim两种算法。这两种算法都使用二叉堆，都容易达到O(E*lgV)的运行时间。
Kruskal和Prim算法
安全边(safe edge)：若A是一个最小生成树的子集，若有一条边(u, v)，使得将它加入集合A后，A仍然是一个最小生成树的子集，则这样的边是一个安全边。
轻边(light edge)：把无向图G = (V, E)割（划分）成两部分(S, V - S)，若A中没有一条边被割开，则说该割不妨害边集A。如果某条边的权值是通过这条割中最小的，则称该边为这条割的一条轻边。
可以证明，若割不妨害A，则把轻边加入A是安全的。
无论是Kruskal还是Prim算法，都是不断加入安全边的过程，所以它们都是一种贪心算法。
Kruskal算法中，集合A是一个森林(初始时每个顶点都是一颗树)，加入集合A的安全边总是连接两个不同连通分支的最小权边。伪代码如下：
MST-KRUSKAL(G, w)
A ← Ø
for each vertex v ∈ V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) ∈ E, taken in nondecreasing order by weight
do if FIND-SET(u) ≠ FIND-SET(v)
then A ← A ∪ {(u, v)}
UNION(u, v)
return APrim算法中，添加入A的安全边总是连接树与一个不在树中的顶点的最小权边。
MST-PRIM(G, w, r)
for each u ∈ V [G]
do key[u] ← ∞
π[u] ← NIL
key[r] ← 0
Q ← V [G]
while Q ≠ Ø
do u ← EXTRACT-MIN(Q)
for each v ∈ Adj[u]
do if v ∈ Q and w(u, v) < key[v]
then π[v] ← u
key[v] ← w(u, v)
通过使用斐波那契(Fibonacci)堆，Prim的算法可以进一步改善为O(E + V*lgV)。
四、最短路径
1、单源最短路径
考虑从芝加哥到波士顿的最短路径，我们有一张美国公路图，公路图上标明了每一对相邻的公路交叉点之间的距离，应该如何找出这一条最短路线呢？把这类问题总结出来，得到单源最短路径问题。
单源最短路径问题希望给出定源顶点s属于V到每个顶点v属于V的最短路径。一旦解决了单源最短路径，那么它的变体也解决了。比如，单终点路径问题，单对顶点最短路径问题，每对顶点间最短路径问题等。
解决单源最短路径的算法有Bellman-Ford算法，Dijkstra算法（贪心算法）以及Floyd-Warshall算法（动态规划算法）。
2、Bellman-Ford算法
Bellman-Ford算法能够处理权为负的情况。
松弛（relaxation）:对每个顶点v属于V，都设置一个属性d[v]，用来描述从起始点s到v的最短路径上权值的上界（d也称为“最短路径估计”）。若存在d[v] > d[u] + w(u, v)这种情况的出现，则令d[v] = d[u] + w(u, v)。也就是说，当d[v] <= d[u] + w(u, v)时，满足此约束没有“压力”，是松弛的。
得到Bellman-Ford的伪代码如下：
BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i ← 1 to |V[G]| - 1
do for each edge (u, v) ∈ E[G]
do RELAX(u, v, w)
for each edge (u, v) ∈ E[G]
do if d[v] > d[u] + w(u, v)
then return FALSE
return TRUE3、Dijkstra算法
Dijkstra算法设置了一个顶点集合S，从原点s到集合中顶点的最终最短路径的权值均已确定。S初始为空集。反复选取V – S中的有最短路径估计的顶点u加入到S中，并对u的所有出边进行松弛。
DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S ← Ø
Q ← V[G]
while Q ≠ Ø
do u ← EXTRACT-MIN(Q)
S ← S ∪{u}
for each vertex v ∈ Adj[u]
do RELAX(u, v, w)