跳转至

树和图

  • 树是无环、连通的特殊图
  • 图的分类：
    • 有向图
    • 无向图（特殊的有向双向图）

有向图

  1. 邻接矩阵
    1. g[a][b]存储a——>b的关系
    2. 存储重边时仅保留一边
    3. 缺点：浪费空间
  2. 邻接表（单链表）
    1. 为每一个点存储一个单链表
    2. 每个链表表示该结点所有连通的
    3. 插入时候一般选择头插
  3. 树和图的存储： 
    int h[N], e[M], ne[M], idx;

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

  4. 遍历

    1. 深度优先遍历

      1. 特点：可以算出每一个子树的大小 
        bool st[N];

void dfs(int u){
    st[u] = true;
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(!st[j]) dfs(j);
    }
}

    2. 宽度优先遍历

例题

DFS：树的重心

问题： 1. 怎么实现删除结点 2. 为什么可以从任意结点开始深搜：图是无向图 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5+10, M = 2 * N;
int h[N], e[M], ne[M], idx;
bool st[N];
int n, m, ans = N;

void connect(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, res = 0;      
    //sum记录结点总数，但并不作为结果输出,
    //res记录结果
    for(int i = h[u];i != -1;i = ne[i]){        //遍历访问每一个子节点
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);         //u结点的单棵子树的节点数
            res = max(s, res);      //记录最大连通子树的节点数
            sum += s;       //求和，求所有以j为根的树的大小
        }
    }
    res = max(res, n - sum);     //n-sum指的是     

    ans = min(ans, res);        //比较，获取较小值
    return sum;     //返回和
}

int main(){
    cin >> n;
    int a, b;
    memset(h, -1, sizeof h);

    for(int i = 0;i < n - 1;i++){
        scanf("%d%d", &a, &b);
        connect(a, b);         //无向图的双向连接
        connect(b, a);
    }

    dfs(1);               //为什么从任意点搜索都可以？？？？？

    cout << ans << endl;

    return 0;
}

BFS：图中点的层次

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+10;
int h[N], e[N], ne[N], idx;
int recorder[N];
int n, m;
queue<int> q;

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

int bfs(){
    memset(recorder, -1, sizeof recorder);
    recorder[1] = 0;
    q.push(1);
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(recorder[j] == -1){
                recorder[j] = recorder[t] + 1;
                q.push(j);
            }
        }
    }
    return recorder[n];
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);        //注意单链表的初始化
    int a, b;
    while(m--){
        cin >> a >> b;
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}

有向图的宽搜的一个经典应用：图的拓补序列

  • 拓补的意义：一个图中，所有的边都是从前指向后的

    对于每个点，有入度，出度（度数） - 入度：有多少条边指向自己 - 出度：有多少条边出去

所有入度为0的点都可以作为起点 一个有向无环图一定至少存在一个入度为0的点 模板： 

d[]存储所有点的入度
queue<int> q;（所有入度为0的点入队）
while(!q.empty()){
    auto t = q.front();
    q.pop();
    枚举所有的出边:
        删除t——>j的边，使d[j]--;
        if(d[j] == 0) 说明当前的拓补序列成立 //因为所有入度为0的点，都可以成为拓补序列的起点
        q.push(j);
}

问题： - 如何计算入度：在连接边的时候，对后者的入度+1即可 - 如何找到拓补序列：使用模拟队列时，队列的的元素即是拓补序列 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];

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

bool topsort(){
    int hh = 0, tt = -1;
    for(int i = 1;i <= n;i++){
        if(d[i] == 0){
            q[++tt] = i;
        }
    }

    while(tt >= hh){
        int t = q[hh++];
        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[++tt] = j;
        }
    }


    return tt == n - 1;
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a, b;
    while(m--){
        cin >> a >> b;
        add(a, b);
        d[b]++;     //统计入度
    }

    if(topsort()){
        for(int i = 0;i < n;i++){
            printf("%d ",q[i]);     //打印拓补序列
        }
        puts("");
    }
    else{
        printf("-1");
    }

    return 0;
}