图论算法模板整理及思路 不断更新 绝对精品
软件设计 2017-04-17
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 } DFSBFS
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 } BFSFlyoed
思路：三层循环遍历中间节点
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 } FlyoedDijkstra
主要思想：每次找到一个能到达的最近的点，来更新到达其他点的距离
思路：
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 else
31 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 else
83 print(1,i);
84 cout<<endl;
85 }
86
87 return 0;
88 } DijkstraSPFA
主要思想：初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时结束
思路：需要变量：
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 do
19 {
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 } SPFA邻接矩阵存储1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 const int MAXN=30001;
7 const int maxn=0x7fffffff;
8 struct node
9 {
10 int u;
11 int v;
12 int w;
13 int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 int n,m,begin,end;
18 int dis[MAXN];
19 int vis[MAXN];
20 void spfa()
21 {
22 for(int i=1;i<=n;i++)dis[i]=maxn;
23 queue<int>q;
24 vis[begin]=1;
25 q.push(begin);
26 dis[begin]=0;
27 while(q.size()!=0)
28 {
29 int p=q.front();
30 q.pop();
31 vis[p]=0;
32 for(int i=head[p];i!=-1;i=edge[i].next)
33 {
34 if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn)
35 {
36 dis[edge[i].v]=dis[p]+edge[i].w;
37 if(vis[edge[i].v]==0)
38 {
39 q.push(edge[i].v);
40 vis[edge[i].v]=1;
41 }
42 }
43 }
44 }
45 printf("%d",dis[end]);
46 }
47 int main()
48 {
49 scanf("%d%d%d%d",&n,&m,&begin,&end);
50 for(int i=1;i<=n;i++)head[i]=-1;
51 for(int i=1;i<=m;i++)
52 {
53 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
54 edge[num].next=head[edge[num].u];
55 head[edge[num].u]=num++;
56 edge[num].w=edge[num-1].w;
57 edge[num].u=edge[num-1].v;
58 edge[num].v=edge[num-1].u;
59 edge[num].next=head[edge[num].u];
60 head[edge[num].u]=num++;
61 }
62 spfa();
63 return 0;
64 } SPFA邻接表存储单源最短路径输出
主要思想
主要利用递归的思想，一层一层的进行迭代
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 } TarjanKruskal算法
主要思想：
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 } KruskalKruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。
相关推荐
earthhouge 0喜欢 / 0评论 2020-07-19
lixiaotao 0喜欢 / 0评论 2020-02-16
Happyunlimited 0喜欢 / 0评论 2019-11-01
ResysChina 0喜欢 / 0评论 2018-04-22
ResysChina 0喜欢 / 0评论 2018-04-14
MATLAB 0喜欢 / 0评论 2018-04-12
锦妖和她的小伙伴们 0喜欢 / 0评论 2018-02-21
锦妖和她的小伙伴们 0喜欢 / 0评论 2018-02-21