樹

1. 并查集：
   • 并查集的應用：
     • 判斷連通性、判環(huán)
     • Kruskal算法=排序+并查集
   • 并查集的存儲方式
     • 邏輯：雙親表示法的樹
     • 存儲：數(shù)組
   • 并查集的時間復雜度（m為并查集長度）
     • find：優(yōu)化前為$O(m)$；優(yōu)化后為$O(lo{g}_{2}n)$
     • union：$O(1)$
     • 總復雜度：優(yōu)化前$O(m^2)$；優(yōu)化后$O(m)$
2. 樹、森林、二叉樹遍歷序列的關系

   樹	森林	二叉樹
   先根遍歷	先序遍歷	先序遍歷
   后根遍歷	中序遍歷	中序遍歷

   關于森林的中序遍歷/后序遍歷叫法問題：二者指森林的同一種遍歷方法，都是先遍歷第一棵樹的子節(jié)點，然后是第一棵樹的根節(jié)點，然后是第二棵樹… 之所以稱為中序遍歷，是因為要先處理完一棵樹再處理另一棵樹。

圖

1. DFS與BFS算法的應用：
   • DFS：
     • 判斷圖的（強）連通性
       • 無向圖的連通性：若從任意一個節(jié)點出發(fā)，僅需一次DFS就可以訪問圖中所有節(jié)點，則該無向圖就是連通的
       • 有向圖的強連通性：從任意一個節(jié)點v出發(fā)DFS，若可以遍歷該有向圖的所有節(jié)點，則此時將該有向圖的所有邊反向，再次從節(jié)點v出發(fā)進行DFS，若能夠再次遍歷該有向圖的所有節(jié)點，則表示該有向圖是強連通圖
     • 判斷圖中是否有環(huán)（回路）
     • 歐拉回路求解：若一條路徑能不重復的包含圖中所有邊，則稱該路徑為歐拉路徑。若一條回路（從一個節(jié)點出發(fā)又能回到該節(jié)點的路徑）是歐拉路徑，則稱為歐拉回路。DFS可以判斷圖中是否存在歐拉回路
     • 迷宮
     • 判斷二分圖
   • BFS：
     • 求解單源最短路徑問題（只適用于無權圖）
     • 迷宮
     • 判斷二分圖
2. 最短路徑
   • 有無環(huán)（回路）對Dijkstra算法并無影響，但Dijkstra算法不能求解存在負權值邊的圖；Floyd算法可以求帶有負權值邊的圖，但圖中不能存在負權回路（因為帶有負權回路的圖沒有最短路徑）
   • Dijkstra算法是解決單源最短路徑類問題，floyd算法是解決多源最短路徑（指圖中任意兩個頂點之間的最短路徑）類問題
   • Dijkstra算法屬于貪心算法，floyd算法屬于動態(tài)規(guī)劃算法
3. 判斷有向圖是否有環(huán)（回路）的幾種方法：
   • 深度優(yōu)先遍歷：若在遍歷過程中遇到要訪問的節(jié)點已在棧中就是有環(huán)
   • 拓撲排序：找不到拓撲序列必定有環(huán)
4. 拓撲排序
   • 在拓撲排序算法中，為暫存入度為零的頂點可以使用棧，也可以使用隊列。（因為只要入了棧/隊列，就都是入度為零的，從哪個入度為零的先開始都無所謂）
   • 采用深度優(yōu)先遍歷也可實現(xiàn)拓撲排序