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

软件设计

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 }

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

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

单源最短路径输出

主要思想

主要利用递归的思想，一层一层的进行迭代

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即为最小生成树的总权值之和。

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

图论算法