做推文加入视频的网站,南通水情最新信息,涟水住房和城乡建设局网站,什么网站ppt做的好代码随想录算法训练营第70天:图论9
拓扑排序精讲
卡码网#xff1a;117. 软件构建(opens new window)
题目描述#xff1a;
某个大型软件项目的构建系统拥有 N 个文件#xff0c;文件编号从 0 到 N - 1#xff0c;在这些文件中#xff0c;某些文件依赖于其他文件的…代码随想录算法训练营第70天:图论9
拓扑排序精讲
卡码网117. 软件构建(opens new window)
题目描述
某个大型软件项目的构建系统拥有 N 个文件文件编号从 0 到 N - 1在这些文件中某些文件依赖于其他文件的内容这意味着如果文件 A 依赖于文件 B则必须在处理文件 A 之前处理文件 B 0 A, B N - 1。请编写一个算法用于确定文件处理的顺序。
输入描述
第一行输入两个正整数 M, N。表示 N 个文件之间拥有 M 条依赖关系。
后续 M 行每行两个正整数 S 和 T表示 T 文件依赖于 S 文件。
输出描述
输出共一行如果能处理成功则输出文件顺序用空格隔开。
如果不能成功处理相互依赖则输出 -1。
输入示例
5 4
0 1
0 2
1 3
2 4输出示例
0 1 2 3 4
提示信息
文件依赖关系如下
所以文件处理的顺序除了示例中的顺序还存在
0 2 4 1 3
0 2 1 3 4
等等合法的顺序。
数据范围
0 N 10 ^ 51 M 10 ^ 9
#拓扑排序的背景
本题是拓扑排序的经典题目。
一聊到 拓扑排序一些录友可能会想这是排序不会想到这是图论算法。
其实拓扑排序是经典的图论问题。
先说说 拓扑排序的应用场景。
大学排课例如 先上A课才能上B课上了B课才能上C课上了A课才能上D课等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。
拓扑排序在文件处理上也有应用我们在做项目安装文件包的时候经常发现 复杂的文件依赖关系 A依赖BB依赖CB依赖DC依赖E 等等。
如果给出一条线性的依赖顺序来下载这些文件呢
有录友想上面的例子都很简单啊我一眼能给排序出来。
那如果上面的依赖关系是一百对呢一千对甚至上万个依赖关系这些依赖关系中可能还有循环依赖你如何发现循环依赖呢又如果排出线性顺序呢。
所以 拓扑排序就是专门解决这类问题的。
概括来说给出一个 有向图把这个有向图转成线性的排序 就叫拓扑排序。
当然拓扑排序也要检测这个有向图 是否有环即存在循环依赖的情况因为这种情况是不能做线性排序的。
所以拓扑排序也是图论中判断有向无环图的常用方法。 #拓扑排序的思路
拓扑排序指的是一种 解决问题的大体思路 而具体算法可能是广搜也可能是深搜。
大家可能发现 各式各样的解法纠结哪个是拓扑排序
其实只要能在把 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序。
实现拓扑排序的算法有两种卡恩算法BFS和DFS 卡恩1962年提出这种解决拓扑排序的思路 一般来说我们只需要掌握 BFS 广度优先搜索就可以了清晰易懂如果还想多了解一些可以再去学一下 DFS 的思路但 DFS 不是本篇重点。
接下来我们来讲解BFS的实现思路。
以题目中示例为例如图
做拓扑排序的话如果肉眼去找开头的节点一定能找到 节点0 吧都知道要从节点0 开始。
但为什么我们能找到 节点0呢因为我们肉眼看着 这个图就是从 节点0出发的。
作为出发节点它有什么特征
你看节点0 的入度 为0 出度为2 也就是 没有边指向它而它有两条边是指出去的。 节点的入度表示 有多少条边指向它节点的出度表示有多少条边 从该节点出发。 所以当我们做拓扑排序的时候应该优先找 入度为 0 的节点只有入度为0它才是出发节点。 理解以上内容很重要
接下来我给出 拓扑排序的过程其实就两步
找到入度为0 的节点加入结果集将该节点从图中移除
循环以上两步直到 所有节点都在图中被移除了。
结果集的顺序就是我们想要的拓扑排序顺序 结果集里顺序可能不唯一
#模拟过程
用本题的示例来模拟这一过程
1、找到入度为0 的节点加入结果集
2、将该节点从图中移除
1、找到入度为0 的节点加入结果集
这里大家会发现节点1 和 节点2 入度都为0 选哪个呢
选哪个都行所以这也是为什么拓扑排序的结果是不唯一的。
2、将该节点从图中移除
1、找到入度为0 的节点加入结果集
节点2 和 节点3 入度都为0选哪个都行这里选节点2
2、将该节点从图中移除
后面的过程一样的节点3 和 节点4入度都为0选哪个都行。
最后结果集为 0 1 2 3 4 。当然结果不唯一的。
#判断有环
如果有 有向环怎么办呢例如这个图
这个图我们只能将入度为0 的节点0 接入结果集。
之后节点1、2、3、4 形成了环找不到入度为0 的节点了所以此时结果集里只有一个元素。
那么如果我们发现结果集元素个数 不等于 图中节点个数我们就可以认定图中一定有 有向环
这也是拓扑排序判断有向环的方法。
通过以上过程的模拟大家会发现这个拓扑排序好像不难还有点简单。
#写代码
理解思想后确实不难但代码写起来也不容易。
为了每次可以找到所有节点的入度信息我们要在初始话的时候就把每个节点的入度 和 每个节点的依赖关系做统计。
代码如下
cin n m;
vectorint inDegree(n, 0); // 记录每个文件的入度
vectorint result; // 记录结果
unordered_mapint, vectorint umap; // 记录文件依赖关系while (m--) {
// s-t先有s才能有t
cin s t;
inDegree[t]; // t的入度加一
umap[s].push_back(t); // 记录s指向哪些文件
}
找入度为0 的节点我们需要用一个队列放存放。
因为每次寻找入度为0的节点不一定只有一个节点可能很多节点入度都为0所以要将这些入度为0的节点放到队列里依次去处理。
代码如下 queueint que;
for (int i 0; i n; i) {
// 入度为0的节点可以作为开头先加入队列
if (inDegree[i] 0) que.push(i);
}开始从队列里遍历入度为0 的节点将其放入结果集。 while (que.size()) {
int cur que.front(); // 当前选中的节点
que.pop();
result.push_back(cur);
// 将该节点从图中移除 }这里面还有一个很重要的过程如何把这个入度为0的节点从图中移除呢
首先我们为什么要把节点从图中移除
为的是将 该节点作为出发点所连接的边删掉。
删掉的目的是什么呢
要把 该节点作为出发点所连接的节点的 入度 减一。
如果这里不理解看上面的模拟过程第一步
这事节点1 和 节点2 的入度为 1。
将节点0删除后图为这样
那么 节点0 作为出发点 所连接的节点的入度 就都做了 减一 的操作。
此时 节点1 和 节点 2 的入度都为0 这样才能作为下一轮选取的节点。
所以我们在代码实现的过程中本质是要将 该节点作为出发点所连接的节点的 入度 减一 就可以了这样好能根据入度找下一个节点不用真在图里把这个节点删掉。
该过程代码如下 while (que.size()) {
int cur que.front(); // 当前选中的节点
que.pop();
result.push_back(cur);
// 将该节点从图中移除
vectorint files umap[cur]; //获取cur指向的节点
if (files.size()) { // 如果cur有指向的节点
for (int i 0; i files.size(); i) { // 遍历cur指向的节点
inDegree[files[i]] --; // cur指向的节点入度都做减一操作
// 如果指向的节点减一之后入度为0说明是我们要选取的下一个节点放入队列。
if(inDegree[files[i]] 0) que.push(files[i]);
}
}}最后代码如下
#include iostream
#include vector
#include queue
#include unordered_map
using namespace std;
int main() {
int m, n, s, t;
cin n m;
vectorint inDegree(n, 0); // 记录每个文件的入度unordered_mapint, vectorint umap;// 记录文件依赖关系
vectorint result; // 记录结果while (m--) {
// s-t先有s才能有t
cin s t;
inDegree[t]; // t的入度加一
umap[s].push_back(t); // 记录s指向哪些文件
}
queueint que;
for (int i 0; i n; i) {
// 入度为0的文件可以作为开头先加入队列
if (inDegree[i] 0) que.push(i);
//cout inDegree[i] endl;
}
// int count 0;
while (que.size()) {
int cur que.front(); // 当前选中的文件
que.pop();
//count;
result.push_back(cur);
vectorint files umap[cur]; //获取该文件指向的文件
if (files.size()) { // cur有后续文件
for (int i 0; i files.size(); i) {
inDegree[files[i]] --; // cur的指向的文件入度-1
if(inDegree[files[i]] 0) que.push(files[i]);
}
}
}
if (result.size() n) {
for (int i 0; i n - 1; i) cout result[i] ;
cout result[n - 1];
} else cout -1 endl;}dijkstra朴素版精讲
卡码网47. 参加科学大会(opens new window)
【题目描述】
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。
小明的起点是第一个车站终点是最后一个车站。然而途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素如天气变化等不同这些因素都会影响每条路径的通行时间。
小明希望能选择一条花费时间最少的路线以确保他能够尽快到达目的地。
【输入描述】
第一行包含两个正整数第一个正整数 N 表示一共有 N 个公共汽车站第二个正整数 M 表示有 M 条公路。
接下来为 M 行每行包括三个整数S、E 和 V代表了从 S 车站可以单向直达 E 车站并且需要花费 V 单位的时间。
【输出描述】
输出一个整数代表小明从起点到终点所花费的最小时间。
输入示例
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9输出示例12
【提示信息】
能够到达的情况
如下图所示起始车站为 1 号车站终点车站为 7 号车站绿色路线为最短的路线路线总长度为 12则输出 12。
不能到达的情况
如下图所示当从起始车站不能到达终点车站时则输出 -1。
数据范围
1 N 500; 1 M 5000;
#思路
本题就是求最短路最短路是图论中的经典问题即给出一个有向图一个起点一个终点问起点到终点的最短路径。
接下来我们来详细讲解最短路算法中的 dijkstra 算法。
dijkstra算法在有权图权值非负数中求从起点到其他节点的最短路径算法。
需要注意两点
dijkstra 算法可以同时求 起点到所有节点的最短路径权值不能为负数
这两点后面我们会讲到
如本题示例中的图
起点节点1到终点节点7 的最短路径是 图中 标记绿线的部分。
最短路径的权值为12。
其实 dijkstra 算法 和 我们之前讲解的prim算法思路非常接近如果大家认真学过prim算法那么理解 Dijkstra 算法会相对容易很多。这也是我要先讲prim再讲dijkstra的原因
dijkstra 算法 同样是贪心的思路不断寻找距离 源点最近的没有访问过的节点。
这里我也给出 dijkstra三部曲
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
大家此时已经会发现这和prim算法 怎么这么像呢。
我在prim算法讲解中也给出了三部曲。 prim 和 dijkstra 确实很像思路也是类似的这一点我在后面还会详细来讲。
在dijkstra算法中同样有一个数组很重要起名为minDist。
minDist数组 用来记录 每一个节点距离源点的最小距离。
理解这一点很重要也是理解 dijkstra 算法的核心所在。
大家现在看着可能有点懵不知道什么意思。
没关系先让大家有一个印象对理解后面讲解有帮助。
我们先来画图看一下 dijkstra 的工作过程以本题示例为例 以下为朴素版dijkstra的思路
示例中节点编号是从1开始所以为了让大家看的不晕minDist数组下标我也从 1 开始计数下标0 就不使用了这样 下标和节点标号就可以对应上了避免大家搞混
#朴素版dijkstra
#模拟过程 0、初始化
minDist数组数值初始化为int最大值。
这里在强点一下 minDist数组的含义记录所有节点到源点的最短路径那么初始化的时候就应该初始为最大值这样才能在后续出现最短路径的时候及时更新。
图中max 表示默认值节点0 不做处理统一从下标1 开始计算这样下标和节点数值统一 方便大家理解避免搞混
源点节点1 到自己的距离为0所以 minDist[1] 0
此时所有节点都没有被访问过所以 visited数组都为0 以下为dijkstra 三部曲
1、选源点到哪个节点近且该节点未被访问过
源点距离源点最近距离为0且未被访问。
2、该最近节点被标记访问过
标记源点访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
更新 minDist数组即源点节点1 到 节点2 和 节点3的距离。
源点到节点2的最短距离为1小于原minDist[2]的数值max更新minDist[2] 1源点到节点3的最短距离为4小于原minDist[3]的数值max更新minDist[4] 4
可能有录友问为啥和 minDist[2] 比较
再强调一下 minDist[2] 的含义它表示源点到节点2的最短距离那么目前我们得到了 源点到节点2的最短距离为1小于默认值max所以更新。 minDist[3]的更新同理 1、选源点到哪个节点近且该节点未被访问过
未访问过的节点中源点到节点2距离最近选节点2
2、该最近节点被标记访问过
节点2被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
更新 minDist数组即源点节点1 到 节点6 、 节点3 和 节点4的距离。
为什么更新这些节点呢 怎么不更新其他节点呢
因为 源点节点1通过 已经计算过的节点节点2 可以链接到的节点 有 节点3节点4和节点6.
更新 minDist数组
源点到节点6的最短距离为5小于原minDist[6]的数值max更新minDist[6] 5源点到节点3的最短距离为3小于原minDist[3]的数值4更新minDist[3] 3源点到节点4的最短距离为6小于原minDist[4]的数值max更新minDist[4] 6 1、选源点到哪个节点近且该节点未被访问过
未访问过的节点中源点距离哪些节点最近怎么算的
其实就是看 minDist数组里的数值minDist 记录了 源点到所有节点的最近距离结合visited数组筛选出未访问的节点就好。
从 上面的图或者 从minDist数组中我们都能看出 未访问过的节点中源点节点1到节点3距离最近。
2、该最近节点被标记访问过
节点3被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
由于节点3的加入那么源点可以有新的路径链接到节点4 所以更新minDist数组
更新 minDist数组
源点到节点4的最短距离为5小于原minDist[4]的数值6更新minDist[4] 5 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点有节点4 和 节点6距离源点距离都是 5 minDist[4] 5minDist[6] 5 选哪个节点都可以。
2、该最近节点被标记访问过
节点4被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
由于节点4的加入那么源点可以链接到节点5 所以更新minDist数组
源点到节点5的最短距离为8小于原minDist[5]的数值max更新minDist[5] 8 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点是节点6距离源点距离是 5 minDist[6] 5
2、该最近节点被标记访问过
节点6 被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
由于节点6的加入那么源点可以链接到节点7 所以 更新minDist数组
源点到节点7的最短距离为14小于原minDist[7]的数值max更新minDist[7] 14 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点是节点5距离源点距离是 8 minDist[5] 8
2、该最近节点被标记访问过
节点5 被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
由于节点5的加入那么源点有新的路径可以链接到节点7 所以 更新minDist数组
源点到节点7的最短距离为12小于原minDist[7]的数值14更新minDist[7] 12 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点是节点7终点距离源点距离是 12 minDist[7] 12
2、该最近节点被标记访问过
节点7 被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
节点7加入但节点7到节点7的距离为0所以 不用更新minDist数组 最后我们要求起点节点1 到终点 节点7的距离。
再来回顾一下minDist数组的含义记录 每一个节点距离源点的最小距离。
那么起到节点1到终点节点7的最短距离就是 minDist[7] 按上面举例讲解来说minDist[7] 12节点1 到节点7的最短路径为 12。
路径如图
在上面的讲解中每一步 我都是按照 dijkstra 三部曲来讲解的理解了这三部曲代码也就好懂的。
#代码实现
本题代码如下里面的 三部曲 我都做了注释大家按照我上面的讲解 来看如下代码
#include iostream
#include vector
#include climits
using namespace std;
int main() {
int n, m, p1, p2, val;
cin n m;vectorvectorint grid(n 1, vectorint(n 1, INT_MAX));
for(int i 0; i m; i){
cin p1 p2 val;
grid[p1][p2] val;
}int start 1;
int end n;// 存储从源点到每个节点的最短距离
std::vectorint minDist(n 1, INT_MAX);// 记录顶点是否被访问过
std::vectorbool visited(n 1, false);minDist[start] 0; // 起始点到自身的距离为0for (int i 1; i n; i) { // 遍历所有节点int minVal INT_MAX;
int cur 1;// 1、选距离源点最近且未访问过的节点
for (int v 1; v n; v) {
if (!visited[v] minDist[v] minVal) {
minVal minDist[v];
cur v;
}
}visited[cur] true; // 2、标记该节点已被访问// 3、第三步更新非访问节点到源点的距离即更新minDist数组
for (int v 1; v n; v) {
if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {
minDist[v] minDist[cur] grid[cur][v];
}
}}if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点
else cout minDist[end] endl; // 到达终点最短路径}时间复杂度O(n^2)空间复杂度O(n^2)
#debug方法
写这种题目难免会有各种各样的问题我们如何发现自己的代码是否有问题呢
最好的方式就是打日志本题的话就是将 minDist 数组打印出来就可以很明显发现 哪里出问题了。
每次选择节点后minDist数组的变化是否符合预期 是否和我上面讲的逻辑是对应的。
例如本题如果想debug的话打印日志可以这样写
#include iostream
#include vector
#include climits
using namespace std;
int main() {
int n, m, p1, p2, val;
cin n m;vectorvectorint grid(n 1, vectorint(n 1, INT_MAX));
for(int i 0; i m; i){
cin p1 p2 val;
grid[p1][p2] val;
}int start 1;
int end n;std::vectorint minDist(n 1, INT_MAX);std::vectorbool visited(n 1, false);minDist[start] 0;
for (int i 1; i n; i) {int minVal INT_MAX;
int cur 1;for (int v 1; v n; v) {
if (!visited[v] minDist[v] minVal) {
minVal minDist[v];
cur v;
}
}visited[cur] true;for (int v 1; v n; v) {
if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {
minDist[v] minDist[cur] grid[cur][v];
}
}// 打印日志
cout select: cur endl;
for (int v 1; v n; v) cout v : minDist[v] ;
cout endl endl;;}
if (minDist[end] INT_MAX) cout -1 endl;
else cout minDist[end] endl;}
打印后的结果
select:1
1:0 2:1 3:4 4:2147483647 5:2147483647 6:2147483647 7:2147483647select:2
1:0 2:1 3:3 4:6 5:2147483647 6:5 7:2147483647select:3
1:0 2:1 3:3 4:5 5:2147483647 6:5 7:2147483647select:4
1:0 2:1 3:3 4:5 5:8 6:5 7:2147483647select:6
1:0 2:1 3:3 4:5 5:8 6:5 7:14select:5
1:0 2:1 3:3 4:5 5:8 6:5 7:12select:7
1:0 2:1 3:3 4:5 5:8 6:5 7:12打印日志可以和上面我讲解的过程进行对比每一步的结果是完全对应的。
所以如果大家如果代码有问题打日志来debug是最好的方法
#如何求路径
如果题目要求把最短路的路径打印出来应该怎么办呢
这里还是有一些“坑”的本题打印路径和 prim 打印路径是一样的我在 prim算法精讲 【拓展】中 已经详细讲解了。
在这里就不再赘述。
打印路径只需要添加 几行代码 打印路径的代码我都加上的日志如下
#include iostream
#include vector
#include climits
using namespace std;
int main() {
int n, m, p1, p2, val;
cin n m;vectorvectorint grid(n 1, vectorint(n 1, INT_MAX));
for(int i 0; i m; i){
cin p1 p2 val;
grid[p1][p2] val;
}int start 1;
int end n;std::vectorint minDist(n 1, INT_MAX);std::vectorbool visited(n 1, false);minDist[start] 0; //加上初始化
vectorint parent(n 1, -1);for (int i 1; i n; i) {int minVal INT_MAX;
int cur 1;for (int v 1; v n; v) {
if (!visited[v] minDist[v] minVal) {
minVal minDist[v];
cur v;
}
}visited[cur] true;for (int v 1; v n; v) {
if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {
minDist[v] minDist[cur] grid[cur][v];
parent[v] cur; // 记录边
}
}}// 输出最短情况
for (int i 1; i n; i) {
cout parent[i] - i endl;
}
}打印结果
-1-1
1-2
2-3
3-4
4-5
2-6
5-7对应如图
#出现负数
如果图中边的权值为负数dijkstra 还合适吗
看一下这个图 有负权值
节点1 到 节点5 的最短路径 应该是 节点1 - 节点2 - 节点3 - 节点4 - 节点5
那我们来看dijkstra 求解的路径是什么样的继续dijkstra 三部曲来模拟 dijkstra模拟过程上面已经详细讲过以下只模拟重要过程例如如何初始化就省略讲解了 初始化
1、选源点到哪个节点近且该节点未被访问过
源点距离源点最近距离为0且未被访问。
2、该最近节点被标记访问过
标记源点访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
更新 minDist数组即源点节点1 到 节点2 和 节点3的距离。
源点到节点2的最短距离为100小于原minDist[2]的数值max更新minDist[2] 100源点到节点3的最短距离为1小于原minDist[3]的数值max更新minDist[4] 1 1、选源点到哪个节点近且该节点未被访问过
源点距离节点3最近距离为1且未被访问。
2、该最近节点被标记访问过
标记节点3访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
由于节点3的加入那么源点可以有新的路径链接到节点4 所以更新minDist数组
源点到节点4的最短距离为2小于原minDist[4]的数值max更新minDist[4] 2 1、选源点到哪个节点近且该节点未被访问过
源点距离节点4最近距离为2且未被访问。
2、该最近节点被标记访问过
标记节点4访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
由于节点4的加入那么源点可以有新的路径链接到节点5 所以更新minDist数组
源点到节点5的最短距离为3小于原minDist[5]的数值max更新minDist[5] 5 1、选源点到哪个节点近且该节点未被访问过
源点距离节点5最近距离为3且未被访问。
2、该最近节点被标记访问过
标记节点5访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
节点5的加入而节点5 没有链接其他节点 所以不用更新minDist数组仅标记节点5被访问过了 1、选源点到哪个节点近且该节点未被访问过
源点距离节点2最近距离为100且未被访问。
2、该最近节点被标记访问过
标记节点2访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图
至此dijkstra的模拟过程就结束了根据最后的minDist数组我们求 节点1 到 节点5 的最短路径的权值总和为 3路径 节点1 - 节点3 - 节点4 - 节点5
通过以上的过程模拟我们可以发现 之所以 没有走有负权值的最短路径 是因为 在 访问 节点 2 的时候节点 3 已经访问过了就不会再更新了。
那有录友可能会想 我可以改代码逻辑啊访问过的节点也让它继续访问不就好了
那么访问过的节点还能继续访问会不会有死循环的出现呢控制逻辑不让其死循环那特殊情况自己能都想清楚吗可以试试实践出真知
对于负权值的出现大家可以针对某一个场景 不断去修改 dijkstra 的代码但最终会发现只是 拆了东墙补西墙对dijkstra的补充逻辑只能满足某特定场景最短路求解。
对于求解带有负权值的最短路问题可以使用 Bellman-Ford 算法 我在后序会详细讲解。
#dijkstra与prim算法的区别 这里再次提示需要先看我的 prim算法精讲 否则可能不知道我下面讲的是什么。 大家可以发现 dijkstra的代码看上去 怎么和 prim算法这么像呢。
其实代码大体不差唯一区别在 三部曲中的 第三步 更新minDist数组
因为prim是求 非访问节点到最小生成树的最小距离而 dijkstra是求 非访问节点到源点的最小距离。
prim 更新 minDist数组的写法
for (int j 1; j v; j) {
if (!isInTree[j] grid[cur][j] minDist[j]) {
minDist[j] grid[cur][j];
}
}因为 minDist表示 节点到最小生成树的最小距离所以 新节点cur的加入只需要 使用 grid[cur][j] grid[cur][j] 就表示 cur 加入生成树后生成树到 节点j 的距离。
dijkstra 更新 minDist数组的写法
for (int v 1; v n; v) {
if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {
minDist[v] minDist[cur] grid[cur][v];
}
}因为 minDist表示 节点到源点的最小距离所以 新节点 cur 的加入需要使用 源点到cur的距离 minDist[cur] cur 到 节点 v 的距离 grid[cur][v]才是 源点到节点v的距离。
此时大家可能不禁要想 prim算法 可以有负权值吗
当然可以
录友们可以自己思考思考一下这是为什么
这里我提示一下prim算法只需要将节点以最小权值和链接在一起不涉及到单一路径。
#总结
本篇我们深入讲解的dijkstra算法详细模拟其工作的流程。
这里我给出了 dijkstra 三部曲 来 帮助大家理解 该算法不至于 每次写 dijkstra 都是黑盒操作没有框架没有章法。
在给出的代码中我也按照三部曲的逻辑来给大家注释只要理解这三部曲即使 过段时间 对 dijkstra 算法有些遗忘依然可以写出一个框架出来然后再去调试细节。
对于图论算法一般代码都比较长很难写出代码直接可以提交通过都需要一个debug的过程所以 学习如何debug 非常重要
这也是我为什么 在本文中 单独用来讲解 debug方法。
本题求的是最短路径和是多少同时我们也要掌握 如何把最短路径打印出来。
我还写了大篇幅来讲解 负权值的情况 只有画图带大家一步一步去 看 出现负权值 dijkstra的求解过程才能帮助大家理解问题出在哪里。
如果我直接讲是因为访问过的节点 不能再访问导致错过真正的最短路我相信大家都不知道我在说啥。
最后我还讲解了 dijkstra 和 prim 算法的 相同 与 不同之处 我在图论的讲解安排中 先讲 prim算法 再讲 dijkstra 是有目的的 理解这两个算法的相同与不同之处 有助于大家学习的更深入。
而不是 学了 dijkstra 就只看 dijkstra 算法之间 都是有联系的多去思考 算法之间的相互联系会帮助大家思考的更深入掌握的更彻底。
本篇写了这么长我也只讲解了 朴素版dijkstra关于 堆优化dijkstra我会在下一篇再来给大家详细讲解。
加油
dijkstra堆优化版精讲
卡码网47. 参加科学大会(opens new window)
【题目描述】
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。
小明的起点是第一个车站终点是最后一个车站。然而途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素如天气变化等不同这些因素都会影响每条路径的通行时间。
小明希望能选择一条花费时间最少的路线以确保他能够尽快到达目的地。
【输入描述】
第一行包含两个正整数第一个正整数 N 表示一共有 N 个公共汽车站第二个正整数 M 表示有 M 条公路。
接下来为 M 行每行包括三个整数S、E 和 V代表了从 S 车站可以单向直达 E 车站并且需要花费 V 单位的时间。
【输出描述】
输出一个整数代表小明从起点到终点所花费的最小时间。
输入示例
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9输出示例12
【提示信息】
能够到达的情况
如下图所示起始车站为 1 号车站终点车站为 7 号车站绿色路线为最短的路线路线总长度为 12则输出 12。
不能到达的情况
如下图所示当从起始车站不能到达终点车站时则输出 -1。
数据范围
1 N 500; 1 M 5000;
#思路 本篇我们来讲解 堆优化版dijkstra看本篇之前一定要先看 我讲解的 朴素版dijkstra否则本篇会有部分内容看不懂。 在上一篇中我们讲解了朴素版的dijkstra该解法的时间复杂度为 O(n^2)可以看出时间复杂度 只和 n 节点数量有关系。
如果n很大的话我们可以换一个角度来优先性能。
在 讲解 最小生成树的时候我们 讲了两个算法prim算法从点的角度来求最小生成树、Kruskal算法从边的角度来求最小生成树
这么在n 很大的时候也有另一个思考维度即从边的数量出发。
当 n 很大边 的数量 也很多的时候稠密图那么 上述解法没问题。
但 n 很大边 的数量 很小的时候稀疏图是不是可以换成从边的角度来求最短路呢
毕竟边的数量少。
有的录友可能会想n 节点数量很大边不就多吗 怎么会边的数量少呢
别忘了谁也没有规定 节点之间一定要有边连接着例如有一万个节点只有一条边这也是一张图。
了解背景之后再来看 解法思路。
#图的存储
首先是 图的存储。
关于图的存储 主流有两种方式 邻接矩阵和邻接表
#邻接矩阵
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。
例如 grid[2][5] 6表示 节点 2 链接 节点5 为有向图节点2 指向 节点5边的权值为6 套在题意里可能是距离为6 或者 消耗为6 等等
如果想表示无向图即grid[2][5] 6grid[5][2] 6表示节点2 与 节点5 相互连通权值为6。
如图
在一个 n 节点数为8 的图中就需要申请 8 * 8 这么大的空间有一条双向边即grid[2][5] 6grid[5][2] 6
这种表达方式邻接矩阵 在 边少节点多的情况下会导致申请过大的二维数组造成空间浪费。
而且在寻找节点链接情况的时候需要遍历整个矩阵即 n * n 的时间复杂度同样造成时间浪费。
邻接矩阵的优点
表达方式简单易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图在边数接近顶点数平方的图中邻接矩阵是一种空间效率较高的表示方法。
缺点
遇到稀疏图会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵造成时间浪费
#邻接表
邻接表 使用 数组 链表的方式来表示。 邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表。
邻接表的构造如图
这里表达的图是
节点1 指向 节点3 和 节点5节点2 指向 节点4、节点3、节点5节点3 指向 节点4节点4指向节点1。
有多少边 邻接表才会申请多少个对应的链表节点。
从图中可以直观看出 使用 数组 链表 来表达 边的链接情况 。
邻接表的优点
对于稀疏图的存储只需要存储边空间利用率高遍历节点链接情况相对容易
缺点
检查任意两个节点间是否存在边效率相对低需要 O(V)时间V表示某节点链接其他节点的数量。实现相对复杂不易理解
#本题图的存储
接下来我们继续按照稀疏图的角度来分析本题。
在第一个版本的实现思路中我们提到了三部曲
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
在第一个版本的代码中这三部曲是套在一个 for 循环里为什么
因为我们是从节点的角度来解决问题。
三部曲中第一步选源点到哪个节点近且该节点未被访问过这个操作本身需要for循环遍历 minDist 来寻找最近的节点。
同时我们需要 遍历所有 未访问过的节点所以 我们从 节点角度出发代码会有两层for循环代码是这样的 注意代码中的注释标记两层for循环的用处 for (int i 1; i n; i) { // 遍历所有节点第一层for循环 int minVal INT_MAX;
int cur 1;// 1、选距离源点最近且未访问过的节点 第二层for循环
for (int v 1; v n; v) {
if (!visited[v] minDist[v] minVal) {
minVal minDist[v];
cur v;
}
}visited[cur] true; // 2、标记该节点已被访问// 3、第三步更新非访问节点到源点的距离即更新minDist数组
for (int v 1; v n; v) {
if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {
minDist[v] minDist[cur] grid[cur][v];
}
}}那么当从 边 的角度出发 在处理 三部曲里的第一步选源点到哪个节点近且该节点未被访问过的时候 我们可以不用去遍历所有节点了。
而且 直接把 边带权值加入到 小顶堆利用堆来自动排序那么每次我们从 堆顶里 取出 边 自然就是 距离源点最近的节点所在的边。
这样我们就不需要两层for循环来寻找最近的节点了。
了解了大体思路我们再来看代码实现。
首先是 如何使用 邻接表来表述图结构这是摆在很多录友面前的第一个难题。
邻接表用 数组链表 来表示代码如下C中 vector 为数组list 为链表 定义了 n1 这么大的数组空间
vectorlistint grid(n 1);不少录友不知道 如何定义的数据结构怎么表示邻接表的我来给大家画一个图
图中邻接表表示
节点1 指向 节点3 和 节点5节点2 指向 节点4、节点3、节点5节点3 指向 节点4节点4 指向 节点1
大家发现图中的边没有权值而本题中 我们的边是有权值的权值怎么表示在哪里表示
所以 在vectorlistint grid(n 1); 中 就不能使用int了而是需要一个键值对 来存两个数字一个数表示节点一个数表示 指向该节点的这条边的权值。
那么 代码可以改成这样 pair 为键值对可以存放两个int
vectorlistpairint,int grid(n 1);举例来给大家展示 该代码表达的数据 如下
节点1 指向 节点3 权值为 1节点1 指向 节点5 权值为 2节点2 指向 节点4 权值为 7节点2 指向 节点3 权值为 6节点2 指向 节点5 权值为 3节点3 指向 节点4 权值为 3节点5 指向 节点1 权值为 10
这样 我们就把图中权值表示出来了。
但是在代码中 使用 pairint, int 很容易让我们搞混了第一个int 表示什么第二个int表示什么导致代码可读性很差或者说别人看你的代码看不懂。
那么 可以 定一个类 来取代 pairint, int
类或者说是结构体定义如下
struct Edge {
int to; // 邻接顶点
int val; // 边的权重Edge(int t, int w): to(t), val(w) {} // 构造函数
};这个类里有两个成员变量有对应的命名这样不容易搞混 两个int的含义。
所以 本题中邻接表的定义如下
struct Edge {
int to; // 链接的节点
int val; // 边的权重Edge(int t, int w): to(t), val(w) {} // 构造函数
};vectorlistEdge grid(n 1); // 邻接表
我们在下面的讲解中会直接使用这个邻接表的代码表示方式
#堆优化细节
其实思路依然是 dijkstra 三部曲
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
只不过之前是 通过遍历节点来遍历边通过两层for循环来寻找距离源点最近节点。 这次我们直接遍历边且通过堆来对边进行排序达到直接选择距离源点最近节点。
先来看一下针对这三部曲如果用 堆来优化。
那么三部曲中的第一步选源点到哪个节点近且该节点未被访问过我们如何选
我们要选择距离源点近的节点即该边的权值最小所以 我们需要一个 小顶堆 来帮我们对边的权值排序每次从小顶堆堆顶 取边就是权值最小的边。
C定义小顶堆可以用优先级队列实现代码如下
// 小顶堆
class mycomparison {
public:
bool operator()(const pairint, int lhs, const pairint, int rhs) {
return lhs.second rhs.second;
}
};
// 优先队列中存放 pair节点编号源点到该节点的权值
priority_queuepairint, int, vectorpairint, int, mycomparison pq;pairint, int中 第二个int 为什么要存 源点到该节点的权值因为 这个小顶堆需要按照权值来排序
有了小顶堆自动对边的权值排序那我们只需要直接从 堆里取堆顶元素小顶堆中最小的权值在上面就可以取到离源点最近的节点了 未访问过的节点不会加到堆里进行排序
所以三部曲中的第一步我们不用 for循环去遍历直接取堆顶元素
// pair节点编号源点到该节点的权值
pairint, int cur pq.top(); pq.pop();
第二步该最近节点被标记访问过 这个就是将 节点做访问标记和 朴素dijkstra 一样 代码如下
// 2. 第二步该最近节点被标记访问过
visited[cur.first] true;
cur.first 是指取 pairint, int 里的第一个int即节点编号
第三步更新非访问节点到源点的距离这里的思路 也是 和朴素dijkstra一样的。
但很多录友对这里是最懵的主要是因为两点
没有理解透彻 dijkstra 的思路没有理解 邻接表的表达方式
我们来回顾一下 朴素dijkstra 在这一步的代码和思路如果没看过我讲解的朴素版dijkstra这里会看不懂 // 3、第三步更新非访问节点到源点的距离即更新minDist数组
for (int v 1; v n; v) {
if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {
minDist[v] minDist[cur] grid[cur][v];
}
}其中 for循环是用来做什么的 是为了 找到 节点cur 链接指向了哪些节点因为使用邻接矩阵的表达方式 所以把所有节点遍历一遍。
而在邻接表中我们可以以相对高效的方式知道一个节点链接指向哪些节点。
再回顾一下邻接表的构造数组 链表
假如 加入的cur 是节点 2 那么 grid[2] 表示的就是图中第二行链表。 grid数组的构造我们在 上面 「图的存储」中讲过
所以在邻接表中我们要获取 节点cur 链接指向哪些节点就是遍历 grid[cur节点编号] 这个链表。
这个遍历方式C代码如下
for (Edge edge : grid[cur.first]) 如果不知道 Edge 是什么看上面「图的存储」中邻接表的讲解
cur.first 就是cur节点编号 参考上面pair的定义 pair节点编号源点到该节点的权值
接下来就是更新 非访问节点到源点的距离代码实现和 朴素dijkstra 是一样的代码如下
// 3. 第三步更新非访问节点到源点的距离即更新minDist数组
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点cur指向的节点为 edge
// cur指向的节点edge.to这条边的权值为 edge.val
if (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDist
minDist[edge.to] minDist[cur.first] edge.val;
pq.push(pairint, int(edge.to, minDist[edge.to]));
}
}但为什么思路一样有的录友能写出朴素dijkstra但堆优化这里的逻辑就是写不出来呢
主要就是因为对邻接表的表达方式不熟悉
以上代码中cur 链接指向的节点编号 为 edge.to 这条边的权值为 edge.val 如果对这里模糊的就再回顾一下 Edge的定义
struct Edge {
int to; // 邻接顶点
int val; // 边的权重Edge(int t, int w): to(t), val(w) {} // 构造函数
};确定该节点没有被访问过!visited[edge.to] 目前 源点到cur.first的最短距离minDist cur.first 到 edge.to 的距离 edge.val 是否 小于 minDist已经记录的 源点到 edge.to 的距离 minDist[edge.to]
如果是的话就开始更新操作。
即
if (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDist
minDist[edge.to] minDist[cur.first] edge.val;
pq.push(pairint, int(edge.to, minDist[edge.to])); // 由于cur节点的加入而新链接的边加入到优先级队里中
}
同时由于cur节点的加入源点又有可以新链接到的边将这些边加入到优先级队里中。
以上代码思路 和 朴素版dijkstra 是一样一样的主要区别是两点
邻接表的表示方式不同使用优先级队列小顶堆来对新链接的边排序
#代码实现
堆优化dijkstra完整代码如下
#include iostream
#include vector
#include list
#include queue
#include climits
using namespace std;
// 小顶堆
class mycomparison {
public:
bool operator()(const pairint, int lhs, const pairint, int rhs) {
return lhs.second rhs.second;
}
};
// 定义一个结构体来表示带权重的边
struct Edge {
int to; // 邻接顶点
int val; // 边的权重Edge(int t, int w): to(t), val(w) {} // 构造函数
};int main() {
int n, m, p1, p2, val;
cin n m;vectorlistEdge grid(n 1);for(int i 0; i m; i){
cin p1 p2 val;
// p1 指向 p2权值为 val
grid[p1].push_back(Edge(p2, val));}int start 1; // 起点
int end n; // 终点// 存储从源点到每个节点的最短距离
std::vectorint minDist(n 1, INT_MAX);// 记录顶点是否被访问过
std::vectorbool visited(n 1, false); // 优先队列中存放 pair节点源点到该节点的权值
priority_queuepairint, int, vectorpairint, int, mycomparison pq;// 初始化队列源点到源点的距离为0所以初始为0
pq.push(pairint, int(start, 0)); minDist[start] 0; // 起始点到自身的距离为0while (!pq.empty()) {
// 1. 第一步选源点到哪个节点近且该节点未被访问过 通过优先级队列来实现
// 节点 源点到该节点的距离
pairint, int cur pq.top(); pq.pop();if (visited[cur.first]) continue;// 2. 第二步该最近节点被标记访问过
visited[cur.first] true;// 3. 第三步更新非访问节点到源点的距离即更新minDist数组
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点cur指向的节点为 edge
// cur指向的节点edge.to这条边的权值为 edge.val
if (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDist
minDist[edge.to] minDist[cur.first] edge.val;
pq.push(pairint, int(edge.to, minDist[edge.to]));
}
}}if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点
else cout minDist[end] endl; // 到达终点最短路径
}
时间复杂度O(ElogE) E 为边的数量空间复杂度O(N E) N 为节点的数量
堆优化的时间复杂度 只和边的数量有关 和节点数无关在 优先级队列中 放的也是边。
以上代码中while (!pq.empty()) 里套了 for (Edge edge : grid[cur.first])
for 里 遍历的是 当前节点 cur 所连接边。
那 当前节点cur 所连接的边 也是不固定的 这就让大家分不清这时间复杂度究竟是多少
其实 for (Edge edge : grid[cur.first]) 里最终的数据走向 是 给队列里添加边。
那么跳出局部代码整个队列 一定是 所有边添加了一次同时也弹出了一次。
所以边添加一次时间复杂度是 O(E) while (!pq.empty()) 里每次都要弹出一个边来进行操作在优先级队列小顶堆中 弹出一个元素的时间复杂度是 O(logE) 这是堆排序的时间复杂度。
当然小顶堆里 是 添加元素的时候 排序还是 取数元素的时候排序这个无所谓时间复杂度都是O(E)总之是一定要排序的而小顶堆里也不会滞留元素有多少元素添加 一定就有多少元素弹出
所以 该算法整体时间复杂度为 OElogE)
网上的不少分析 会把 n 节点的数量算进来这个分析是有问题的举一个极端例子在n 为 10000且是有一条边的 图里以上代码大家感觉执行了多少次
while (!pq.empty()) 中的 pq 存的是边其实只执行了一次。
所以该算法时间复杂度 和 节点没有关系。
至于空间复杂度邻接表是 数组 链表 数组的空间 是 N 有E条边 就申请对应多少个链表节点所以是 复杂度是 N E
#拓展
当然也有录友可能想 堆优化dijkstra 中 我为什么一定要用邻接表呢我就用邻接矩阵 行不行
也行的。
但 正是因为稀疏图所以我们使用堆优化的思路 如果我们还用 邻接矩阵 去表达这个图的话就是 一个高效的算法 使用了低效的数据结构那么 整体算法效率 依然是低的。
如果还不清楚为什么要使用 邻接表可以再看看上面 我在 「图的存储」标题下的讲解。
这里我也给出 邻接矩阵版本的堆优化dijkstra代码
#include iostream
#include vector
#include list
#include climits
using namespace std;
// 小顶堆
class mycomparison {
public:
bool operator()(const pairint, int lhs, const pairint, int rhs) {
return lhs.second rhs.second;
}
};int main() {
int n, m, p1, p2, val;
cin n m;vectorvectorint grid(n 1, vectorint(n 1, INT_MAX));for(int i 0; i m; i){
cin p1 p2 val;
// p1 指向 p2权值为 val
grid[p1][p2] val;
}int start 1; // 起点
int end n; // 终点// 存储从源点到每个节点的最短距离
std::vectorint minDist(n 1, INT_MAX);// 记录顶点是否被访问过
std::vectorbool visited(n 1, false);// 优先队列中存放 pair节点源点到该节点的距离
priority_queuepairint, int, vectorpairint, int, mycomparison pq;// 初始化队列源点到源点的距离为0所以初始为0
pq.push(pairint, int(start, 0));minDist[start] 0; // 起始点到自身的距离为0while (!pq.empty()) {
// 节点 源点到该节点的距离
// 1、选距离源点最近且未访问过的节点
pairint, int cur pq.top(); pq.pop();if (visited[cur.first]) continue;visited[cur.first] true; // 2、标记该节点已被访问// 3、第三步更新非访问节点到源点的距离即更新minDist数组
for (int j 1; j n; j) {
if (!visited[j] grid[cur.first][j] ! INT_MAX (minDist[cur.first] grid[cur.first][j] minDist[j])) {
minDist[j] minDist[cur.first] grid[cur.first][j];
pq.push(pairint, int(j, minDist[j]));
}
}
}if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点
else cout minDist[end] endl; // 到达终点最短路径}
时间复杂度O(E * (N logE)) E为边的数量N为节点数量空间复杂度O(log(N^2))
while (!pq.empty()) 时间复杂度为 E while 里面 每次取元素 时间复杂度 为 logE和 一个for循环 时间复杂度 为 N 。
所以整体是 E * (N logE)
#总结
在学习一种优化思路的时候首先就要知道为什么要优化遇到了什么问题。
正如我在开篇就给大家交代清楚 堆优化方式的背景。
堆优化的整体思路和 朴素版是大体一样的区别是 堆优化从边的角度出发且利用堆来排序。
很多录友别说写堆优化 就是看 堆优化的代码也看的很懵。
主要是因为两点
不熟悉邻接表的表达方式对dijkstra的实现思路还是不熟
这是我为什么 本篇花了大力气来讲解 图的存储就是为了让大家彻底理解邻接表以及邻接表的代码写法。
至于 dijkstra的实现思路 朴素版 和 堆优化版本 都是 按照 dijkstra 三部曲来的。
理解了三部曲dijkstra 的思路就是清晰的。
针对邻接表版本代码 我做了详细的 时间复杂度分析也让录友们清楚相对于 朴素版时间都优化到哪了。
最后 我也给出了 邻接矩阵的版本代码分析了这一版本的必要性以及时间复杂度。
至此通过 两篇dijkstra的文章终于把 dijkstra 讲完了如果大家对我讲解里所涉及的内容都吃透的话详细对 dijkstra 算法也就理解到位了。 文章转载自： http://www.morning.gjwkl.cn.gov.cn.gjwkl.cn http://www.morning.lizimc.com.gov.cn.lizimc.com http://www.morning.rzcbk.cn.gov.cn.rzcbk.cn http://www.morning.qpqb.cn.gov.cn.qpqb.cn http://www.morning.wnhsw.cn.gov.cn.wnhsw.cn http://www.morning.mhnrx.cn.gov.cn.mhnrx.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.llxqj.cn.gov.cn.llxqj.cn http://www.morning.nydtt.cn.gov.cn.nydtt.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.ckdgj.cn.gov.cn.ckdgj.cn http://www.morning.c7496.cn.gov.cn.c7496.cn http://www.morning.pzcqz.cn.gov.cn.pzcqz.cn http://www.morning.spqbp.cn.gov.cn.spqbp.cn http://www.morning.qkrzn.cn.gov.cn.qkrzn.cn http://www.morning.cyyhy.cn.gov.cn.cyyhy.cn http://www.morning.yodajy.cn.gov.cn.yodajy.cn http://www.morning.gwmny.cn.gov.cn.gwmny.cn http://www.morning.fdwlg.cn.gov.cn.fdwlg.cn http://www.morning.skbbt.cn.gov.cn.skbbt.cn http://www.morning.bpmnl.cn.gov.cn.bpmnl.cn http://www.morning.cgtfl.cn.gov.cn.cgtfl.cn http://www.morning.bsrqy.cn.gov.cn.bsrqy.cn http://www.morning.jbtlf.cn.gov.cn.jbtlf.cn http://www.morning.tgxrm.cn.gov.cn.tgxrm.cn http://www.morning.dwfzm.cn.gov.cn.dwfzm.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.bkppb.cn.gov.cn.bkppb.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.wlgpz.cn.gov.cn.wlgpz.cn http://www.morning.ljmbd.cn.gov.cn.ljmbd.cn http://www.morning.rdnpg.cn.gov.cn.rdnpg.cn http://www.morning.rcntx.cn.gov.cn.rcntx.cn http://www.morning.rsfp.cn.gov.cn.rsfp.cn http://www.morning.txfzt.cn.gov.cn.txfzt.cn http://www.morning.xhgxd.cn.gov.cn.xhgxd.cn http://www.morning.langlaitech.cn.gov.cn.langlaitech.cn http://www.morning.rqwwm.cn.gov.cn.rqwwm.cn http://www.morning.tdhxp.cn.gov.cn.tdhxp.cn http://www.morning.fqyxb.cn.gov.cn.fqyxb.cn http://www.morning.rdzgm.cn.gov.cn.rdzgm.cn http://www.morning.fqyxb.cn.gov.cn.fqyxb.cn http://www.morning.mwmtk.cn.gov.cn.mwmtk.cn http://www.morning.hhpbj.cn.gov.cn.hhpbj.cn http://www.morning.pdgqf.cn.gov.cn.pdgqf.cn http://www.morning.eshixi.com.gov.cn.eshixi.com http://www.morning.rnqnp.cn.gov.cn.rnqnp.cn http://www.morning.kqpxb.cn.gov.cn.kqpxb.cn http://www.morning.ffmx.cn.gov.cn.ffmx.cn http://www.morning.lcbgf.cn.gov.cn.lcbgf.cn http://www.morning.lthgy.cn.gov.cn.lthgy.cn http://www.morning.rmdwp.cn.gov.cn.rmdwp.cn http://www.morning.shuanga.com.cn.gov.cn.shuanga.com.cn http://www.morning.5-73.com.gov.cn.5-73.com http://www.morning.gllhx.cn.gov.cn.gllhx.cn http://www.morning.nrbcx.cn.gov.cn.nrbcx.cn http://www.morning.qnzld.cn.gov.cn.qnzld.cn http://www.morning.rkfgx.cn.gov.cn.rkfgx.cn http://www.morning.qxbsq.cn.gov.cn.qxbsq.cn http://www.morning.gbpanel.com.gov.cn.gbpanel.com http://www.morning.pjtnk.cn.gov.cn.pjtnk.cn http://www.morning.qkcyk.cn.gov.cn.qkcyk.cn http://www.morning.frpfk.cn.gov.cn.frpfk.cn http://www.morning.dxrbp.cn.gov.cn.dxrbp.cn http://www.morning.mtrz.cn.gov.cn.mtrz.cn http://www.morning.ntcmrn.cn.gov.cn.ntcmrn.cn http://www.morning.xkjrq.cn.gov.cn.xkjrq.cn http://www.morning.ylkkh.cn.gov.cn.ylkkh.cn http://www.morning.tgcw.cn.gov.cn.tgcw.cn http://www.morning.yskhj.cn.gov.cn.yskhj.cn http://www.morning.zdsdn.cn.gov.cn.zdsdn.cn http://www.morning.sfsjh.cn.gov.cn.sfsjh.cn http://www.morning.qfrsm.cn.gov.cn.qfrsm.cn http://www.morning.jikuxy.com.gov.cn.jikuxy.com http://www.morning.wmqrn.cn.gov.cn.wmqrn.cn http://www.morning.wzknt.cn.gov.cn.wzknt.cn http://www.morning.pzcqz.cn.gov.cn.pzcqz.cn http://www.morning.ydfr.cn.gov.cn.ydfr.cn http://www.morning.rtsd.cn.gov.cn.rtsd.cn http://www.morning.yfnjk.cn.gov.cn.yfnjk.cn
