树和二叉树

树的层次遍历

用队列来实现。
queue.add(root)
do{
node = queue.pop()
print(node)
queue.add(node.left
queue.add(node.right)
}

这样遍历二叉树的方法成为宽度优先遍历(Breadth-First Search, BFS). BFS在显示图和隐式图算法中很重要。

二叉树的递归遍历

• PreOrder(T) = T的根结点 + PreOrder(T的左子树) + PreOrder(T的右子树)
• InOrder(T) = InOrder(T的左子树) + T的根结点 + InOrder(T的右子树)
• PostOrder(T) = PostOrder(T的左子树) + PostOrder(T的右子树) + T的根结点

这三种遍历都属于递归遍历，或者说深度优先遍历(Depth-Frist Search, DFS).

eg: 根据二叉树的InOrder和PostOrder, 构造树的结构
LC105, construct binary tree from preorder and inorder.
LC106, construct binary tree from inorder and postorder.//this one
LC889, construct binary tree from preorder and postorder.

思路都是, postorder的第一个字符就是root, 因此只需在inorder中找到它。就知道左，右子树的postorder和inorder了。然后递归来创建树。

图

DFS求联通块

图也有DFS和BFS遍历。由于DFS更容易编写，一般用DFS找联通块。从每个’1’格子出发，递归遍历它周围的格子。每次访问都给它打上一个“连通分量编号”的tag, 这样就可以在访问之前检查它是否已经有了编号，从而避免同一个格子访问多次。
LC200. Number of islands

1
2
3
4
5
6

input:
****@
*@@*@
*@**@
@@@*@
@@**@

找连通分量，包括相邻或斜对角。可以定一个一个三维数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void dfs(int r, int c, int id){
  if(r<0||r>=m ||c<0 || c>=n) return; //出界
  if(idx[r][c] > 0 || pic[r][c]!='@') return;//不是@或已经访问过的格子
  idx[r][c] = id;//连通分量编号
  for(int dr=-1; dr<=1; dr++){
    for(int dc=-1; dc<=1; dc++){
      if(dr!=0 || dc!=0) dfs(r+dr, c+dc, id);
    }
  }
}

int main(){
  int cnt=0;
  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      if(idx[i][j] == 0 && pic[i][j] == '@') dfs(i, j, ++cnt);
    }
  }
  return cnt;
}

上面的代码用一个二重循环来找到当前格子的相邻8个格子。也可以用常量数组， 或者写8条DFS调用。

用BFS求最短路

经典立体: 走迷宫。有n行m列的单元格组成，每个单元格要么是空地(1)要么是障碍物(0), 要求找到从起点到终点的最短路径。

例题6-14 Abbott的复仇
一个最多包含9*9个交叉点点迷宫，输入起点，离开起点时的朝向和终点，求一条最短路。
迷宫的特殊之处在于进入一个交叉点的方形(用NEWS来表示上下左右)不同, 允许出去的方向也不同。
例如一个房间标志 WLF NR ER表示，进入时如果方向为左(W), 可以左转(L)或者直行(F)。如果进入时朝向为N或者E, 则只能右转(R).

分析: 和普通迷宫在本质上是一样的，但是由于“朝向”也起到了关键作用，所以需要用一个三元组(r, c, dir)表示位于(r,c)，面朝dir这个状态。用d[r][c][dir]表示初始状态到(r, c, dir)到最短路长度，并用p[r][c][dir]保存了状态(r, c, dir)在BFS树中的父结点。
P用来输出最短路径(所以需要记录父节点，这样可以一直倒推回来).
注意: 使用BFS求出图的最短路之后，可以用递归的方式打印最短路的具体路径。如果最短路非常长，递归可能会引起栈的一处。此时可以该用循环，用vector保存路径。

很多复杂的迷宫问题都可以转化为最短路问题,然后用BFS求解,在套用BFS框架前，要搞清楚图中的结点包含哪些内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

const char* dirs = "NESW";//顺时针旋转， 编号0~3
const char* turns = "FLR";//方向，直行，左转，右转。编号0~3

//行走函数，根据当前状态和转弯方式，计算出后继状态
const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

