这篇文章上次修改于 355 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(2): 基环树&字典树

基环树

若一个图有n个节点，n-1条边，那么这个图一定无环，此时若再增加一条边，必定会出现一条环。

由此可得 n个节点，n条边，必定有个环，去掉这个环的每个边，剩余的就是多颗树。

对于一个这样的图我们就称为基环树

基环树实际上是图而不是树

无向图上的基环树

graph LR
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))

3 --- 4
4 --- 5
5 --- 3

2 --- 4
1 --- 2
6 --- 2
7 --- 5

图中的3 4 5形成一个环，这就是基环树的基本特征

同时，如果图不一定全联通，那就有多个基环树组成，有几个联通分量就有几个基环树

有向图上的基环树

同样是n个节点，n条边作为前提条件

内向基环树

若每个点都只有一条出度，该图为内向基环树

graph LR
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))

3 ---> 4
4 ---> 5
5 ---> 3

2 ---> 4
1 ---> 2
6 ---> 2
7 ---> 5

除了环以外的树枝上的节点都指向其树的父节点

外向基环树

若每个点都只有一条入度，该图为内向基环树

graph RL
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))

3 ---> 4
4 ---> 5
5 ---> 3


2 ---> 1
2 ---> 6
5 ---> 7
4 ---> 2

除了环以外的树枝上的节点都是树的父节点指向子节点。

寻找环

tarjan 算法

搜索每个节点，标记节点的 DFN 值，并记录每个结点的前驱；

若搜索到一条返祖边，则从当前节点沿前驱节点回溯至边的另一端点，则回溯路上的所有节点均为环上的节点；

vector <edge> g[MAXN];
int dfn[MAXN], cnt, fa[MAXN], loop[MAXN], len;
void dfs_loop(int i) {
	dfn[i] = ++cnt;
	for (int t = 0; t < g[i].size(); t++){
		int v = g[i][t];
		if (v == fa[i]) continue;
		if (!dfn[v]) {
			fa[v] = i;
			dfs_loop(v);
		} else {
			if (dfn[v] < dfn[i]) continue; 
			loop[++len] = v;
			for (; v != i; v = fa[v]) loop[++len] = fa[v];
		}
	}
}

拓扑排序

记录每个节点的度数，进行拓扑排序；

则入度 ≥ 2 的点即为环上的点；

则拓扑排序后度数不为 0 的节点即为环上的点；

void topo_loop() {
	queue <int> q;  
	for (int i = 1; i <= n; i++) {
		if (de[i] == 1) q.push(i);
	}   
    while (!q.empty()) {
        int i = q.front();
		q.pop();
        for (int t = 0; t < g[i].size(); t++) {
            int v = g[i][t];
			if (de[v] > 1) {
            	de[v]--;
            	if (de[v] == 1) q.push(v);
			}
        }
    }
    return;
}

字典树

字典树，又称Trie树、前缀树，是一种树形结构，用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

// Trie节点
struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}

    // 递归释放内存
    ~TrieNode() {
        for (auto& pair : children) {
            delete pair.second;
        }
    }
};

// Trie类
class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 插入单词
    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    // 搜索单词
    bool search(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return node != nullptr && node->isEndOfWord;
    }

    // 判断是否有单词以给定前缀开头
    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return node != nullptr;
    }

    // 释放内存
    ~Trie() {
        delete root;
    }
};

每一个节点就是一个字符，可以储存多个字符的前缀情况。

Mai Icy