对于图论算法,NOIP初赛不要求会实现算法,但手工操作还是要会的,复赛是要求会代码实现的。

什么是图

一个图是一个序偶 <V, E>,记为 G =<V, E> 。

V 为顶点集, E 为 V 中结点之间的边的集合。

自环:一条边的两个端点是相同的。

重边:两个端点之间有两条以上的边,称他们是重边。

简单图:没有自环和重边的图。

无向边:边是双向的。

有向边:单向边,有箭头。

无向图:只有无向边的图。

有向图:只有有向边的图。

混合图:既有无向边又有有向边。

顶点的度:无向图中,一个顶点相连的边数称为该顶点的度;有向图中,从一个顶点出发的边数称为该顶点得出度;到达该顶点的边数称为它的入度。

NOIP初赛复习(十一)图论算法基础-少儿编程网

图论基本定理:著名的握手定理。无向图中结点度数的总和等于边数的两倍。有向图中结点入度的和等于出度的和等于边数。

通路:给定图G中结点和边交替出现的一个序列:v0 e1 v1 e2 v2 … ek vk,若每条边ei的两端点是vi-1 和vi ,那么称该序列是从v0到vk的一条通路。

基本通路(路径):没有重复出现的结点的通路。

图的连通性:若一张无向图的任意两个结点之间都存在通路,那么称该图是连通的。

连通分量:图中连通的顶点与边的集合。

权和网:在图的边给出相关的数,成为权。权可以表示一个顶点到另一个顶点的距离,耗费等。带权图一般成为网。

NOIP初赛复习(十一)图论算法基础-少儿编程网

最短路径:对于一张不带权的无向图来说,从s到t的最短路径就是所有从s到t的通路中长度最短的那一条(可能不唯一),通路上的边数称为路径的长度。

完全图:任何两个顶点之间都有边(弧)相连称为完全图。

稀疏图、稠密图:边(弧)很少的图称为稀疏图,反之为稠密图。


图的存储:邻接矩阵

在邻接矩阵表示中,除了存放顶点本身信息外,还用一个矩阵表示各个顶点之间的关系。若(i,j)∈E(G)或〈i,j〉∈E(G),则矩阵中第i行 第j列元素值为1,否则为0 。

例如, 下面为两个无向图和有向图对应的邻接矩阵。

NOIP初赛复习(十一)图论算法基础-少儿编程网
NOIP初赛复习(十一)图论算法基础-少儿编程网

空间复杂度:O(V^2)

优点:直观,容易理解,可以直接查看任意两点的关系。

缺点:对于稀疏图,会有很多空间根本没有利用。对于带权图,不能处理重边。要查询某一个顶点的所有边,要枚举V次。

图的存储:邻接表

对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。

NOIP初赛复习(十一)图论算法基础-少儿编程网

空间复杂度:有向图O(V+E)无向图O(V+2*E)

优点:节省空间,能快速找到某个顶点所有相连的顶点,而无需访问无关顶点。


图的遍历

为什么要遍历?很多图上的信息只通过点与边的集合是很难获得的,通过对图的遍历我们可以获取图上的信息。

图的遍历算法:宽度优先遍历(BFS)

给定图G和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离。

宽度优先的过程对结点着色。

白色: 没有考虑过的点。

黑色: 已经完全考虑过的点。

灰色: 发现过, 但没有处理过, 是遍历边界。

依次处理每个灰色结点u, 对于邻接边(u, v), 把v着成灰色并加入树中, 在树中u是v的父亲(parent)或称前驱(predecessor)。距离d[v] = d[u] + 1。整棵树的根为s。

NOIP初赛复习(十一)图论算法基础-少儿编程网

图的遍历算法:深度优先遍历(DFS)

新发现的结点先扩展。

得到的可能不是一棵树而是森林, 即深度优先森林(Depth-firstforest)。

特别之处: 引入时间戳(timestamp)。

发现时间d[v]: 变灰的时间。

结束时间f[v]: 变黑的时间。

