首页 > > 程序设计 > C/C++ >

图论算法模板整理及思路不断更新绝对精品

2018-06-17 22:47:54来源：未知阅读 ()

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 }

DFS

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 }

BFS

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 }

Flyoed

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]);

Flyod求图的连通性

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 }

Dijkstra

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 }

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邻接表存储

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 }

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 }

Tarjan

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 }

Kruskal

拓扑排序

算法实现：

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 }