例题分析
LeetCode 第 785 题：给定一个无向图 graph，当这个图为二部图时返回 true。
提示：如果能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为二部图。
解题思路
判断一个给定的任意图是否为二部图，就必须要对该图进行一次遍历：
- 深度优先
- 广度优先
（关于深度优先和广度优先算法，将在第 06 节课进行详细讨论）。
二部图，图的所有顶点可以分成两个子集 U 和 V，子集里的顶点互不直接相连，图里面所有的边，一头连着子集 U 里的顶点，一头连着子集 V 里的顶点。
给图里的顶点涂上颜色，子集 U 里的顶点都涂上红色，子集 V 里的顶点都涂上蓝色。
开始遍历这个图的所有顶点，想象一下手里握有红色和蓝色的画笔，每次交替地给遍历当中遇到的顶点涂上颜色。
如果这个顶点还没有颜色，那就给它涂上颜色，然后换成另外一支画笔。
下一个顶点，如果发现这个顶点已经涂上了颜色，而且颜色跟我手里画笔的颜色不同，那么表示这个顶点它既能在子集 U 里，也能在子集 V 里。
所以，它不是一个二部图。
前缀树（Trie）
应用场景
前缀树被广泛地运用在字典查找当中，也被称为字典树。
举例：给定一系列字符串，这些字符串构成了一种字典，要求你在这个字典当中找出所有以“ABC”开头的字符串。
解法 1：暴力搜索
直接遍历一遍字典，然后逐个判断每个字符串是否由“ABC”开头。假设字典很大，有 N 个单词，要对比的不是“ABC”，而是任意的，那不妨假设所要对比的开头平均长度为 M，那么时间复杂度是 O(M×N)。
解法 2：前缀树
如果用前缀树头帮助对字典的存储进行优化，那么可以把搜索的时间复杂度下降为 O(M)，其中 M 表示字典里最长的那个单词的字符个数，在很多情况下，字典里的单词个数 N 是远远大于 M 的。因此，前缀树在这种场合中是非常高效的。
经典应用
网站上的搜索框会罗列出以搜索文字作为开头的相关搜索信息，这里运用了前缀树进行后端的快速检索。
汉字拼音输入法的联想输出功能也运用了前缀树。
举例：假如有一个字典，字典里面有如下词："A"，"to"，"tea"，"ted"，"ten"，"i"，"in"，"inn"，每个单词还能有自己的一些权重值，那么用前缀树来构建这个字典将会是如下的样子：
性质
1. 每个节点至少包含两个基本属性。
children：数组或者集合，罗列出每个分支当中包含的所有字符
isEnd：布尔值，表示该节点是否为某字符串的结尾
2. 前缀树的根节点是空的
所谓空，即只利用到这个节点的 children 属性，即只关心在这个字典里，有哪些打头的字符。
3. 除了根节点，其他所有节点都有可能是单词的结尾，叶子节点一定都是单词的结尾。
实现
前缀树最基本的操作就是两个：创建和搜索。
1. 创建
- 遍历一遍输入的字符串，对每个字符串的字符进行遍历
- 从前缀树的根节点开始，将每个字符加入到节点的 children 字符集当中。
- 如果字符集已经包含了这个字符，则跳过。
- 如果当前字符是字符串的最后一个，则把当前节点的 isEnd 标记为真。
由上，创建的方法很直观。
前缀树真正强大的地方在于，每个节点还能用来保存额外的信息，比如可以用来记录拥有相同前缀的所有字符串。因此，当用户输入某个前缀时，就能在 O(1) 的时间内给出对应的推荐字符串。
2. 搜索
与创建方法类似，从前缀树的根节点出发，逐个匹配输入的前缀字符，如果遇到了就继续往下一层搜索，如果没遇到，就立即返回。
