dfs+树与图的遍历(深度，重心)
邻接表存图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include <iostream>
using namespace std;
const int maxn = 1e6;
int ver[maxn],next[maxn],head[maxn],edge[maxn];
int tot = 0;
// 存图
void add(int u,int v,int w) {
ver[++tot] = v;
edge[tot] = w;
next[tot] = head[u];
head[u] = tot;//head数组下标为0
}
int main() {
freopen("a.txt","r",stdin);
int n,m;
cin >> n >> m;
for (int i=1; i<=m; i++) {
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
}
for (int i=head[1]; i ; i = next[i]) {
i = next[i];
}
return 0;
}邻接表存图跑dfs,顺带求出dfs序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <bits/stdc++.h>
using namespace std;
//数组模拟邻接表
const int maxn = 1e6;
int ver[maxn],next[maxn],edge[maxn],head[maxn];
int vis[maxn];
int tot = 0;// tot代表的是边的编号
void add(int a,int b,int w) {
ver[++tot] = b; // 边tot的终点
edge[tot] = w;
next[tot] = head[a];//原来顶点a的第一条边的编号现在成了tot边的下一条边的编号
head[a] = tot;
}
vector<int> ans;
//邻接表的dfs函数
void dfs(int x) {
ans.push_back(x);
vis[x] = 1;
// printf("点遍历的顺序:%d \n",x);
for (int i=head[x]; i; i=next[i]) {
int y = ver[i];
if ( vis[y] ) continue;
dfs(y);
}
ans.push_back(x);
}
int main() {
freopen("a.txt","r",stdin);
int n,m;
cin >> n >> m;
for (int i=1; i<=m; i++) {
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
}
//遍历从点x出发的所有的点
dfs(1);
reverse(ans.begin(),ans.end());
for (int i=0; i<ans.size(); i++) {
printf("%d ",ans[i]);
}
return 0;
}3 . 树的深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;
//数组模拟邻接表
const int maxn = 1e6;
int ver[maxn],next[maxn],edge[maxn],head[maxn];
int vis[maxn];
int tot = 0;// tot代表的是边的编号
void add(int a,int b,int w) {
ver[++tot] = b; // 边tot的终点
edge[tot] = w;
next[tot] = head[a];//原来顶点a的第一条边的编号现在成了tot边的下一条边的编号
head[a] = tot;
}
int deep = 0;
//邻接表的dfs函数
void dfs(int x,int step) {
if(step > deep) deep = step;
vis[x] = 1;
// printf("点遍历的顺序:%d \n",x);
for (int i=head[x]; i; i=next[i]) {
int y = ver[i];
if ( vis[y] ) continue;
dfs(y,step+1);
}
}
int main() {
freopen("a.txt","r",stdin);
int n,m;
cin >> n >> m;
for (int i=1; i<=m; i++) {
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
}
//遍历从点x出发的所有的点
dfs(1,0);
printf("%d\n",deep);
return 0;
}树的重心
- 定义：删除每一个节点后，分成不同子树，删除节点x得到最大的一颗子树的大小比删除其他节点得到的最大子树都小，则该节点为树的重心,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <iostream>
using namespace std;
const int maxn = 1e6;
int ver[maxn],next[maxn],head[maxn],edge[maxn];
int tot = 0;
bool vis[maxn];
int size[maxn];
void add(int u,int v,int w) {
ver[++tot] = v;
edge[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
int max_part = 0;
int dfs(int x) {
// printf("u=%d ",x);
size[x] = 1;
vis[x] = 1;
for (int i=head[x]; i ; i=next[i]) {
int v = ver[i];
if ( vis[v] ) continue;
dfs(v);
size[x] += size[v];
max_part = max( max_part,size[v] );
}
return max_part;
}
int main() {
freopen("a.txt","r",stdin);
int n,m;
cin >> n >> m;
for (int i=1; i<=m; i++) {
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
// add(v,u,w); //存的是无向图,
}
int pos=0,ans=0x7fffffff;
for (int i=1; i<=n; i++) {
int t = dfs(i);
if ( t < ans ) {
pos = i;
ans = t;
}
}
printf("pos=%d ans=%d\n",pos,ans);
return 0;
}
- 求图的联通块的数量，应该存无向图，然后dfs没有被标记的点,dfs几次就有几个联通块分量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <iostream>
using namespace std;
const int maxn = 1e6;
int ver[maxn],next[maxn],head[maxn],edge[maxn];
int tot = 0;
bool vis[maxn];
int size[maxn];
void add(int u,int v,int w) {
ver[++tot] = v;
edge[tot] = w;
next[tot] = head[u];
head[u] = tot;
}
int dfs(int x) {
vis[x] = 1;
for (int i=head[x]; i ; i=next[i]) {
int v = ver[i];
if ( vis[v] ) continue;
dfs(v);
}
return 0;
}
int main() {
freopen("a.txt","r",stdin);
int n,m;
cin >> n >> m;
for (int i=1; i<=m; i++) {
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
add(v,u,w); //存的是无向图,
}
int cnt = 0;
for (int i=1; i<=n; i++) {
if (!vis[i]) {
dfs(i);
cnt++;
}
}
cout << cnt << endl;
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！