（题目来源：Acwing)
一.图的遍历Acwing847
给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。
输入格式
第一行包含两个整数n和m。接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。(
)
输出格式
输出一个整数，表示1号点到n号点的最短距离。
因为每条边的长度都是1，所以bfs一遍，即可得到1号点到n号点的最短距离
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+100,inf = 0x3f3f3f3f;
int n,m;
int dist[N];
int h[N],e[N],ne[N],idx;
bool st[N];
queue<int> q;
// 使用邻接表来存图
void add(int a,int b)
{
e[idx] =b,ne[idx] = h[a],h[a] = idx++;
}
void bfs()
{
memset(dist,0x3f,sizeof dist);
q.push(1);
dist[1] = 0;
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j] && dist[j] > dist[t]+1)
{
dist[j] = dist[t]+1;
q.push(j);
st[j] =true;
}
}
}
}
int main()
{
cin>>n>>m;
// 邻接表头的初始化！！！
memset(h,-1,sizeof h);
while(m --)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
bfs();
if(dist[n] == inf) cout<<-1<<endl;
else cout<<dist[n]<<endl;
return 0;
}
二.有向图的拓扑排序(Acwing848)
给定一个n个点m条边的有向图，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m (
接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。
输出格式
共一行，如果存在拓扑序列，则输出拓扑序列。
否则输出-1。
一个有向无环图一定存在至少一个拓扑序列
我们可以将所有入度为0的点入队，这些点均可以作起点( 拓扑序列不唯一)，每次将队头的点取出，将这个点的所有邻点的入度减1， 减完后如果该点的入度为0，将其入队，重复此过程，直到所有的点的入度都减为0，根据出队的顺序，就可以得到一个拓扑序列。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5+100;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N]; //d数组用来维护某个点的入度
//使用邻接表来存图
void add(int a,int b)
{
e[idx] = b, ne[idx] = h[a],h[a] = idx++;
}
bool bfs()
{
int hh = 0,tt = -1;
//所有入度为0的点都可以放到拓扑序列的前面
//队列的点入度全部为0
for(int i = 1; i<=n; i++)
if(d[i] == 0)
q[++tt] = i;
while(hh<=tt)
{
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i])
{
//每次取出队头，将与之相连的点的入度减1
//如果减完后该点的入度也为1，将它入队
int j = e[i];
if(--d[j]==0)
q[++tt] = j;
}
}
return n-1 == tt;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i = 1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
//b点的入度+1
d[b]++;
}
if(bfs())
for(int i = 0; i<n; i++)
cout<<q[i]<<" ";
else
cout<<-1<<endl;
return 0;
}
三.单源最短路
1.朴素Dijkstra算法( )
)(Acwing849)
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式
第一行包含整数n和m。(
)
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
我们用集合S来表示已经确定最短距离的点的集合，集合U表示未确定最短距离的点的集合。 开始将1号点与每个点的距离设置成正无穷，遍历1号点的每一个邻点，找到一条权重最小的边，将这个点加入到S中，用这个点来更新1号点到其他点的距离，然后再从U中找到距离1号点最短的点，将其加入S中，并用此点来更新其他点到1号点的距离，重复上述过程，直到所有点均在S中。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
//初始化距离
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for(int i = 0; i<n; i++)
{
int t = -1;
for(int j = 1; j<=n ; j++)
{
if(!st[j] && (t==-1 || dist[j]<dist[t]))
t = j;
}
st[t] = true;
//用该点来更新到其他点的距离
for(int j = 1; j<=n ; j++)
dist[j] = min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
//稠密图，且点数较少，可用邻接矩阵来存图
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(g[a][b],c);
}
int ans = dijkstra();
cout<<ans<<endl;
return 0;
}
2.堆优化版的Dijkstra算法()
)(Acwing850)
题目描述输入输出与上面一题均相同，但点数和边数有变，
朴素版的Dijkstra算法时间复杂度与边数无关，所以一般可处理稠密图，而这一题很明显是稀疏图，如果用朴素版来做，时间大概是，会tle，而堆优化版的Dijkstra时间复杂度是
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+100;
typedef pair<int,int>PII; //距离，编号
int n,m;
int e[N],w[N],head[N],ne[N],idx;
int dist[N];
bool st[N];
//用静态邻接表存储图
void add(int s,int to,int d)
{
e[idx] = to,w[idx] = d,ne[idx] = head[s],head[s] = idx++;
}
int dijkstra()
{
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
//用小根堆维护距离
priority_queue<PII,vector<PII>,greater<PII>>heap;
heap.push({0,1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int distance = t.first,u = t.second;
if(st[u]) continue;
st[u]= true;
for(int i = head[u]; ~i ;i = ne[i])
{
int k = e[i];
//e[i]存储边的终点
if(dist[k]>distance + w[i])
{
dist[k] = distance + w[i];
heap.push({dist[k],k});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int ans = dijkstra();
cout<<ans<<endl;
return 0;
}
3.Spfa算法(Acwing851)
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出”impossible”。
Spfa算法是由Bellman-ford算法(之前的一篇博客简单介绍过,戳这里)通过队列优化过的算法，用一个队列存储待优化的点，一开始先加入起点，当队列不为空时，每次取出队头，遍历该点的所有出边，如果某个邻点的距离可以更新，进行松弛操作，并将这个点加入队列中。这样不断从队列中取出点进行松弛操作，直到队列为空为止。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+100;
typedef pair<int,int>PII; //距离，编号
int n,m;
int e[N],w[N],head[N],ne[N],idx;
int dist[N];
bool st[N];
//用静态邻接表存储图
void add(int s,int to,int d)
{
e[idx] = to,w[idx] = d,ne[idx] = head[s],head[s] = idx++;
}
int spfa()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = head[t]; ~i ;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] =false;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int ans = spfa();
if(ans == -1)
puts("impossible");
else
cout<<ans;
return 0;
}
4.用spfa算法判断负环(Acwing852)
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
如果图中存在负权回路，则输出“Yes”，否则输出“No”。
再spfa算法中，我们每次遍历某个点的邻边时，如果可以进行松弛操作，说明dist[t]+w[i]<dist[j]，而边权未负时此性质也一定满足，而且该边会进行松弛操作(每走一次负边，最短距离都会变得更短)，所以我们可以利用一个cnt数组来维护起点到某个点最短路包含的边数(每次进行松弛操作时，同时更新cnt的信息)，如果cnt[x]>=n，说明从起点到x点经过了n条边，等价于经过了n+1个点，但图中一共只有n个点，由抽屉原理知，一定存在相同的点，即存在环，而且该点经过松弛操作，那么这个环一定是负环。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int M = 1e5+100,N = 2010;
int n,m;
int e[M],w[M],head[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];
void add(int a,int b,int c)
{
e[idx] = b,w[idx] = c,ne[idx] = head[a],head[a] = idx ++;
}
bool spfa()
{
queue<int>q;
//所有的顶点都入队，因为负环不一定在以1为起点的路径上
for(int i = 1; i<=n ;i++)
{
q.push(i);
st[i] = false;
}
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for( int i = head[t] ; ~i ; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n)
return true;
if(!st[j])
{
q.push(j);
st[j] = false;
}
}
}
}
return false;
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof head);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
bool ans = spfa();
if(ans) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
5.Kruskal算法求最小生成树(Acwing859)
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
对一个具有n个顶点，m条边的图来说，我们假设边集为空，则这个图只含有n个点，也可以看做这是一个n个根节点的森林，我们将边集按照权重进行排序，枚举每一条边，如果这条边的两个顶点属于不同的连通块(树)，将两个点合并到一个集合中，如果这条边的两个顶点已经在一个连通块中(树)中，则继续枚举边的过程，直到集合中已经包含n-1条边，就得到最小生成树。
查询是两个点是否属于同一连通块以及将两个点合并到一个连通块中，我们可以利用并查集来维护，在O(1)的情况下完成操作。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5+100;
int n,m;
int p[N];
struct Edge{
int a,b,w;
//重载运算符<
bool operator<(const Edge& W)const
{
return w<W.w;
}
}edge[N];
//使用并查集来维护当前的连通块
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
//将所有的边按照权重从小到大排序
sort(edge,edge+m);
//初始化并查集
for(int i = 1; i<=n; i++) p[i] = i;
//ans维护最小生成树的权重之和,cnt维护连通块当中的边
int ans = 0, cnt = 0;
//枚举每一条边
for(int i = 0; i<m;i ++)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
a = find(a);
b = find(b);
//如果a 与 b 不连通
if(a!=b)
{
//将a这个点加入到集合中来
p[a] = b;
//维护ans
ans += w;
cnt++;
}
}
//所有边都遍历完之后,如果cnt不等于n-1,则不存在最小生成树
if(cnt != n-1)
return 0x3f3f3f3f;
return ans;
}
int main()
{
//n：顶点数 m：边数
cin>>n>>m;
for(int i = 0; i<m; i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
//表示a与b之间有一条权重为w的边
edge[i] = {a,b,w};
}
int ans = kruskal();
if(ans == 0x3f3f3f3f)
puts("impossible");
else
cout<<ans<<endl;
return 0;
}
6.Prim算法求最小生成树(Acwing858)
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
我们用集合S维护已经加入到最小生成树当中的点。开始我们将所有顶点之间的距离初始化成+∞，然后迭代n次，找到集合S外距离集合最近的点（该点与集合中与该点相连的边中权重最小），用该点更新S外的点到S的距离，并将该点加入到集合中。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 510,inf = 0x3f3f3f3f;
int n,m,ans;
int dist[N];
int g[N][N];
bool st[N];
int prim()
{
memset(dist,0x3f,sizeof dist);
//迭代n次，每次向集合中添加一个点
for(int i = 0; i<n; i++)
{
int t = -1;
for(int j = 1; j<=n; j++)
if(!st[j] && (t == -1||dist[t]>dist[j]))
t = j;
if(i && dist[t] == inf) return inf;
if(i) ans+=dist[t];
st[t] = true;
//更新这个点到其他点的距离
for(int j = 1; j<=n; j++)
dist[j] = min(dist[j],g[t][j]);
}
return ans;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m --)
{
int a,b,w;
cin>>a>>b>>w;
g[a][b] = g[b][a] = min(g[a][b],w);
}
int ans = prim();
if(ans == inf)
puts("impossible");
else
cout<<ans<<endl;
return 0;
}
之后会补充二分图以及有向图的强连通分量，无向图的双连通分量hh