1<=d[v] < f[v] <= 2|V|

拓扑排序算法

检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。如果有向图G有一个拓扑排序,则G是一个有向无环图。反之, 任一有向无环图必可进行拓扑排序。

按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。

算法描述:给出一个n个点的有向连通图,首先统计好每个点的前驱个数,每次一个前驱个数为0的点p,并且所有前驱为p的点的前驱个数减一。

例:POJ2367


生成树

树:N个点,N-1条边的连通图(无环连通图)。

生成树: 包含某图G所有点的树。

一个图G是树,当且仅当以下任意一个条件成立:

1、G有V-1条边, 无圈

2、G有V-1条边, 连通

3、任意两点只有唯一的简单路径

4、G连通, 但任意删除一条边后不连通

最小生成树

求带权无向图的一棵子树,包含N个点,N-1条边,边权之和最小。

求最小生成树的算法:Kruskal算法:O(MlogN);Prim算法:O(N^2)。

求最小生成树算法:Kruskal算法

算法描述:一个n个点的图,选若干条边(一定是n-1条)使得图连在一起,并且所有选中的边的长度和最小。

利用并查集,起初每个点各自构成一个集合。

所有边按照边权从小到大排序,依次扫描。

若当前扫描到的边连接两个不同的点集,合并。

本质也是贪心,算法复杂度:O(MlogN)。

与Prim算法相比,没有基准点,该算法是不断选择两个距离最近的集合进行合并的过程。

例:POJ1251、2075、2485、2421、1789、2349……

求最小生成树算法:Prim算法

算法描述:给出一个n个点的连通图,首先选中一个点(一般为第一个点),每次选和已选中的所有点相连的边中最小一条(该边两个端点必须一个是已选中点,另外一个为还没选的点)。

以任意一个点为基准点。

节点分为两组:

1. 在最小生成树上到基准点的路径已经确定的点。

2. 尚未在最小生成树中与基准点相连的点。

不断从第2组中选择与第1组距离最近的点加入第1组。

类似于Dijkstra,本质也是贪心,算法复杂度:O(N^2)

例:POJ1258


单源最短路径问题

给定带权图和一个起点s, 求s到所有点的最短路(边权和最小的路径)。

最短路有环吗?

正环: 何必呢, 删除环则得到更短路。

负环: 无最短路, 因为可以沿负环兜圈子。

求单源最短路径的算法:Dijkstra算法——堆优化的Dijkstra算法;Bellman-Ford算法——SPFA(Shortest Path Fast Algorithm)算法,SLF优化的SPFA算法。

求单源最短路径算法:Dijkstra算法

算法描述:类似Prim算法,给出一个n个点的连通图,假设出发点为st,那么d[st]=0,d[i]表示点i到出发点的距离(i表示除了出发点外的任意点)。每次选d[ ]值最小的点p,然后点p去更新其他还没有被选中的点i的d[ ]值。

节点分成两组:已经确定最短路、尚未确定最短路。

不断从第2组中选择路径长度最短的点放入第1组并扩展。

本质是贪心,只能应用于正权图。

普通的Dijkstra算法复杂度:O(N^2)。

堆优化的Dijkstra算法复杂度:O(NlogN)~O(MlogN)。

例:POJ1847

求单源最短路径算法:SPFA算法

Bellman-Ford算法:对每条边执行更新,迭代N-1次。

SPFA = 队列优化的Bellman-Ford算法。

本质上还是迭代——每更新一次就考虑入队。

稀疏图上的算法复杂度:O(kN),稠密图上退化到O(N^2)。

SLF优化:Small Label First, 新入队点与队头比较。

LLL优化:Large Label Last, 队头与平均值比较。

可以应用于负权图。

例:POJ2449、POJ3635


历年真题

填空题1.有6个城市,任何两个城市之间有一条道路连接,6个城市之间两两之间的距离如下表表示,则城市1到城市6的最短距离为____________。

NOIP初赛复习(十一)图论算法基础-少儿编程网

答案:7