图的基本算法
- bellman-ford算法
- dijkstra算法
- Floyd算法
- spfa算法
- prim算法（最小生成树）
- 拓扑排序
- 图的dfs和bfs
bellman-ford算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
int dist[N],backup[N];
int n,m,k;
struct edge{
int a,b,w;
}edges[M];
int bellman_ford(){
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(backup,dist,sizeof dist);
for(int j=1;j<=m;j++){
int a=edges[j-1].a,b=edges[j-1].b,w=edges[j-1].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
//if(dist[n]>0x3f3f3f3f/2)return -1;
return dist[n];
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
edges[i]={a,b,w};
}
int t=bellman_ford();
if(t>0x3f3f3f3f/2)puts("impossible");
else cout<<t;
return 0;
}
dijkstra算法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N]; //为稠密阵所以用邻接矩阵存储
int dist[N]; //用于记录每一个点距离第一个点的距离
bool st[N]; //用于记录该点的最短距离是否已经确定
int n,m;
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[t]>dist[j]))
t=j;
}
st[t]=true;
for(int u=1;u<=n;u++){
dist[u]=min(dist[u],dist[t]+g[t][u]);
}
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径
//所以每个点初始为无限大
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边
}
cout<<Dijkstra()<<endl;
return 0;
}
Floyd算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210;
int g[N][N];
int m,n,k;
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i==j)g[i][j]=0;
else g[i][j]=999999;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
for(int v=1;v<=n;v++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]>g[i][v]+g[v][j])
g[i][j]=g[i][v]+g[v][j];
}
}
}
while(k--){
int x,y;
cin>>x>>y;
if(g[x][y]>= 900000)printf("impossible\n");
else cout<<g[x][y]<<endl;
}
return 0;
}
spfa算法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],w[N],idx;
int n, m;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int>q;
q.push(1);
st[1]=true;
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=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];
}
int main(){
memset(h,-1,sizeof(h));
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=spfa();
if(t==0x3f3f3f3f)puts("impossible");
else cout<<t;
return 0;
}
prim算法（最小生成树）
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int n,m;
int g[N][N],dist[N];
bool st[N];
int prim(){
memset(dist,0x3f,sizeof dist);
int ans=0;
for(int i=1;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;
if((i-1)&&dist[t]==0x3f3f3f3f)return 0x3f3f3f3f;
if(i-1) ans+=dist[t];
for(int v=1;v<=n;v++){
dist[v]=min(dist[v],g[t][v]);
}
}
return ans;
}
int main(){
memset(g,0x3f,sizeof g);
cin >> n >> m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int t=prim();
if(t==0x3f3f3f3f)cout<<"impossible";
else cout<<t;
return 0;
}
拓扑排序
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],idx;
int n,m;
int q[N],d[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort(){
int hh=0,tt=-1;
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!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(d[j]==0) q[++tt]=j;
}
}
return tt==n-1;
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
if(topsort()){
for(int i=0;i<n;i++){
cout<<q[i]<<' ';
}
}
else{
cout<<-1;
}
return 0;
}
图的dfs和bfs
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
//dfs求岛屿面积
const int N = 1100;
int arr[N][N], book[N][N], sum = 1, m, n, x, y;
void dfs(int x, int y) {
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int ddx, ddy;
for (int i = 0;i < 4;i++) {
ddx = x + dx[i];
ddy = y + dy[i];
if (ddx > m || ddx<1 || ddy>n || ddy < 1)
continue;
if (arr[ddx][ddy] > 0 && book[ddx][ddy] == 0) {
book[ddx][ddy] = 1;
sum++;
dfs(ddx, ddy);
}
}
}
int main() {
cin >> m >> n >> x >> y;
for (int i = 1;i <= m;i++)
for (int j = 1;j <= n;j++)
cin >> arr[i][j];
book[x][y] = 1;
dfs(x, y);
cout << sum;
return 0;
}
//bfs求岛屿面积
typedef pair<int, int> PII;
const int N = 110;
int arr[N][N], book[N][N] = { 0 },m,n,x,y,ans=1;
int main() {
queue<PII>q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int ddx, ddy;
cin >> m >> n>>x>>y;
for (int i = 1;i <= m;i++)
for (int j = 1;j <= n;j++)
cin >> arr[i][j];
book[x][y] = 1;
q.push({ x,y });
while (!q.empty()) {
auto tmp = q.front();
for (int i = 0;i < 4;i++) {
ddx = tmp.first + dx[i];
ddy = tmp.second + dy[i];
if (ddx > m || ddx<1 || ddy>n || ddy < 1)
continue;
if (arr[ddx][ddy] > 0 && book[ddx][ddy] == 0) {
book[ddx][ddy] = 1;
q.push({ ddx,ddy });
ans++;
}
}
q.pop();
}
cout << ans;
return 0;
}
//dfs求最短路（bfs也可以）
const int N = 110;
int Min = 99999, arr[N][N], m, n, book[N][N] = { 0 },p,q;
void dfs(int x,int y , int step) {
int ddx, ddy;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
if (x == p && y == q) {
if (step < Min) {
Min = step;
}
return;
}
for (int i = 0;i < 4;i++) {
ddx = x + dx[i];
ddy = y + dy[i];
if (ddx > m || ddx<1 || ddy>n ||ddy < 1)
continue;
if (arr[ddx][ddy] == 0 && book[ddx][ddy] == 0) {
book[ddx][ddy] = 1;
dfs(ddx, ddy, step + 1);
book[ddx][ddy] = 0;
}
}
}
int main() {
cin >> m >> n;
for (int i = 1;i <= m;i++) {
for (int j = 1;j <= n;j++) {
cin >> arr[i][j];
}
}
cin >> p >> q;
book[1][1] = 1;
dfs(1,1,0);
cout << Min;
return 0;
}