资讯专栏INFORMATION COLUMN

图的基本算法

姘搁『 / 3206人阅读

摘要:图的基本算法算法算法算法算法算法最小生成树拓扑排序图的和算法算法为稠密阵所以用邻接矩阵存储用于记录每一个点距离第一个点的距离用于记录

bellman-ford算法

#include#include#includeusing 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#include#includeusing 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#include#includeusing 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#include#include#includeusing 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#include#includeusing 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#includeusing 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#include#includeusing 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]
            
                     
             
               

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/124093.html

相关文章

  • 基础数据结构和算法概念

    摘要:数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象,称为结点。 本文涉及更多的是概念,代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念,可能部分地方会涉及更高级的算法和算法,具体内容以...

    fsmStudy 评论0 收藏0
  • 以静制动的TensorFlow Fold动态计算图介绍

    摘要:近日它们交锋的战场就是动态计算图,谁能在这场战争中取得优势,谁就把握住了未来用户的流向。所以动态框架对虚拟计算图的构建速度有较高的要求。动态计算图问题之一的多结构输入问题的高效计 随着深度学习的发展,深度学习框架之间竞争也日益激烈,新老框架纷纷各显神通,想要在广大DeepLearner的服务器上占据一席之地。近日它们交锋的战场就是动态计算图,谁能在这场战争中取得优势,谁就把握住了未来用户的流...

    waltr 评论0 收藏0
  • 算法第四版4.1-无向图详解

    摘要:树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造,得到顶点数和边数,增加一条边。该方法不符合第一个条件,上百万个顶点的图是很常见的空间不满足。 四种重要的图模型: 无向图(简单连接) 有向图(连接有方向性) 加权图(连接带有权值) 加权有向图(连接既有方向性又带有权值) 无向图 定义:由一组顶点和一组能够将两个顶点相连的边组成。 特殊:...

    scola666 评论0 收藏0
  • Adobe提出深度抠图:利用卷积网络分离图像前景与背景

    摘要:在等机构新提出的论文中,其采用了大规模数据集与深度神经网络学习图像的自然结构,从而进一步分离图像的前景与背景。一张手动抠图的前景图拥有简单背景作为输入。对于每一张测试图像,按照降序从第列到第列显示了度量下的排名结果排名到。 抠图,一直是一件体力活,它需要大量的操作与时间。而传统抠图算法主要是以色彩为特征分离前景与背景,并在小数据集上完成,而这就造成了传统算法的局限性。在 Adobe 等机构新...

    soasme 评论0 收藏0
  • 学习JavaScript数据结构与算法 — 图

    摘要:图关联矩阵在关联矩阵表示的图中,矩阵的行表示顶点,列表示边。如图,顶点数是,边的数量是,用邻接矩阵表示图需要的空间是,而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。 定义 图和散列表、二叉树一样,是一种非线性数据结构。如图1所示,图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点,比如A和B、A和D是相邻的,而A和...

    yiliang 评论0 收藏0

发表评论

0条评论

姘搁『

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<