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

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

新老客户大回馈,云服务器低至5折

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 }
拓扑排序

 

 Kosaraju算法(强联通分量)

http://www.cnblogs.com/zwfymqz/p/6693881.html

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:bzoj2982 -- Lucas定理

下一篇:bzoj2653 -- 二分+主席树