树和图的dfs和bfs

void dfs(int u)
{
    //标记一下u节点 
    st[u] = true;
    //访问u的每个子节点 
    for( int i = h[u]; i != -1; i = ne[i] ){
        int j = e[i];
        //如果j没有被搜过，一条道走到黑 
        if(!st[j])
            dfs(j);
    }
}

dfs返回以u为根的子树中的点的数量
算法核心：u点子树中点的数量和非子树连通块的点的数量最大值
设u点为重心 
    返回当前节点的一个子树的点的数量
    当前节点所有点数量求和
    记录子树点的最大值
和非子树连通块求最大值
记录最大值的最小值

 1 #include
 2 
 3 using namespace std;
 4 
 5 const int N = 1e5+10;
 6 const int M = 2*N;
 7 
 8 int n, m, idx;
 9 int h[N], e[M], ne[M];
10 
11 int ans = N;
12 
13 bool st[N];
14 
15 void add(int a, int b)
16 {
17     e[idx] = b;
18     ne[idx] = h[a];
19     h[a] = idx++;
20 }
21 
22 int dfs(int u)
23 {
24     int res = 0;
25     st[u] = true;
26     int sum = 1;
27     for( int i = h[u]; i != -1; i = ne[i] ){
28         int j = e[i];
29         if(!st[j]){
30             int s = dfs(j);
31             sum+=s;
32             res = max(res, s);
33         }
34     }
35     res = max(res, n-sum);
36     ans = min(ans, res);
37     
38     return sum;
39 }
40 
41 int main()
42 {
43     memset(h, -1, sizeof h);
44     cin>>n;
45     for( int i = 0; i < n-1; i++ ){
46         int a, b;
47         cin>>a>>b;
48         add(a, b);
49         add(b, a);
50     }
51     dfs(1);
52     cout<endl;
53     
54     return 0;
55 }

bfs()
{
    初始化队列
    d[1] = 0;
    while(队列非空){
        t = 队头;
        for(t的每一个临边){
            j-<临边;
            if(j未被拓展过){
                d[j] = d[t]+1;//d[j]存储起点到j点的距离 
                q.push(j);//将j加入队列 
            } 
        } 
    }
}

 1 #include
 2 
 3 using namespace std;
 4 
 5 const int N = 1e5+10;
 6 
 7 int h[N], e[N], ne[N], idx;
 8 int d[N];
 9 int n, m;
10 
11 void add(int a, int b)
12 {
13     e[idx] = b;
14     ne[idx] = h[a];
15     h[a] = idx++;
16 }
17 
18 int bfs()
19 {
20     queue<int> q;
21     q.push(1);
22     memset(d, -1, sizeof d);
23     d[1] = 0;
24     while(!q.empty()){
25         int t = q.front();
26         q.pop();
27         for( int i = h[t]; i != -1; i = ne[i] ){
28             int j = e[i];
29             if(d[j]==-1){
30                 d[j] = d[t]+1;
31                 q.push(j);
32             }
33         }
34     }
35     return d[n];
36 }
37 
38 int main()
39 {
40     cin>>n>>m;
41     memset(h, -1, sizeof h);
42     for( int i = 0; i < m; i++ ){
43         int a, b;
44         cin>>a>>b;
45         add(a, b);
46     }
47     cout<endl;
48     
49     return 0;
50 }