Graph Theory Algorithms Template Arrangement and Thoughts Continuously Update Absolute Quality
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
Idea: Three-tier cyclic traversal of intermediate nodes
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
Main Idea: Find the nearest point at a time to update the distance to other points.
Ideas:
1. A dis array record pre cursor is needed to record the shortest path from the required point to the other point.
2. (1) Initialization: dis []= dis [starting point] = 0 pre [starting point] = 0
(2) < 1 > for (int i = 1; i < = total number of vertices; i +)
Find the smallest point of dis[i]
vis [Location] = 1
For (points connected to the points found)
if(dis[find]+w[find][i]<dis[i])
{
1. Relaxation
2.pre[i]=find record precursor
}
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
Main idea: Initially join the starting point in the queue. Each time an element is extracted from the queue, and all the points adjacent to it are modified. If a point adjacent to it is modified successfully, it will join the queue. Until the queue ends in empty time
Thought: Variables are needed:
1. A dis array is needed to record the shortest path from the required point to the other point.
2.pre array record precursor
Queue queue
4.vis array records whether the point is in the queue
begin
Initialization: dis []= dis [starting point] = 0 pre [starting point] = 0
2. While (the queue is not empty)
(1) Take out the vertex vis [vertex] = false
(2) For (points connected to vertices)
if(dis[find]+w[find][i]<dis[i])
{
1. Relaxation
if(i is not in the queue)
{
Join the queue
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
Single source shortest path output
Main Ideas
Major use of recursive thinking, layer by layer for iteration
1 void print(int x)
2 {
3 if(pre[a][x]==0)return;
4 print(pre[a][x]);
5 cout<<"->"<<x;
6 }
7 //a For the starting point
Single Source Shortest Circuit Output
Tarjan algorithm
Ideas:
Basic ideas:
1. Initialization
2. Stacking
3. Enumeration:
1. Not in the queue - > access, assign value.
2. In the queue - > assignment
4. Finding Roots - > Output Results
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) { //Represents the number of points being dealt with. The recursive point.
17 DFN[x]=LOW[x]=++tot;// Initialization of new entry points.
18 stack[++index]=x;//Arrival
19 visit[x]=1;//Represents in the stack
20 for(int i=heads[x]; i!=-1; i=edge[i].next) {
21 if(!DFN[edge[i].v]) {
22 //If you haven't visited
23 tarjan(edge[i].v);//Stretch down and start recursion
24 LOW[x]=min(LOW[x],LOW[edge[i].v]);//Recursively, compare who is whose son／Father is the corresponding relationship of trees, which involves the minimum root of strongly connected component subtrees.
25 } else if(visit[edge[i].v ]) {
26 //If visited, and still in the stack.
27 LOW[x]=min(LOW[x],DFN[edge[i].v]);//Compare who is whose son／Father. It's the link correspondence.
28 }
29 }
30 if(LOW[x]==DFN[x]) { //Discovery is the smallest root in the whole strongly connected component subtree.
31 do {
32 printf("%d ",stack[index]);
33 visit[stack[index]]=0;
34 index--;
35 } while(x!=stack[index+1]);//Out of the stack, and output.
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);//When this point has not been visited, start at this point. Prevent the map from not running out
51 return 0;
52 }
Tarjan
Kruskal algorithm
Main ideas:
Kruskal algorithm regards a connected block as a set. Kruskal first ranks all the edges in order from small to large (usually using fast row), and considers that each point is isolated and belongs to n independent sets. Then enumerate each edge in order. If the edge is connected to two different sets, then the edge is added to the minimum spanning tree, and the two different sets are merged into one set; if the two points connected by the edge belong to the same set, they are skipped. Until n-1 edges are selected.
Ideas:
Algorithmic description:
1. Initialization and collection. father[x]=x.
2.tot=0
3. sort all edges from small to large in fast rows. sort
4. Counter k=0;
5. For (i = 1; I < = M; i++) // Loop all edges that have been sorted from small to large
if this is a u,v that does not belong to the same set of edges (u,v) (because it has been sorted, it must be the smallest).
begin
(1) Merging the set of u and V is equivalent to adding edges (u,v) to the minimum spanning tree.
②tot=tot+W(u,v)
③k++
(4) If k=n-1 indicates that the minimum spanning tree has been generated, then break;
end;
6. At the end, tot is the sum of the total weights of the smallest spanning tree.
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
Kruskal algorithm regards a connected block as a set. Kruskal first ranks all the edges in order from small to large (usually using fast row), and considers that each point is isolated and belongs to n independent sets. Then enumerate each edge in order. If the edge is connected to two different sets, then the edge is added to the minimum spanning tree, and the two different sets are merged into one set; if the two points connected by the edge belong to the same set, they are skipped. Until n-1 edges are selected.
Keywords:
C++
Added by brem13 on Tue, 09 Jul 2019 02:58:45 +0300