成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

圖的基本算法

姘擱『 / 3443人閱讀

摘要：圖的基本算法算法算法算法算法算法最小生成樹(shù)拓?fù)渑判驁D的和算法算法為稠密陣所以用鄰接矩陣存儲(chǔ)用于記錄每一個(gè)點(diǎn)距離第一個(gè)點(diǎn)的距離用于記錄

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];    //為稠密陣所以用鄰接矩陣存儲(chǔ)int dist[N];    //用于記錄每一個(gè)點(diǎn)距離第一個(gè)點(diǎn)的距離bool st[N];     //用于記錄該點(diǎn)的最短距離是否已經(jīng)確定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);    //初始化圖 因?yàn)槭乔笞疃搪窂?/span>                                //所以每個(gè)點(diǎn)初始為無(wú)限大    while(m--)    {        int x,y,z;        cin>>x>>y>>z;        g[x][y]=min(g[x][y],z);     //如果發(fā)生重邊的情況則保留最短的一條邊    }    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算法（最小生成樹(shù)）

#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;}

拓?fù)渑判?/h2> 
#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]
            
                     
             
               

                   
 文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

                 
                   
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/124093.html

相關(guān)文章

  • 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法概念

    摘要：數(shù)據(jù)結(jié)構(gòu)程序數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。這兩部分信息組成數(shù)據(jù)元素的存儲(chǔ)映象，稱(chēng)為結(jié)點(diǎn)。 本文涉及更多的是概念，代碼部分請(qǐng)參考之前寫(xiě)過(guò)的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數(shù)據(jù)結(jié)構(gòu)和查找算法 本文主要是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法概念，可能部分地方會(huì)涉及更高級(jí)的算法和算法，具體內(nèi)容以...

    fsmStudy 評(píng)論0 收藏0

  • 以靜制動(dòng)的TensorFlow Fold動(dòng)態(tài)計(jì)算圖介紹

    摘要：近日它們交鋒的戰(zhàn)場(chǎng)就是動(dòng)態(tài)計(jì)算圖，誰(shuí)能在這場(chǎng)戰(zhàn)爭(zhēng)中取得優(yōu)勢(shì)，誰(shuí)就把握住了未來(lái)用戶的流向。所以動(dòng)態(tài)框架對(duì)虛擬計(jì)算圖的構(gòu)建速度有較高的要求。動(dòng)態(tài)計(jì)算圖問(wèn)題之一的多結(jié)構(gòu)輸入問(wèn)題的高效計(jì) 隨著深度學(xué)習(xí)的發(fā)展，深度學(xué)習(xí)框架之間競(jìng)爭(zhēng)也日益激烈，新老框架紛紛各顯神通，想要在廣大DeepLearner的服務(wù)器上占據(jù)一席之地。近日它們交鋒的戰(zhàn)場(chǎng)就是動(dòng)態(tài)計(jì)算圖，誰(shuí)能在這場(chǎng)戰(zhàn)爭(zhēng)中取得優(yōu)勢(shì)，誰(shuí)就把握住了未來(lái)用戶的流...

    waltr 評(píng)論0 收藏0

  • 算法第四版4.1-無(wú)向圖詳解

    摘要：樹(shù)是一副無(wú)環(huán)連通圖。互不相連的樹(shù)組成的集合稱(chēng)為森林。表示無(wú)向圖的數(shù)據(jù)類(lèi)型圖的基本操作的兩個(gè)構(gòu)造，得到頂點(diǎn)數(shù)和邊數(shù)，增加一條邊。該方法不符合第一個(gè)條件，上百萬(wàn)個(gè)頂點(diǎn)的圖是很常見(jiàn)的空間不滿足。 四種重要的圖模型： 無(wú)向圖（簡(jiǎn)單連接） 有向圖（連接有方向性） 加權(quán)圖（連接帶有權(quán)值） 加權(quán)有向圖（連接既有方向性又帶有權(quán)值） 無(wú)向圖 定義：由一組頂點(diǎn)和一組能夠?qū)蓚€(gè)頂點(diǎn)相連的邊組成。 特殊：...

    scola666 評(píng)論0 收藏0

  • Adobe提出深度摳圖：利用卷積網(wǎng)絡(luò)分離圖像前景與背景

    摘要：在等機(jī)構(gòu)新提出的論文中，其采用了大規(guī)模數(shù)據(jù)集與深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)圖像的自然結(jié)構(gòu)，從而進(jìn)一步分離圖像的前景與背景。一張手動(dòng)摳圖的前景圖擁有簡(jiǎn)單背景作為輸入。對(duì)于每一張測(cè)試圖像，按照降序從第列到第列顯示了度量下的排名結(jié)果排名到。 摳圖，一直是一件體力活，它需要大量的操作與時(shí)間。而傳統(tǒng)摳圖算法主要是以色彩為特征分離前景與背景，并在小數(shù)據(jù)集上完成，而這就造成了傳統(tǒng)算法的局限性。在 Adobe 等機(jī)構(gòu)新...

    soasme 評(píng)論0 收藏0

  • 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 圖

    摘要：圖關(guān)聯(lián)矩陣在關(guān)聯(lián)矩陣表示的圖中，矩陣的行表示頂點(diǎn)，列表示邊。如圖，頂點(diǎn)數(shù)是，邊的數(shù)量是，用鄰接矩陣表示圖需要的空間是，而使用關(guān)聯(lián)矩陣表示圖需要的空間是。廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。 定義 圖和散列表、二叉樹(shù)一樣，是一種非線性數(shù)據(jù)結(jié)構(gòu)。如圖1所示，圖由一系列頂點(diǎn)以及連接頂點(diǎn)的邊構(gòu)成。由一條邊連接在一起的頂點(diǎn)成為相鄰頂點(diǎn)，比如A和B、A和D是相鄰的，而A和...

    yiliang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<