图_图的存储_添加边_图的遍历_DFS_树的重心_BFS_图中点的层次

图

树是特殊的图（无环连通图）

• 有向图（a -> b）

• 无向图（a -> b, b -> a）

有向图的存储

• 邻接矩阵（适合稠密图）

• 邻接表（n个单链表）

添加

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
1
2
3
4
5
6

遍历

1.DFS

void dfs(int u)
{
    st[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int t = e[i];
        if(!st[t]) dfs(t);
    }
}
1
2
3
4
5
6
7
8
9

例题：树的重心

删除4号节点，构成了三个子连通块，其中最大连通块的点数为5。

题目分析

• 重心：删除节点1后最大连通块的点数为4，与删除其他节点相比该最大值最小，1为重心

• 遍历每个点，求出删除每个点后最大连通块的点数。

• 求所有最大连通块点数中的最小值

使用DFS遍历

在DFS回溯过程中可以求出子树的点数，以便比较该树中最大连通块的点数

ans：存答案（所有连通块的最大点数中的最小值）

res：存放删除该点以后连通块中点数的最大值

ans = min(res, ans)

#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010, M = N*2;
int n;
int h[M],e[M],ne[M],idx;
bool st[N];
int ans = N;    //答案 => 最大连通块的最小值

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

//返回以u为根的子树中点的数量
int dfs(int u)
{
    st[u] = true;

    int sum = 1;    //子树大小
    int res = 0;    //删除该点以后所有连通块的点数的最大值
    //遍历树
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int t = e[i];   //在树中的序号
        if(!st[t])
        {
            int s = dfs(t);     //s记录当前子树的大小
            res = max(res, s);
            sum += s;   //把当前子树大小加入以u为根节点的树
        }
    }

    res = max(res, n - sum);        //还有一部分连通块为上面树
    ans = min(ans, res);

    return sum;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 0; i < n-1; i++)
    {
        int a,b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63

2.BFS

例题：图中点的层次

根据所有边的长度都是1，可用BFS求最短路，第一次遍历到的点即可为最短。

d[N]：存出该点到起点的距离，同时初始化为-1，可用其来判断是否为第一次遍历。

queue <= 1
while(queue 不空)
{
    t <= 队头
    队头出队
    拓展t的所有邻点x
        if(x未被遍历)
        {
            queue <= x
            d[x] = d[t] + 1
        }
}
1
2
3
4
5
6
7
8
9
10
11
12

#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;
int e[N],ne[N],h[N],idx;
int d[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void bfs(int u)
{
    memset(d, -1, sizeof d);
    
    queue<int> q;
    q.push(u);
    d[1] = 0;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j  = e[i];
            if(d[j] == -1)
            {
                q.push(j);
                d[j] = d[t] + 1;
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    
    int n,m;
    cin >> n >> m;
    int a,b;
    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        add(a, b);
    }
    
    bfs(1);
    
    cout << d[n] << endl;
    
    return 0;
}
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
51
52
53
54
55
56
57
58
59
60
61
62