图论入门
-
图: 图由节点和边组成，一个节点可能与众多节点直接相连，直接相连的节点被称为邻居
-
根据图中的边是有向边还是无向边，图分有向图、无向图和混合图。
-
在有向图中，以结点 v 为出发点的边的数量，我们叫作 v 的出度。而以 v 为 终点的边之数量，称为 v 的入度。
-
节点和边的交替序列，叫做通路，通路上的任意两个结点其实就是互为连通的。如果一条通路的起始点 v1和终止点 vn相同，这种特殊的通路我们就叫作回路。
-
树是一种特殊的图，它是没有简单回路的连通无向图，这些都是树： evernotecid://4FD5F4CB-133C-491F-BEF8-5109BADC162B/appyinxiangcom/24533776/ENResource/p5
-
有向树，是一种特殊的树，也许是图论中使用最广泛的一类图形。其中的边都是有向的，还需要满足三个条件：
- 有且仅有一个节点入度为0（叫做根）
- 除根之外，其他节点入度都为1
- 从根到任意节点，只有一条通路
据此可以看出上面的树中，1和3如果边换成有向，那就是有向树了。有向树还有几个重要的概念，父结点、子结点、兄弟结点、先辈结点、后辈结点、叶子结点、结点的高度（或深度）、树的高度（或深度）。
-
树和图的关系：
- 图中结点之间的关系是 “邻居”， 树中结点之间的关系 “父子”，如果是无向图，“邻居” 之间是互通的，但是 “父子” 默认是单向关系，一般遍历从 “父” 到 “子”，子结点中一般不保留父结点的信息
- 图和树不一样的是，图会存在 “环” 的概念，就是回路，树中永远不可能有回路，否则就不是一棵树
- 可以说链表是特殊的树，树是特殊的图。
- 综上所述，对比树，在一般的图中做深度优先搜索的区别就是：我们需要记录我们之前访问过的结点，防止重复访问
前缀树(prefix tree)
又叫字典树 trie（Trie一词来自retrieve)，就是一种有向树
- 基本性质：
- 根节点不包含字符，除根节点意外每个节点只包含一个字符
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符串不相同
evernotecid://4FD5F4CB-133C-491F-BEF8-5109BADC162B/appyinxiangcom/24533776/ENResource/p9