//turn = 0 直行，1 左转， 2 右转
Node walk(const Node& u, int turn){
  int dir = u.dir;
  if(turn == 1) dir = (dir+3)%4;//逆时针
  if(turn == 2) dir = (dir+1)%4;//顺时针
}

//初始状态是(r0, c0, dir), 计算出(r1, c1). 然后读入has_edge数组, 其中has_edge[r][c][dir][turn]表示当前状态是(r, c, dir), 是否可以沿着转弯方向turn行走。
void bfs(){
  //设置d的初始值为-1
  Queue<Node> q;
  Node u(r1, c1, dir);
  d[u.r][u.c][u.dir] = 0;
  q.push(u);//intial status.
  while(!q.empty()){
    Node u = q.pop();
    if(u is destination){
      print_ans(u);
      return;
    }
    for(int i=0; i<3; i++){//three orientation
        Node v = walk(u, i);
        if(has_edge(u.r, u.c, u.dir, i) && inside(v.r, v.c) && d[v.r][v.c][v.dir]<0{//not visited before.
          d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;
          p[v.r][v.c][v.dir] = u;
          q.push(v);
        }
    }
  }
}

//打印最短路径
void print_ans(Node u){
  vector<Node> nodes;
  for{
    nodes.push(u);
    if(d[u.r][u.v][u.dir] == 0) break;
    u = p[u.r][u.c][u.dir];
  }
  nodes.push(Node(r0, c0, dir));
  //然后逆序遍历数组nodes
}

拓扑排序

假设有n个变量，还有m个二元组(u, v), 分别表示变量u<v, 那么所有变量从小到大排列起来应该是什么样子的呢？(找出其中一个即可)

分析: 把每个变量看成一个点，“小于”关系看成有向边, 则得到了一个有向图。这样我们的任务实际上是把一个图的所有结点排序。使得每一条有向边(u, v)对应的u都排在v的前面。在图论中，这个问题成为拓扑排序。

不难发现，如果图中存在 有向环，则不存在拓扑排序。反之则存在。不包含有向环的有向图称为有向无环图(Directed Acyclic Graph, DAG). 可以借助DFS完成拓扑排序：在访问完一个结点之后把它加到当前拓扑序的首部。

c[u] = 0表示从来没有访问过(从来没有调用过dfs(u)); c[u] = 1表示已经访问过，并且还递归访问过它的所有子孙。(即dfs(u)曾被调用过，并已返回)；c[u] = -1表示正在访问（即递归调用dfs(u)正在栈中，尚未返回）。于是我们在dfs的时候，遇到了c[u] = -1的点，表示存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

itn c[maxn];
bool toposort(){
  t = n;//cursor,由于是递归，每次插入底部。
  memset(c, 0, sizeof(c));
  for(int u=0; u<n; u++){
    if(c[u] == 0){//对还未访问过的点做dfs
      if(!dfs(u)) return false;
    }
  }
  return true;
}

bool dfs(int u){
  c[u] = -1; //访问标志
  for(int v = 0; v<n; v++){
    if(G[u][v]){//have edge
      if(c[v] == -1) return false;//存在有向图，失败退出
      else if(c[v] == 0 && !dfs(v)) return false;
    }
    c[u] = 1; topo[--t] = u;
    return true;
  }
}

欧拉回路

经典问题，是否存在一条路线，可以不重复地走遍7座桥。
首先抽象成图的问题，能否从无向图的一个结点出发，走出一条道路，每条边恰好经过一次。
分析: 在欧拉道路中，”进”和”出”是对应的, 除了起点和终点以外，其他点的进，出次数应该相等。则如果一个无向图是连通的，且最多只有两个奇点，并且两个奇点也必须从一个出发，一个终止。则其中一个点的出度恰好比入度大1(起点)，一个点的出度恰好比入度小1(终点)。还有一个容易被忽略的前提条件：图必须是连通的(DFS)

例题:
输入n个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同(例如acm, malform, mouse)。

解题:
把字母看成结点，单词看成有向边，当且仅当图中有欧拉路径。
a的入度为1,出度为0. m的入度出度都为2, e的入度为0，出度为1. 则欧拉环路存在。

• ← Previous Post
• Next Post →