图论算法模板整理及思路 不断更新 绝对精品
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 }1 for (k = 1; k <= n; k++)
2 for (i = 1; i <= n; i++)
3 for (j = 1; j <= n; j++)
4 dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);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 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 }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 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 } 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 }http://codevs.cn/problem/1269/
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 const int MAXN=100001;
7 const int maxn=0xfffffff;
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;
18 int dis[MAXN];
19 int vis[MAXN];// 是否在队列中
20 int tot=0;
21 int pre[MAXN];// 记录次短路
22 void spfa()
23 {
24 dis[1]=0;
25 vis[1]=1;
26 queue<int>q;
27 q.push(1);
28 while(q.size()!=0)
29 {
30 int p=q.front();
31 q.pop();
32 vis[p]=0;
33 for(int i=head[p];i!=-1;i=edge[i].next)
34 {
35 int to=edge[i].v;
36 if(dis[to]>dis[p]+edge[i].w)
37 {
38 pre[to]=dis[to];// 记录下更新之前的长度 即次长
39 dis[to]=dis[p]+edge[i].w;
40 //if(edge[i].v==n)tot++;
41 if(vis[to]==0)
42 {
43 q.push(to);
44 vis[to]=1;
45 }
46 }
47 else if(dis[to]!=dis[p]+edge[i].w&&pre[to]>dis[p]+edge[i].w)
48 {
49 pre[to]=dis[p]+edge[i].w;// 根据条件，此时需要更新，否则就不是次短路
50 if(vis[to]==0)
51 {
52 q.push(to);
53 vis[to]=1;
54 }
55 }
56 if(pre[to]>pre[p]+edge[i].w)// 同理，需要更新
57 {
58 pre[to]=pre[p]+edge[i].w;
59 if(vis[to]==0)
60 {
61 q.push(to);
62 vis[to]=1;
63 }
64 }
65 }
66 }
67 }
68 int main()
69 {
70 scanf("%d%d",&n,&m);
71 for(int i=1;i<=n;i++)
72 {
73 head[i]=-1;
74 dis[i]=maxn;
75 pre[i]=maxn;
76 }
77 for(int i=1;i<=m;i++)
78 {
79 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
80 edge[num].next=head[edge[num].u];
81 head[edge[num].u]=num++;
82 }
83 spfa();
84 if(pre[n]!=maxn)
85 printf("%d",pre[n]);
86 else
87 {
88 printf("-1");
89 }
90 return 0;
91 }单源最短路径输出
主要思想
主要利用递归的思想，一层一层的进行迭代
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即为最小生成树的总权值之和。
http://codevs.cn/problem/3315/ 3315 时空跳跃者的魔法
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 const int MAXN=1000001;
8 const int maxn=0x7fffffff;
9 int x[MAXN];
10 int y[MAXN];
11 int z[MAXN];
12 int tas[MAXN];
13 struct node
14 {
15 int u;
16 int v;
17 double w;
18 int next;
19 }edge[MAXN];
20 int num=1;
21 int head[MAXN];
22 int f[MAXN];
23 int comp(const node & a, const node & b)
24 {
25 if(a.w<b.w)
26 return 1;
27 return 0;
28 }
29 int find(int x)
30 {
31 if(f[x]!=x)
32 f[x]=find(f[x]);
33 return f[x];
34 }
35 void unionn(int x,int y)
36 {
37 int fx=find(x);
38 int fy=find(y);
39 f[fx]=fy;
40 }
41 int main()
42 {
43 int n;
44 scanf("%d",&n);
45 for(int i=1;i<=n;i++)
46 {
47 scanf("%d%d%d%d",&x[i],&y[i],&z[i],&tas[i]);
48 f[i]=i;
49 }
50 for(int i=1;i<=n;i++)
51 {
52 for(int j=1;j<=n;j++)
53 {
54 edge[num].u=i;
55 edge[num].v=j;
56 edge[num].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))+abs(tas[i]-tas[j]);
57 edge[num].next=head[i];
58 head[i]=num++;
59 }
60 }
61 sort(edge+1,edge+num,comp);
62 int k=0;
63 double tot=0;
64 for(int i=1;i<=num;i++)
65 {
66 if(find(edge[i].u)!=find(edge[i].v))
67 {
68 unionn(edge[i].u,edge[i].v);
69 tot=tot+edge[i].w;
70 tot=floor(tot);
71 k++;
72 }
73 if(k==n-1)break;
74 }
75 char sr[101];
76 scanf("%s",sr);
77 double p=atof(sr);
78 if(tot>p)
79 {
80 printf("Death");
81 }
82 else
83 {
84 printf("%.0lfTas",tot);
85 }
86 return 0;
87 }拓扑排序
算法实现：
a) 数据结构：indgr[i]: 顶点i的入度;
stack[ ]: 栈
b) 初始化:top=0 (栈顶指针置零)
c) 将初始状态所有入度为0的顶点压栈
d) I=0 (计数器)
e) while 栈非空(top>0)
i. 栈顶的顶点v出栈；top-1; 输出v；i++；
ii. for v的每一个后继顶点u
1. indgr[u]--; u的入度减1
2. if （u的入度变为0） 顶点u入栈
f) 算法结束
http://codevs.cn/problem/2833/2833 奇怪的梦境
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<stack>
6 using namespace std;
7 const int MAXN=30001;
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 rudu[MAXN];
18 int tot=0;
19 int n,m;
20 stack<int>s;
21 void topsort()
22 {
23 for(int i=1;i<=n;i++)
24 {
25 if(rudu[i]==0)
26 {
27 s.push(i);
28 tot++;
29 }
30 }
31 while(s.size()!=0)
32 {
33 int p=s.top();
34 s.pop();
35 for(int i=head[p];i!=-1;i=edge[i].next)
36 {
37 rudu[edge[i].v]--;
38 if(rudu[edge[i].v]==0)
39 {
40 s.push(edge[i].v);
41 tot++;
42 }
43 }
44 }
45 if(tot==n)printf("o(∩_∩)o");
46 else
47 {
48 printf("T_T\n%d",n-tot);
49 //printf("%d",tot);
50 }
51 }
52 int main()
53 {
54
55 scanf("%d%d",&n,&m);
56 for(int i=1;i<=n;i++)head[i]=-1;
57 for(int i=1;i<=m;i++)
58 {
59 scanf("%d%d",&edge[num].u,&edge[num].v);
60 edge[num].next=head[edge[num].u];
61 rudu[edge[num].v]++;
62 head[edge[num].u]=num++;
63 }
64 topsort();
65 return 0;
66 }Kosaraju算法（强联通分量）
http://www.cnblogs.com/zwfymqz/p/6693881.html
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读