算法基础第三章搜索与图论
图算法(数组版)
1.1最短路径Dijkstra算法:
- 假设顶点是\(V_0到V_5\) 六个点，开始时候是没有连线的，但是已知能互相到达的顶点之间的边权。
- 步骤是每次从顶点0开始查找，找出距离顶点最短的点，然后标记该点为true,再查询该点能直达的其他点加上边权会不会比原先记录的距离值小—>即更新最短距离；遍历完了所有从该点能到的点后再次回到起点。
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXV=1000;
const int INF = 0x3f3f3f3f;//很大的数
int n,m,s,G[MAXV][MAXV];//n为顶点数量，m为边数，s为起点
int d[MAXV];//起点到各点的最短路径长度
bool vis[MAXV]={false}; //标记访问数组 false为没有访问，true 为访问过
/*本题输入:
6 8 0 //6个顶点 8条边 起点为0号
0 1 1 从0点到1点距离为1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
*/
void Dijkstra(int s){
fill(d,d+MAXV,INF);
d[s]=0; //初始化操作
for(int i=0;i<n;i++){//每次更新完都要回到起点,循环n次
int u=-1,MIN=INF; //比较下面，u使得d[u]最小，MIN存放该最小的d[u]
for(int j=0;j<n-1;j++){
if(vis[j]==false && d[j]<MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return;//剩下的顶点和起点s不通
vis[u]= true;//找出距离起点最短的点 u
for(int v=0;v<n;v++){//从 u 开始走，更新最短距离
if(vis[v]==false && G[u][v]!=INF && d[u]+G[u][v]<d[v]){//G[u][v]是从u到v顶点的直通距离
d[v]=d[u]+G[u][v];
}
}
}
}
int main(){
int u,v,w;
cin>>n>>m>>s;
fill(G[0],G[0]+MAXV*MAXV,INF);
for(int i=0;i<m;i++){
cin>>u>>v>>w;
G[u][v]=w;
}
Dijkstra(s); // s
for(int i=0;i<n;i++){
cout<<d[i];//输出结果最短路径
}
return 0;
}
1.2基本模板
//初始化
for(循环n次){
u = 使得d[u]最小且还未被访问的顶点的标号;
记u已被访问;
for(从u出发能到达的所有顶点v){
if(v未被访问 && 以u为中介点使s到顶点v 的最短距离d[v]更优){
优化d[v];
}
2.1图的存储
树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(1) 邻接矩阵：g[a][b] 存储边a->b
(2) 邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
当这个图是n个点 m条边的无向图时，那么m可能和 n的2倍差不多:
这时， 不妨设M = 2 * N
h[N] e[M]、ne[M]
2.2树与图的遍历
时间复杂度O(n+m),n表示点数，m表示边数
(1)深度优先遍历
int dfs(int u)
{
st[u] = true;
for(int i = h[u];i!= - 1;i = ne[i])
{
int j = e[i];
if(!st[j]) dfs(j);
}
}
(2)宽度优先遍历
queue<int> q;
st[1] = true;
q.push(1);
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t];h!=-1;i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
q.push(j);
}
}
}
最短路算法
3.dijkstra算法
- 朴素版dijkstra算法适合稠密图，用邻接矩阵存储
- 堆优化版适合稀疏图，用邻接表存储 点的范围较大–稀疏图
3.1朴素\(dijkstra\)算法
时间复杂是 \(O(n^2+m)\), n 表示点数，m 表示边数
1、当到一个时间点时，图上部分的点的最短距离已确定，部分点的最短距离未确定。
2、选一个所有未确定点中离源点最近的点，把他认为成最短距离。
3、再把这个点所有出边遍历一边，更新所有的点。
算法设计：贪心
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
// 点的坐标从1~n
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 求得是1号点到其他点的距离，就标记dist[1] = 0
// 遍历其他点
for (int i = 0; i < n - 1; i ++ ) { // 只是循环n-1次没有其他意义
int t = -1;
// 在还未用来更新最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j])) // t==-1用来确定剩余未用来更新的第一个点
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
// if(!st[j]) 可写可不写
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
st[]更确切的含义是某个点是否已经更新过其他点，st最短路确定而不是它的最短距离是否已经确定。所以更新其他点的距离时，前面更新过的点也要更新 其实也可以加上
if(!st[j])
3.2堆优化dijkstra算法
思路：
集合S中的点表示已经找到最短路径
堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。
1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为：
弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
用该点更新临界点的距离，若更新成功就加入到堆中。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 150010;
// 稀疏图用邻接矩阵来存储
int h[N], e[N], ne[N], idx;
int w[N], dist[N];
bool st[N];
int n, m;
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c; // 边的权重,
// 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
h[a] = idx++;
}
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[1] = 0;
heap.push({0,1}); // 把初始值放入小根堆里 距离--点
while(heap.size()) {
PII k = heap.top(); // 取不在集合S中距离最短的点，集合S表示已经确定最短路的点的集合
heap.pop();
int v = k.second, distance = k.first;
if(st[v]) continue;
st[v] = true;
// 以 v 为出点，遍历v的邻接点
for(int i = h[v]; i != -1; i = ne[i]) {
int j = e[i];
if(dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n,&m);
while(m--) {
int x,y,c;
scanf("%d%d%d", &x,&y,&c);
add(x,y,c);
}
cout << dijkstra() << endl;
return 0;
}
一些问题：
- 在更新dist时，有可能两个点重复进堆，有的点它既是a的邻接点又是b的邻接点，这样的点可能会在更新a的邻接点时加进一次，右在更新b的邻接点的时再进入一次，这样队列中就有两个一样的点，虽然距离不同，所以用
st数组对已经找出最短路径的点进行标记，避免重复计算
4.\(Bellman-Ford\)算法
题目：有边数限制的最短路a
单源最短路径算法
对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。
设计：动态规划
时间复杂度：\(O(V*E)\) 顶点数 边数, \(n顶点数，m边数\)
理解：对所有边进行\(n-1\)次松弛操作,因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边，
换句话说，第1轮在所有边进行松弛后，得到的是源点最多经过1条边到达其他顶点的最短距离；
第2轮在对所有的边进行松弛后，得到的是源点最多经过2条边到达其他顶点的最短距离；
算法描述：
1、\(dist[N]\)数组表示源顶点到所有顶点的距离，初始化为\(infinte\),\(dist[1][1]=0\),
2、计算最短路径，执行\(V-1\)次遍历
对于图中的每条边：如果起点到u的距离d加上权值w小于到终点v的距离，更新终点v的距离值d
\(if(dist[b]>dist[a]+w) dist[b]=dist[a]+w\)
例如以下加上一个拷贝数组就可以求最多经过k条边的最短距离
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
int backup[N]; // 拷贝数组,这样就保证轮数与边数一致
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
// 初始时，1号点到其他点的距离为inf
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
memcpy(backup,dist,sizeof dist); // 拷贝数组,因为更新其他点时候会影响其他点的更新信息
for (int j = 0; j < m; j ++ ) // 遍历每条边
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > backup[a] + w)
dist[b] = backup[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
判断是否有负权环，再对边进行一次额外的遍历，如果还能更新说明仍然存在一条边使得两点距离更短，事实上再更新多次还是有更新的情况。
注意：
-
如果不限制边数，直接求最短路，不需要拷贝数组
-
如果限制边数，则需要拷贝数组
-
为什么是
> 0x3f3f3f3f / 2(主要还是因为每条边都遍历了，遍历了很多无用的边) -
5、\(SPFA\)算法
题目： spafa判断负环
//blog.csdn.net/qq_35644234/article/details/61614581 这篇博客给出了过程
//www.cnblogs.com/acioi/p/11694294.html spfa求负环的解释
时间复杂度 平均情况下 \(O(m)\)，最坏情况下 \(O(nm)\), n 表示点数，m 表示边数
\(SPFA算法\)是对上面的\(bellmanford\)算法的队列优化
算法描述：首先建立一个队列，初始队列里只有起始点，建立一个表格记录起始点到所有点的最短路径(初始值赋为极大值)，然后进行松弛操作，依次用队列中的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把其加入到队列中。
求负环：如果某个点进入队列的次数超过N次则存在负环(N为图的顶点数)
最优解法：用一个cnt[i] 数组记录当前到 到 i 点的最短路径上经过的点的数量，如果 出现cnt[i] > n说明出现了负环。也可统计边数，当边数 >= n时也是出现了负环。
st数组的作用只是记录当前有哪些点在队列中
int n; // 总点数
int h[N],w[N],e[N],ne[N],idx; // 邻接表存储所有边
int dist[N];
bool st[N];// 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
// 取出队列中的一个元素来更新距离
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false; // 先弹出队列标记为false，因为后面可能还会有更新
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t]+w[i])
{
// 先更新最短距离
dist[j] = dist[t] + w[i];
// 如果被更新的点不在队列中，就要加入，因为后面需要用到其最短值
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
5、\(Floyd\)算法
\(Floyd\)算法属于暴力求解，时间复杂度\(O(n^3)\),\(n\)表示点数
// 初始化
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
d[i][j] = (i == j ? 0 : INF);
}
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ ) // z
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
if(g[l][r] > inf / 2) cout << "impossible" << endl;
else cout << g[l][r] << endl;
- 判断无最短路径的方法是
> inf / 2, 原因：加入求1~6个点的距离，6是终点，
d[1][5] = 0x3f，1到5不可达，此时 d[5][6] = -4, d[1][6] = d[1][5] + d[5][6] !=0x3f但是大于0x3f/2。此时1到6是不可达的。
6、有向无环图的拓扑序列
题目：有向无环图的拓扑序列
在图论中，拓扑排序是一个有向无环图的所有顶点的线性序列：
1、每个顶点出现一次
2、若存在一条从A到B的路径，那么在序列中顶点A在B的前面。
一个有向无环图一定至少存在一个入度为0的点
如何求拓扑序列？
- 拓扑序列中，所有的边都是从前往后的，因此入度为0的点都可以作为起点，将所有入度为0的点入队，因为前面没有点指向它，它只能指向后面的点
- 入队之后，将它指向的终点的入度减去1
入度为0的点入队
queue<int> q;
for(int i = 1;i <= n;i++) {
if(!d[i]) q.push(i);
}
遍历t的所有出边
for(int i = h[t]; i!=-1;i = ne[i]) {
int j = e[i];
}
完整模板
bool f() {
int q[N], hh = 0, tt = -1;
for(int i = 1; i < n;i++) {
if(!d[i]) q[++tt] = i; // 入队
}
while(hh <= tt) {
int t = q[hh++];
// 遍历t的终点
for(int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
d[j]--;
if(!d[j]) q[++tt] = j;
}
}
return tt == n - 1; // 是否所有点都入队了，否则表示图中有环
}
