做题ing

数据结构：存储方式、遍历方式

数据结构有很多种。但是存储方式，无非就是数组或者链表。比如：
1. 树
  - 数组存储：完全二叉树👉堆
  - 链表存储：最常用的，二叉树、AVL树、多叉树
2. 图
  - 数组存储：邻接矩阵。方便操作，但是不适用于稀疏图。
  - 链表存储：邻接表。省空间，但是不好操作
数组、链表，优缺点
- 数组：
  - 优点：随机访问
  - 缺点：扩容、插入、删除，时间复杂度高是O(N)
- 链表
  - 优点：扩容、插入、删除，方便
  - 缺点：不能随机访问，存储空间消耗大（每个节点保存数值、前驱/后继指针）
数据结构遍历方式，无非迭代和递归两种。
- 迭代（数组）
- 递归（链表、二叉树）

BFS

本质：求图中起点到终点的最短距离
一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些。

BFS：代码框架

 // 计算从起点 start 到终点 target 的最近距离
 int BFS(Node start, Node target) {
     Queue<Node> q; // 核心数据结构
     Set<Node> visited; // 避免走回头路

     q.offer(start); // 将起点加入队列
     visited.add(start);
     int step = 0; // 记录扩散的步数

     while (q not empty) {
         int sz = q.size();
         /* 将当前队列中的所有节点向四周扩散 */
         for (int i = 0; i < sz; i++) {
             Node cur = q.poll();
             /* 划重点：这里判断是否到达终点 */
             if (cur is target)
                 return step;
             /* 将 cur 的相邻节点加入队列 */
             for (Node x : cur.adj())
                 if (x not in visited) {
                     q.offer(x);
                     visited.add(x);
                 }
         }
         /* 划重点：更新步数在这里 */
         step++;
     }
 }

关键
- 一个队列，一个循环
- visited 作用是防止走回头路，多数时候是必须的。
  - 对于二叉树结构，不需要 visited。因为，没有子节点到父节点的指针，本来就不会走回头路。
BFS 和 DFS(回溯/递归) 的优缺点
- BFS，时间复杂度低，空间复杂度高。
  - time：借助队列，「齐头并进」，不需要遍历完毕，就能找到最短距离。depth 每增加一次，队列中的所有节点「齐头并进」都向前迈一步，保证第一次到达终点时，走的步数最少。
  - space：空间开销来自队列。队列中，每次保存二叉树的一层节点，最坏情况下，space是最底层节点的数量 N/2，即 O(N)。（假设满二叉树）
- DFS，时间复杂度高，空间复杂度低。
  - time：要想找到最短路径，得把二叉树遍历完毕。DFS靠递归的堆栈记录走过的路径，对比所有路径找最短。
  - space：空间开销来自递归堆栈，最坏情况下就是树的高度，即 O(logN)。（假设满二叉树）

做题ing

数据结构/算法知识点、题型整理

做题ing

数据结构：存储方式、遍历方式

BFS

CATALOG

FEATURED TAGS

FRIENDS