图的基本算法

admin • • C/C++

图的基本算法

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("impossiblen");
        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;
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>