关于c++:树与图

树的存储

树的父亲表示法

// data
string nodes[N];
int fa[N];
fa[0] = -1;

void add(int b, int a) {fa[b] = a;
}

二叉树的儿子表示法

struct Node {
    string data;
    int lc; // 未应用指针
    int rc; // 未应用指针
    Node() { lc = rc = -1;}
};
Node nodes[N];

二叉树的数组表示法

// data
string nodes[N];
// ch[i][0]示意左儿子，ch[i][1]示意右儿子
int ch[N][2];

树与图的存储

树是一种非凡的图，与图的存储形式雷同。
无向图也是一种非凡的有向图。对于无向图中的边 xy，存储两条有向边 x->y , y->x。因而咱们能够只思考 有向图 的存储。

邻接矩阵（浓密图）

bool g[N][N];

void add(int x, int y) {g[x][y] = 1; }

邻接表（稠密图）

#include <vector>

std::vector<int> g[N];

// 增加一条边 x ->y
void add(int x, int y) {g[x].push_back(y); }

树与图的遍历

深度优先遍历（邻接表）

void dfs(int i) {st[i] = true; // 点 i 曾经被遍历过

    for (auto j : g[i])
        if (!st[j]) dfs(j);
}

宽度优先遍历（邻接表）

void bfs(int i) {
    queue<int> q;
    q.push(i);
    st[i] = true; // 点 i 曾经被遍历过
    
    while (!q.empty()) {int t = q.front();
        q.pop();

        for (auto j : g[t])
            if (!st[j]) {q.push(j);
                st[j] = true; // 点 j 曾经被遍历过
            }
    }
}