首页 > 代码库 > 图论算法大集锦
图论算法大集锦
1.图的存储:
(1)邻接矩阵：
#include<iostream>#include<cstdio>#include<cstdlib>#define MAXN 0x7fffffff//没有路径（边的长度为极限）； #define maxn 9999//数据边的最大值； #define MAX 0x7fffffff/3//两极限边相加可能超过int 大小； using namespace std;int m,n;//点的个数和边的个数；int s[maxn][maxn];void adjacency_matrix_storage(){ cin>>m>>n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) s[i][j]=MAXN; for(int i=1;i<=n;++i) { int s1,s2,weight; cin>>s1>>s2>>weight; s[s1][s2]=weight; //s[s2][s1]=weight; 如果是无向边就加上这句； } } int main(){ adjacency_matrix_storage(); //后面是其他操作； return 0; }
(2)邻接表：
#include<iostream>#include<cstdio>#include<cstdlib>#define maxn 99999#define MAXN 0x7fffffff/3using namespace std;struct node{ int a,b,w,next;};node edge[maxn];//用邻接表存储边； int head[maxn],sum=1;//存储顶点，sum为下标； int m,n; //顶点个数和边的个数； void push(int a,int b,int c){ edge[sum].a=a; edge[sum].b=b; edge[sum].w=c; edge[sum].next=head[a]; head[a]=sum++;}void Initialization(){ sum=1; for(int i=1;i<=m*n;++i) { head[i]=-1;//用-1作为标志表明链表的结束； edge[i].w=MAXN; }}int main(){ int i,j; cin>>m>>n; Initialization(); for(i=1;i<=n;++i) { int a,b,c; cin>>a>>b>>c; push(a,b,c);//有向边； } cin>>j; cout<<endl; for(int k=head[j];k!=-1;k=edge[k].next)//调用顶点J相连的每一条边； { int l=edge[k].b;//L和顶点J的关系是:L和J之间存在一条从J指向L的有向线段； cout<<j<<‘ ‘<<l<<endl; } //······其他操作； return 0;}
一般情况下使用邻接表存储会降低使用空间大小和有效节约时间；但如果是比较稠密的图这两种方式就区别不大了；
2.图的遍历：
(1)DFS：
#include<iostream>#include<cstdio>#include<cstdlib>#define maxn 99999#define MAXN 0x7fffffff/3using namespace std;struct node{ int a,b,w,next;};node edge[maxn];//用邻接表存储边； int head[maxn],sum=1;//存储顶点，sum为下标； int m,n; //顶点个数和边的个数；bool visit[maxn]={false}; void push(int a,int b,int c){ edge[sum].a=a; edge[sum].b=b; edge[sum].w=c; edge[sum].next=head[a]; head[a]=sum++;}void Initialization(){ sum=1; for(int i=1;i<=m*n*2;++i) { head[i]=-1;//用-1作为标志表明链表的结束； edge[i].w=MAXN; visit[i]=false; }}void DFS(int sum){ visit[sum]=true; if(edge[sum].b!=0) cout<<"-->"<<edge[sum].b; for(int k=head[sum];k!=-1;k=edge[k].next)//调用顶点J相连的每一条边； if(!visit[edge[k].b]) DFS(edge[k].b);}int main(){ int i,j; cin>>m>>n; Initialization(); for(i=1;i<=n;++i) { int a,b,c; cin>>a>>b>>c; push(a,b,c);//有向边； } cin>>j; cout<<endl; cout<<j; DFS(j); //······其他操作； return 0;}
(2)BFS：
#include<iostream>#include<queue>#include<cstdio>#include<cstdlib>#define maxn 99999#define MAXN 0x7fffffff/3using namespace std;struct node{ int a,b,w,next;};node edge[maxn];//用邻接表存储边； int head[maxn],sum=1;//存储顶点，sum为下标； int m,n; //顶点个数和边的个数；bool visit[maxn]={false},vis[maxn]={false}; void push(int a,int b,int c){ edge[sum].a=a; edge[sum].b=b; edge[sum].w=c; edge[sum].next=head[a]; head[a]=sum++;}void Initialization(){ sum=1; for(int i=1;i<=m*n*2;++i) { head[i]=-1;//用-1作为标志表明链表的结束； edge[i].w=MAXN; visit[i]=vis[i]=false; }}void DFS(int sum){ visit[sum]=true; if(edge[sum].b!=0) cout<<"-->"<<edge[sum].b; for(int k=head[sum];k!=-1;k=edge[k].next)//调用顶点J相连的每一条边； if(!visit[edge[k].b]) DFS(edge[k].b);}void BFS(int sum){ queue<int>que; que.push(sum); vis[sum]=true; cout<<sum; while(!que.empty()) { int su=que.front(); que.pop(); for(int k=head[su];k!=-1;k=edge[k].next)//调用顶点J相连的每一条边； if(!vis[edge[k].b]) { que.push(edge[k].b); vis[edge[k].b]=true; cout<<"-->"<<edge[k].b; } }}int main(){ int i,j; cin>>m>>n; Initialization(); for(i=1;i<=n;++i) { int a,b,c; cin>>a>>b>>c; push(a,b,c);//有向边； } cin>>j; cout<<endl; cout<<j; DFS(j); cout<<endl<<"******************"<<endl; BFS(j); //······其他操作； return 0;}
一般来说这两者都有不小的缺点：DFS深度优先搜索会调用大量的栈空间，很容易爆栈；
而BFS内存耗费量大（需要开大量的数组单元用来存储状态）
总而言之，这两者都在时空上有很大的局限性；慎用！
3.求最短路径
(1)Flyoed:
#include <cstdio>#include <iostream>#define MAXN 99999999using namespace std;int dis[10][10],k,i,j,n,m;int main() { cin >> n >> m; for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(i==j) dis[i][j]=0; else dis[i][j]=MAXN; for(i=1; i<=m; i++) { int a,b,c; cin >> a >> b >> c ; dis[a][b]=c; } for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(dis[i][j]>dis[i][k]+dis[k][j] ) dis[i][j]=dis[i][k]+dis[k][j]; int start,end; cin >> start >> end ; cout << dis[start][end] <<endl; return 0;}
(2)Dijkstra:
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>const int MAXN = 1010;const int INF = 999999999;int n, k;int map[MAXN][MAXN];bool visit[MAXN];int pre[MAXN];int dist[MAXN];void init(){ memset(visit, false, sizeof(visit)); for (int i = 1; i <= n; ++i){ for (int j = 1; j <= n; ++j) map[i][j] = INF; pre[i] = i; dist[i] = INF; }}void Dijkstra(const int v){ int i, j; int minValue, minNode; dist[1] = 0; visit[1] = true; for (i = 2; i <= n; ++i){ if (map[1][i] != INF){ dist[i] = map[1][i]; pre[i] = 1; } } for (i = 1; i <= n; ++i) { minValue = INF; minNode = 0; for (j = 1; j <= n; ++j){ if (!visit[j] && minValue > dist[j]){ minNode = j; minValue = dist[j]; } } if (minNode == 0) break; visit[minNode] = true; for (j = 1; j <= n; ++j) { if (!visit[j] && map[minNode][j] != INF && dist[j] > dist[minNode] + map[minNode][j]) { dist[j] = dist[minNode] + map[minNode][j]; pre[j] = minNode; } } if (minNode == v) break; }}
(3)SPFA:
long long SPFA(int st) { for(int i=1;i<=n;i++) sp[i]=inf; sp[1]=0; queue<int> q; q.push(st); while(!q.empty()) { int kai=q.front();q.pop(); for(int i=H[kai];i!=-1;i=E[i].next) { if(sp[E[i].v]>E[i].count+sp[kai]){ sp[E[i].v]=E[i].count+sp[kai]; q.push(E[i].v); } } } long long ans=0; for(int i=1;i<=n;i++) ans+=sp[i]; return ans; } void spfa(int s,int dis[]) { int i,pre[N]; bool used[N]; queue<int> q; memset(used,0,sizeof(used)); memset(pre,-1,sizeof(pre)); for(i=0; i<N; i++) dis[i]=inf; dis[s]=0; used[s]=true; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); used[u]=false; for(i=0; i<map[u].size(); i++) { Node p=map[u][i]; if(dis[p.v]>dis[u]+p.len) { dis[p.v]=dis[u]+p.len; pre[p.v]=u; if(!used[p.v]) { used[p.v]=true; q.push(p.v); } } } } }
三者的时间复杂度依次为：O(n^3),O(n^2),O(KE),其中E是边数，K是常数，平均值为2，图越稠密，K越大；
其中F·····和D·······算法比较的稳定，可是很慢啊，SPFA一般情况下比较快，可是一但图很稠密，就退化到N^2的复杂度；
但还是SPFA用的最多，也最好用，建议做最短路径的题用SPFA；
图论算法大集锦
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。