NOIP初赛复习21图论算法基础
对于图论算法，NOIP初赛不要求会实现算法，但手工操作还是要会的，复赛是要求会代码实现的。
什么是图
一个图是一个序偶
,记为 G = 。
V 为顶点集, E 为 V 中结点之间的边的集合。
自环：一条边的两个端点是相同的。
重边：两个端点之间有两条以上的边，称他们是重边。
简单图：没有自环和重边的图。
无向边：边是双向的。
有向边：单向边，有箭头。
无向图：只有无向边的图。
有向图：只有有向边的图。
混合图：既有无向边又有有向边。
顶点的度：无向图中，一个顶点相连的边数称为该顶点的度；有向图中，从一个顶点出发的边数称为该顶点得出度；到达该顶点的边数称为它的入度。
图论基本定理：著名的握手定理。无向图中结点度数的总和等于边数的两倍。有向图中结点入度的和等于出度的和等于边数。
通路：给定图G中结点和边交替出现的一个序列：v0 e1 v1 e2 v2 … ek vk，若每条边ei的两端点是vi-1 和vi ，那么称该序列是从v0到vk的一条通路。
基本通路(路径)：没有重复出现的结点的通路。
图的连通性：若一张无向图的任意两个结点之间都存在通路，那么称该图是连通的。
连通分量：图中连通的顶点与边的集合。
权和网：在图的边给出相关的数，成为权。权可以表示一个顶点到另一个顶点的距离，耗费等。带权图一般成为网。
最短路径：对于一张不带权的无向图来说，从s到t的最短路径就是所有从s到t的通路中长度最短的那一条(可能不唯一)，通路上的边数称为路径的长度。
完全图：任何两个顶点之间都有边（弧）相连称为完全图。
稀疏图、稠密图：边（弧）很少的图称为稀疏图，反之为稠密图。
图的存储：邻接矩阵
在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）∈E(G)或〈i,j〉∈E(G),则矩阵中第i行 第j列元素值为1，否则为0 。
例如, 下面为两个无向图和有向图对应的邻接矩阵。
空间复杂度：O(V^2)
优点：直观，容易理解，可以直接查看任意两点的关系。
缺点：对于稀疏图，会有很多空间根本没有利用。对于带权图，不能处理重边。要查询某一个顶点的所有边，要枚举V次。
图的存储：邻接表
对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。
空间复杂度：有向图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。
图的遍历算法：深度优先遍历(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
单源最短路径问MATCH_
word
word文档格式规范word作业纸小票打印word模板word简历模板免费word简历
_1714062534598_0
给定带权图和一个起点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
历年
真题
北京中考数学真题pdf四级真题及答案下载历年四级真题下载证券交易真题下载资料分析真题下载
填空题1．有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为____________。
城市1
城市2
城市3
城市4
城市5
城市6
城市1
0
2
3
1
12
15
城市2
2
0
2
5
3
12
城市3
3
2
0
3
6
5
城市4
1
5
3
0
7
9
城市5
12
3
6
7
0
2
城市6
15
12
5
9
2
0
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
：7
浙公网安备 33021202002483