6. 树的入门

  • 满二叉树：
    • 每个节点恰好都有两个孩子节点且所有叶子节点都在同一层。
    • 节点个数为2h+1-1，其中h为树的层数。
  • 完全二叉树：
    • 假设树的按高度为h，将所有节点从根节点开始从左至右，从上至下，依次编号（根节点为1），那么将得到从1~n（n为节点总数）的完整序列。注意：在遍历过程中对于空指针也赋予编号。如果所有叶子结点的深度为h或者h-1，且在节点编号序列中没有漏掉任何数字和节点，那么此二叉树叫做完全二叉树。
    • 节点个数为2h ~ 2h+1-1，对于拥有n个节点的完全二叉树。空指针的个数为n+1

image.png

深度遍历用栈，层序遍历用队列

二叉树的非递归前序、中序、后序遍历

  • 前序遍历：https://blog.csdn.net/dabusiGin/article/details/102547845
    • 现将root进栈
    • 然后while循环判断 !stack.isEmpty()
      • 先出栈，打印当前节点数据
      • 然后 右子节点不为空先进栈
      • 在 左子节点不为空入栈

  • 中序遍历：https://blog.csdn.net/qq_43255017/article/details/104239777?spm=3001.4430
    • 现将root赋值给当前节点，Node current = root;
    • 然后循环判断while (current != null || !stack.isEmpty())
      • 循环while判断，只要当前节点不为null（此步骤为将所有最左侧左子节点入栈）
        • 当前节点入栈
        • 当前节点改为左子节点 current = current.left;
      • 判断，!stack.isEmpty()
        • 出栈，设为当前节点 current = s.removeFirst();，并打印当前节点数据
        • 当前节点改为 右子节点，（为了输出右子节点）

6.树的入门.pdf

11. 图的入门


深度优先搜索：

  1.  private void bfs(Graph G, int v) {
  3.         //让顶点v进入队列，待搜索
  4.         waitSearch.enqueue(v);
  5.         //通过循环，如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
  6.         while(!waitSearch.isEmpty()){
  7.             //弹出一个待搜索的顶点
  8.             Integer wait = waitSearch.dequeue();
  9.             //把当前顶点v标识为已搜索
  10.             marked[v] = true;
  11.             //遍历wait顶点的邻接表
  12.             for (Integer w : G.adj(wait)) {
  13.                 if (!marked[w]){
  14.                     marked[w] = true;
  15.                     waitSearch.enqueue(w);
  16.                     //让相通的顶点+1；,结果错了，总是多了1
  17.                     count++;
  18.                     System.out.println("点："+w);
  19.                 }
  20.             }
  21.         }
  24.     }

DFS应用：拓扑排序、两点之间的路径（先深度优先标出与其联通的所有点，过程中用一个数组标记当前点前面的点 ）
BFS应用：最短路径

12. 图的进阶


https://www.bilibili.com/video/BV1zz4y1m7Nq?from=search&seid=6080602822924734684
image.png
image.png
最短路径树算法，上面的更容易理解

若权重存在负数，则只能用Bellman-Ford算法

13. 常见查找算法

14. 十字链表

15. 最大流（max-flow）、最小割（min-cut）定理

15.1 基本概念

https://blog.csdn.net/yjr3426619/article/details/82715779
image.png
流量图：增加了标注流量 和容量的有向图
image.png
弧：图中的边
弧的流量：经过弧上的时机流量xij
弧的容量：弧上能够通过的最大流量Cij
网络流：所有这些弧的流量所组成的集合
源点（发点）：仅有出弧而没有入弧的点Vs
汇点（收点）：仅有入弧而没有出弧的点Vt
中间点：既非源点也非汇点的其他点
可行流：

  • 每条弧上的流量不能超过其容量，
  • 平衡条件：
    • 源点的输出量=汇点的输入量
    • 对于除了源点和汇点以外的每个点来说，流入它的流量之和必须与从它流出的流量之和相等

image.png
链μ：点、弧的交错序列
image.png
前向弧：弧的方向与源点到汇点方向一致
后向弧：弧的方向与源点到汇点方向相反
image.png
增广链（增流链）：能够使流增大的一条链。前向弧可以增加流量（非饱和流），后向弧可以减少流量（非零流）

15.2 最大流：

可行流x是最大流的充要条件是不存在从源点到汇点的关于流x的一条增广链

15.3 求解最大流——Ford-Fulkerson算法（标号法）

https://www.bilibili.com/video/BV1Yt4y1q77c?p=3&spm_id_from=pageDriver

一、标号过程

①标记是前向弧还是后向弧，前向弧为“+”
②标记每条弧流的改变量可以是多少

  1. 给源点标号（0，+∞），源点的改变量可以是无穷
  2. 取一个已经标号的点Vi，对于Vi一切未标号的邻接点Vj，按照下列规则处理：
    1. 深度优先算法对相邻节点标号
    2. 广度优先算法标号

下面采用深度优先标号：

  1. 若弧为前向弧并且为非饱和弧，则给Vj标号（+Vi，△j），Vi→Vj，改变量增量△j=min{Cij-xij，△i}，△i为顶点Vi的改变量
  2. 若弧为后向弧并且为非零流弧，则给Vj标号（-Vi，△j），Vi←Vj，改变量减少量△j=min{xij，△i}
    1. 重复步骤2，知道汇点Vt被标号或标号过程无法进行下去，则标号结束。
  3. 若Vt被标号，则存在一条增广链，转到调整过程
  4. 若Vt未被标号，二标号过程无法进行下去，则可行流（当前的流量图）为最大流

    二、调整过程

  1. 设 △1**=**min{△j|链μ的前向弧改变量}

△2**=**min{△j|链μ的后向弧改变量}
△**=**min{△1，△2}

  1. 取整条链μ上所有弧的改变量最小值△。该值就是调整量△。增广链μ上的前向弧加上调整量△，后向弧减去调整量△，不属于增广链上的弧不变
  2. 去掉所有标号，回到第一步重新标号

    15.4 最小割：

    S-T Cut 将顶点分成两个集合S、T。其中源点s∈S，汇点t∈T
    image.png
    上图S-T Cut 容量为 Cap（S,T）= 2+2+2 =6
    image.png
    上图S-T Cut 容量为 Cap（S,T）= 2+1 =3

    Min-Cut：S-T Cut中 容量最小的那个 min{Cap（S,T）}

S-T Cut是切断管道，让起点的水无法流向终点。
Min-Cut目标是让切断的管道容量最小，最省事

最大流最小割定理

最大流的流量=最小割的容量
image.png

16. floyd算法

又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

bellman算法求解存在负权重的图的最短路径-

17. TSP问题（旅行商问题）

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

MTSP

18. 爬山算法

爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 属于人工智能算法的一种。

19. NP问题

https://blog.csdn.net/qq_29176963/article/details/82776543?depth_1-
image.png
n为不确定
NP问题是指存在多项式算法能够验证的非决定性问题，是否计算机可解

20. 图着色问题

最著名的NP-完全问题之一

21. 匈牙利算法

图论中寻找最大匹配的算法

22. 背包问题