首页 > 代码库 > 图论算法模板整理及思路 不断更新 绝对精品
图论算法模板整理及思路 不断更新 绝对精品
DFS
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 queue<int>q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p)10 {11 q.push(p);12 vis[p]=1;13 printf("%c-->",char(q.front()+64));14 while(q.size()!=0)15 { 16 int k=q.front();17 q.pop();18 for(int i=1;i<=n;i++)19 {20 21 if(vis[i]==0&&map[k][i]==1)22 {23 printf("%c-->",char(i+64));24 //q.pop();25 q.push(i);26 vis[i]=1;27 }28 }29 }30 }31 int main()32 {33 34 scanf("%d%d",&n,&m);35 for(int i=1;i<=m;i++)36 {37 char x,y;38 //scanf("\n%d %d",&x,&y);39 cin>>x>>y;40 x=x-64;41 y=y-64;42 map[x][y]=map[y][x]=1;43 }44 bfs(1);45 return 0;46 }
BFS
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 queue<int>q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p)10 {11 q.push(p);12 vis[p]=1;13 printf("%c-->",char(q.front()+64));14 while(q.size()!=0)15 { 16 int k=q.front();17 q.pop();18 for(int i=1;i<=n;i++)19 {20 21 if(vis[i]==0&&map[k][i]==1)22 {23 printf("%c-->",char(i+64));24 //q.pop();25 q.push(i);26 vis[i]=1;27 }28 }29 }30 }31 int main()32 {33 34 scanf("%d%d",&n,&m);35 for(int i=1;i<=m;i++)36 {37 char x,y;38 //scanf("\n%d %d",&x,&y);39 cin>>x>>y;40 x=x-64;41 y=y-64;42 map[x][y]=map[y][x]=1;43 }44 bfs(1);45 return 0;46 }
Flyoed
思路：三层循环遍历中间节点
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int a[101][101]; 6 int pass[101][101]; 7 int main() 8 { 9 memset(a,999999,sizeof(a));10 int n,m;11 scanf("%d%d",&n,&m);12 for(int i=1;i<=m;i++)13 {14 int x,y,zhi;15 scanf("%d%d%d",&x,&y,&zhi);16 a[x][y]=zhi;17 a[y][x]=zhi;18 }19 for(int k=1;k<=n;k++)20 {21 for(int i=1;i<=n;i++)22 {23 for(int j=1;j<=n;j++)24 {25 if(a[i][j]>a[i][k]+a[k][j])26 {27 a[i][j]=a[i][k]+a[k][j];28 pass[i][j]=k;29 }30 }31 }32 }33 printf("%d %d\n",a[1][4],a[2][6]);34 printf("%d %d\n",pass[1][4],pass[2][6]);35 return 0;36 }
Dijkstra
主要思想：每次找到一个能到达的最近的点，来更新到达其他点的距离
思路：
1.需要一个dis数组记录需要求的点到其他点的最短路径 pre数组记录前驱
2.（1）初始化:dis[]=∞ dis[开始的点]=0 pre[开始的点]=0
（2）<1>for(int i=1;i<=顶点总数;i++)
找到dis[i]最小的点
vis[找到的点]=1
for(与找到的点相连的点)
if(dis[find]+w[find][i]<dis[i])
{
1.松弛
2.pre[i]=find 记录前驱
}
end
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int a[101][101]; 6 int dis[101]; 7 int maxn=0x7f; 8 int vis[1001]; 9 int pass[1001];10 void print(int bg,int ed)11 {12 int ans[101];13 int now=1;14 ans[now]=ed;15 now++;16 // ans[now]=ed;17 //now++;18 int tmp=pass[ed];19 while(tmp!=bg)20 {21 ans[now]=tmp;22 now++;23 tmp=pass[tmp];24 }25 ans[now]=bg;26 for(int i=now;i>=1;i--)27 {28 if(i!=1)29 printf("%d-->",ans[i]);30 else31 printf("%d",ans[i]);32 }33 }34 int main()35 {36 memset(a,maxn,sizeof(a));37 int n,m;38 int beginn=1;39 scanf("%d%d",&n,&m);40 for(int i=1;i<=m;i++)41 {42 int x,y,zhi;43 scanf("%d%d%d",&x,&y,&zhi);44 a[x][y]=zhi;45 a[y][x]=zhi;46 }47 48 for(int i=1;i<=n;i++)49 {50 if(a[beginn][i]!=maxn)51 {52 dis[i]=a[beginn][i];53 }54 }55 dis[beginn]=0;56 for(int i=1;i<=n;i++)57 {58 int minn=maxn;59 int k=-1;60 for(int j=1;j<=n;j++)61 {62 if(dis[j]<=minn&&vis[j]==0)63 {64 minn=dis[j];65 k=j;66 }67 }68 vis[k]=1;69 for(int j=1;j<=n;j++)70 {71 if(dis[k]+a[k][j]<=dis[j])72 {73 dis[j]=dis[k]+a[k][j];74 pass[j]=k;75 }76 }77 }78 for(int i=1;i<=n;i++)79 {80 cout<<dis[i]<<" ";81 if(i==1)cout<<i;82 else83 print(1,i);84 cout<<endl;85 }86 87 return 0;88 }
SPFA
主要思想：初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时结束
思路：需要变量：
1.需要一个dis数组记录需要求的点到其他点的最短路径
2.pre数组记录前驱
3.queue队列
4.vis数组 记录该点是否在队列中
begin
1.初始化:dis[]=∞ dis[开始的点]=0 pre[开始的点]=0
2.while(队列不为空)
（1）取出顶点 vis[顶点]=false
（2）for(与顶点相连的点)
if(dis[find]+w[find][i]<dis[i])
{
1.松弛
if(i不在队列中)
{
加入队列
vis[i]=true;
}
}
end;
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int map[101][101]; 7 int dis[101]; 8 bool vis[101]; 9 queue<int>q;10 int n,m;11 int bg=1;12 void spfa()13 {14 dis[bg]=0;15 vis[bg]=1;16 q.push(bg);17 dis[bg]=0;18 do19 {20 int k=q.front(); 21 for(int j=1;j<=n;j++)22 {23 if(dis[j]>dis[k]+map[k][j])24 {25 dis[j]=dis[k]+map[k][j];26 if(vis[j]==0)27 {28 q.push(j);29 vis[j]=1;30 }31 }32 }33 q.pop();34 vis[k]=0;35 }while(q.size()!=0);36 for(int i=1;i<=n;i++)37 cout<<dis[i]<<endl;38 }39 int main()40 {41 memset(map,0x7f,sizeof(map));42 memset(dis,0x7f,sizeof(dis));43 memset(vis,0,sizeof(vis));44 scanf("%d%d",&n,&m);45 for(int i=1;i<=m;i++)46 {47 int x,y,z;48 scanf("%d%d%d",&x,&y,&z);49 map[x][y]=map[y][x]=z;50 }51 //int a,b;52 //scanf("%d%d",&a,&b);53 spfa();54 return 0;55 }
单源最短路径输出
主要思想
主要利用递归的思想，一层一层的进行迭代
1 void print(int x)2 {3 if(pre[a][x]==0)return;4 print(pre[a][x]);5 cout<<"->"<<x;6 }7 //a为开始的点
Tarjan算法
思路：
基本思路：
1.初始化
2.入栈
3.枚举：
1.不在队列中->访问，进行赋值，
2.在队列中->赋值
4.寻找根->输出结果
1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 struct node { 6 int v,next; 7 } edge[1001]; 8 int DFN[1001],LOW[1001]; 9 int stack[1001],heads[1001],visit[1001],cnt,tot,index;10 void add(int x,int y) {11 edge[++cnt].next=heads[x];12 edge[cnt].v = y;13 heads[x]=cnt;14 return ;15 }16 void tarjan(int x) { //代表第几个点在处理。递归的是点。17 DFN[x]=LOW[x]=++tot;// 新进点的初始化。18 stack[++index]=x;//进站19 visit[x]=1;//表示在栈里20 for(int i=heads[x]; i!=-1; i=edge[i].next) {21 if(!DFN[edge[i].v]) {22 //如果没访问过23 tarjan(edge[i].v);//往下进行延伸，开始递归24 LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。25 } else if(visit[edge[i].v ]) {26 //如果访问过，并且还在栈里。27 LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系28 }29 }30 if(LOW[x]==DFN[x]) { //发现是整个强连通分量子树里的最小根。31 do {32 printf("%d ",stack[index]);33 visit[stack[index]]=0;34 index--;35 } while(x!=stack[index+1]);//出栈，并且输出。36 printf("\n");37 }38 return ;39 }40 int main() {41 memset(heads,-1,sizeof(heads));42 int n,m;43 scanf("%d%d",&n,&m);44 int x,y;45 for(int i=1; i<=m; i++) {46 scanf("%d%d",&x,&y);47 add(x,y);48 }49 for(int i=1; i<=n; i++)50 if(!DFN[i]) tarjan(1);//当这个点没有访问过，就从此点开始。防止图没走完51 return 0;52 }
Kruskal算法
主要思想：
Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。
思路：
算法描述:
1.初始化并查集。father[x]=x。
2.tot=0
3.将所有边用快排从小到大排序。sort
4.计数器 k=0;
5.for (i=1; i<=M; i++) //循环所有已从小到大排序的边
if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)，
begin
①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。
②tot=tot+W(u,v)
③k++
④如果k=n-1,说明最小生成树已经生成，则break;
end;
6. 结束，tot即为最小生成树的总权值之和。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int map[101][101]; 6 int nmap[101][101]; 7 int pass[101]; 8 int vis[101]; 9 int now=1;10 int n,m;11 int num=0;12 void dfs(int p)13 {14 vis[p]=1;15 for(int i=1;i<=n;i++)16 {17 if(vis[i]==0&&map[p][i]==1)18 {19 dfs(i);20 21 }22 }23 pass[now]=p;24 now++;25 }26 void ndfs(int p)27 {28 vis[p]=0;29 for(int i=1;i<=n;i++)30 {31 if(vis[i]==1&&nmap[p][i]==1)32 ndfs(i);33 }34 }35 int main()36 {37 38 scanf("%d%d",&n,&m);39 for(int i=1;i<=m;i++)40 {41 int x,y;42 scanf("%d%d",&x,&y);43 map[x][y]=1;44 nmap[y][x]=1;45 }46 for(int i=1;i<=n;i++)47 {48 if(vis[i]==0)49 dfs(i);50 }51 pass[now]=1;52 for(int i=n;i>=1;i--)53 {54 if(vis[pass[i]]==1)55 {56 ndfs(pass[i]);57 num++;58 }59 }60 cout<<num;61 return 0;62 }
Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。
图论算法模板整理及思路 不断更新 绝对精品
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。