图3:拓扑排序
现实生活中的的顺序并不是简单的大小比较,而是一种依赖关系。比如我们穿衣服必须先穿内裤再穿外裤,先穿袜子再穿鞋。再比如,编译文件的时候先编译没有依赖的文件,再编译依赖文件。
现实生活中的的顺序并不是简单的大小比较,而是一种依赖关系。比如我们穿衣服必须先穿内裤再穿外裤,先穿袜子再穿鞋。再比如,编译文件的时候先编译没有依赖的文件,再编译依赖文件。
图的表达能力很强,图的搜索算法在实际生产中有巨大的用出,不论是游戏寻路,地图导航,路径规划等等方向都有普遍应用。我们生活中很多场景都可以抽象为图结构,这使得图算法一直是一个重点,难点也是热点。
在图论中,图 (graph) 是一个二元组 G=(V(G), E(G))。其中 V(G) 是非空集,称为 点集 (vertex set),对于 V 中的每个元素,我们称其为 顶点 (vertex) 或 节点 (node),简称 点;E(G)为 V(G) 各结点之间边的集合,称为 边集 (edge set)。常用 G=(V,E) 表示图。
图(Graph)是一种由顶点(vertex)和边(edge)组成的非线性数据结构。
Trie 树,也叫“字典树”,它是一个树形结构,是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。是属于多模式匹配的一种解法。
BF、RK、BM和KMP都是单模式匹配算法,也就是一个主串只能匹配一个模式串。在很多时候我们还需要多模式匹配,也就是一个主串匹配多个模式串,比如聊天敏感词。敏感词是一个列表,一个主串可能包含了多个敏感词。