[Algo] Graph & Tree

图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)

graph can be represented by adjacency matrix or adjacency table.

Basic :

• directed / undirected graph
• complete graph (every tow vertexes are connected ： bi-directions if directed graph)
• transerval graph : DFS/BFS 
• 需要有一个visted flag来避免环
• DFS用 stack或者recusive call
• BFS用queue
• 利用一个from表记录下来当前node之前一个点可以用来输出路径
• DFS是寻路，BFS找到的是最短路径
• E= sum(D(i)) / 2 = sum(ID(i) + OD(i)) / 2 : 边的数量 == 所有顶点 出度 入度的总和除以2

Advanced :

• Strongly connected component : 
• directed graph
• 每一個頂點皆可以經由該圖上的邊抵達其他的每一個點的有向圖 
• DAG Directed Acyclic Graph 有向无环图
• 拓扑排序（Topological Sorting）
• 定义：
• 每个顶点出现且只出现一次
• 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面
• 算法： 每次移除无前序的node， 这个顺序就是topological sort
• 应用 ： “排序”具有依赖关系的任务
• 
  

tree ！= DAG （子节点对应唯一父节点，但是DAG可以出现共享子节点的情况）

tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

E=N-1 边数==点数-1

Tree < DAG < Graph

• 正是因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。
• 一棵树中的任意两个结点有且仅有唯一的一条路径连通。
• 一棵树如果有 n 个结点，那么它一定恰好有 n-1 条边。

Tree Traversal

• DFS (recusive implementation is easy: can use stack insteandly)
• In-order ： root -> left -> right
• Pre-order ： left->root -> right
• Post-order : left-> right -> root
• BFS
• traversal by level : use queue

Binary Search Tree

• 若左子树非空，则左子树所有结点关键字值均小于根结点关键字的值
• 若右子树非空，则右子树所有结点关键字值均小于根结点关键字的值
• 左，右子树本身也是一个二叉搜索树（BST）

https://github.com/jianfeipan/LeetCode/blob/main/graph/tree/BST/BST.cpp

Is BTS : 

中序遍历一个BST会得到一个有序的递增序列

Search:

recusive or while loop 

Insert node:

if left child is null --> insert as left child,

if right child is null --> insert as right child,

else --> recusivly insert to that branch

Remove node:

if no left and no right child, --> remove directly

if no left child --> replace current node by right tree

if no right child --> replace current node by left ree

if has left and right child -->  

• set left branch's MAX value then call remove to remove that value on left tree 

or 

• set right branch's MIN value then call remove to remove that value on right tree