《数据结构与算法之美》笔记009

43. | 拓扑排序：如何确定代码源文件的编译依赖关系 - 开始

编译器如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序：
使用 '图' 这种数据结构的 '拓扑排序算法' 解决.
什么是拓扑排序

多个元素,部分或全部元素的两两依赖关系已经确定,如何安排一个序列,能够满足上述元素的两两依赖关系.
很多时候,拓扑排序的序列不是唯一的,因为可能不是所有元素之间都具有依赖关系.

c26d0f472d9a607c0c4eb688c01959bd[1].jpg

拓扑排序的原理很简单,重要的是拓扑排序的实现.
如何确定代码源文件的编译依赖关系:

把源文件和源文件之间的依赖关系,抽象成1个有向图;
每个源文件对应图中的一个顶点;
源文件之间的依赖关系就是顶点之间的边;
如果A先于B执行,或者说B依赖于A,就在A和B之间,构建一条从A指向B的的边;
注意这个图必须是一个有向无环图. 因为图中一旦成环,拓扑排序就无法工作;
拓扑排序本身就是基于有向无环图的一个算法.

public class Graph {
  //定义顶点的个数
  private int v;
  //每个顶点对应一个邻接表, 多个顶点构邻接表数组
  private LinkeList<Integer>[] adj;
  //构造函数
  public Graph(int v){
    this.v = v;
    adj = new LinkedList<Integer>[v];
    for(int i=0; i<v; i++){
      adj[i] = new LinkedList<Integer>();
    }
  }
  
  //s优先于t / t依赖于s
  //从顶点s出发,构建一条指向t的边
  public void addEdge(int s, int t){
    adj[s].add(t);
  }
}

如何在Graph这个有向无环图上,实现拓扑排序,有2种算法: Kahn算法和 DFS深度优先搜索算法.
看Kahn算法和 DFS深度优先搜索算法之前,首先回顾下之前的'图'相关知识.

43前置知识: 图

图是一种非线性表数据结构.
图中的每个元素叫做顶点.
图中的1个顶点可以与其他任意顶点进行连接,连接叫做边.
有向图:
每条边都是有方向的.A->B:从A到B. B->A:从B到A.
无向图:
每条边都是没有方向的.单纯代表A-B两个顶点建立连接.
每个顶点有多少条边,叫做顶点的度.
有向图中,每个顶点有入度和出度.
- 入度:有多少条边指向该顶点;
- 出度:从该顶点发出多少条边;
  
  图

带权图

每条边都有1个权重/weight.

带权图

图的存储方法: 邻接矩阵和邻接表.
使用邻接矩阵存储图

邻接矩阵底层是1个二维数组.
对于有向图: 顶点i向顶点j发出一条边 , 则 A[i][j] = 1;
对于无向图: 顶点i和顶点j之间有边,则 A[i][j] 和 A[j][i] 都是1;
对于带权图: 数组元素存储连接的2个顶点之间的权重;

使用邻接矩阵存储图

练一下markdown中怎么画矩阵.

$$\begin{matrix}
A & B & C\\
D & E & F\\
G & H & I\\
\end{matrix}$$

无向图:
$\begin{matrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 0\\ \end{matrix}$
有向图:
$\begin{matrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0\\ \end{matrix}$
带权图:
$\begin{matrix} 0 & 5 & 3 & 0\\ 5 & 0 & 2 & 6\\ 3 & 2 & 0 & 1\\ 0 & 6 & 1 & 0\\ \end{matrix}$

邻接矩阵的缺点: 浪费存储空间.
- 对于无向图,顶点i,j之间有边,需要A[i][j]和A[j][i]都存储为1,实际只存1个就够了.浪费了一半空间;
- 对于稀疏图.即顶点很多,但每个顶点的边不多,使用邻接矩阵就更加浪费存储空间.
  - 比如微信十亿用户,但每个用户最多2000个好友.使用邻接矩阵会浪费绝大部分存储空间.
邻接矩阵的有点:
- 邻接矩阵基于数组,获取2个顶点的关系非常快;
- 临街矩阵存储图可以将很多图的运算,转换为矩阵之间的运算,效率很高.

使用邻接表存储图

使用邻接表存储图

邻接表存储图很像散列表.
每个顶点对应1条链表,存储与该顶点相连的其他顶点.
邻接表存储图和邻接矩阵存储图比较:
- 相对于邻接数组节省空间,尤其是稀疏图场景.只有相连的顶点的边才会存储在对应顶点的链表中.
- 是用时间换空间,比如查询顶点A和顶点B是否相连,就要在A顶点对应的链表中遍历查询.
- 链表的存储对缓存不友好,所以链表中查询两个顶点之间的关系效率低.
- 可以将邻接表中的链表替换为支持快速查找的数据结构: 红黑树、跳表、有序动态数组,散列表

使用图,存储微博的用户之间关系
针对微博用户关系，假设我们需要支持下面这样几个操作：判断用户 A 是否关注了用户 B；判断用户 A 是否是用户 B 的粉丝；用户 A 关注用户 B；用户 A 取消关注用户 B；根据用户名称的首字母排序，分页获取用户的粉丝列表；根据用户名称的首字母排序，分页获取用户的关注列表。

public class Graph {
  //微博系统中用户量
  private int v;
  //BestType用于指代特定的数据结构,用于替换链表,提升链表的查询效率
  //followers用于存储每个用户关注的人
  private BestType<Integer>[] followers;
  //fans用户存储每个用户被哪些人关注
  private BestType<Integer>[] fans;
  public Graph(int v){
    this.v = v;
    followers = new BestType<Integer>[v];
    fans= new BestType<Integer>[v];
    for(int i=0; i<v; i++){
      followers[i] = new BestType<Integer>();
      fans[i] = new BestType<Integer>();
    }
  }
  //用户a关注用户b
  public void follow(User a, User b){
    Integer aIndex = hash(a);
    Integer bIndex = hash(b);
    Integer aId = a.userId;
    Integer bId = b.userId;
    //将用户b的id添加到用户a对应的 关注的人 中
    followers[aIndex].add(bId);
    //将用户a的id添加到用户b对应的 粉丝 中
    fans[bIndex].add(aId);
  }
  //用户a不再关注用户b
  public void unfollow(User a,User b){
    Integer aIndex = hash(a);
    Integer bIndex = hash(b);
    Integer aId = a.userId;
    Integer bId = b.userId;
    //将用户b的id从用户a对应的 关注的人 中删除
    followers[aIndex].remove(bId);
    //将用户a的id从用户b对应的 粉丝 中删除
    fans[bIndex].remove(aId);
  }
  
  //BestType具体选择哪一种支持快速查询的数据结构: 跳表 .
  //跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。
  //最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效
}

深度优先搜索算法和广度优先搜索算法 , 都是基于 '图' 这种数据结构.
广度优先搜索/BFS/Breadth-First-Search

public class Graph { // 无向图
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t) { // 无向图一条边存两次
    adj[s].add(t);
    adj[t].add(s);
  }
}

广度优先搜索,就是先查找离起始顶点最近的,然后是次近的,一层层往外搜索.
从顶点s出发,搜索一条从s到t的最短路径.

private void bfs(int s, int t){
  if(s == t){
    //同一顶点不用继续搜索
    return;
  }
  //记录指定顶点是否访问过
  boolean[] visited = new boolean[v];
  visited[s] = true;
  //保存每个访问过的顶点的前一顶点
  int[] prev = new int[v];
  for(int i=0;i<v;i++){
    prev[i] = -1;
  }
  //保存待比较其后续顶点的顶点
  Queue<Integer> queue = new LinkedList<Integer>();
  queue.add(s);
  while(queue.size() > 0){
    //获取当前顶点
    int curr = queue.poll();
    //遍历比较当前顶点的所有子顶点
    for(int i = 0; i<adj[curr].size(); i++){
      int c = adj[curr].get(i);
      if(!visited[c]){
        //标记当前子顶点 已被访问过
        visited[c] = true;
        //标记当前子顶点 的上一结点就是curr
        prev[c] = curr;
        //如果当前子顶点 就是 要寻找的最终顶点
        if(c == t){
          //打印整个搜索路径, 终止循环
          printRouter(prev, s, t);
          return;
        }
        queue.add(c);
      }
    }
  }
}
private void printRouter(int[] prev, int start, int target){
  if(prev[target] != -1 && target != start){
    //继续打印 start 到 target之前1个元素的路径
    printRouter(prev, start, prev[target]);
  }
  //打印当前元素
  System.out.println("当前元素:" + target);
}

广度优先搜索算法的时间复杂度,空间复杂度:
- 时间复杂度是O(V+E)
  - V表示顶点的个数,E表示边的个数
  - 对于1个连通图.即一个图中所有的顶点都是连通的图,E肯定大于V
  - 所以广度优先搜索算法的时间复杂度简写为O(E)
- 空间复杂度的O(V)
  - visited 数组,prev 数组,queue队列,这三个存储空间大小都不会超过顶点个数V.
  - 所以其空间复杂度是O(V).

深度优先搜索 / DFS / Depth-First-Search

深度优先搜索算法,本质上就是回溯算法
每一步,都要n种走法,每一种走法都走一遍
回溯算法的套路

1: 整体问题最终值 存放在回溯方法体外;
2: 回溯方法中有判断终止条件 及 整体问题最终值修改逻辑;
3: 回溯方法中:
每一步都有n种走法;
都走一遍;

套路:
int bestValue = -1;
private void recur(int param, int bound){
  if(shouldReturn(param, bound)){
    if(shouldModifBest(param,bound)){
      bestValue = **;
    }
    return;
  }
  //n种走法
  recur(p1,bound);
  ***
  recur(pn,bound);
}

调用方式:
int bestValue = -1;
recur(p1.bound);
sys: 最优解: + bestValue.

使用深度优先搜索算法寻找顶点s到顶点t的路径

private boolean found = false;
private void recurDfs(int curr, int target, boolean[] visited, int[] prev){
  if(found){
    //之前已经找到路径,避免重复执行
    //终止条件
    return;
  }
  visited[curr] = true;
  if(curr == target){
    //终止条件
    //修改方法体外的变量
    found = true;
    return;
  }
  //获取n条可能走的路径
  for(int i=0; i<adj[curr].size(); i++){
    int c = adj[curr].get(i);
    if(!visited[c]){
      //之前没有遍历过该子顶点
      prev[c] = curr;
      //每一条可以走的路径,都走一次
      recurDfs(c, target, visited,prev);
    }
  }
}
private testDFS(int s, int t){
  found = false;
  boolean[] visited = new boolean[v];
  int[] prev = new int[v];
  for(int i=0;i<v;i+){
    prev[i] = -1;
  }
  //回溯算法
  recurDfs(s, t, visited, prev)
  //打印路径
  printRouter(prev, s, t);
}

深度优先搜索算法/回溯算法的时间复杂度和空间复杂度
- 遍历 + 回溯, 每条边最多访问2次: parent -> n个child; 每个child -> 包括parent在内的n个顶点.
- 时间复杂度是O(E). E是边数量
- 空间复杂度是O(V). 因为额外的visited ,prev 数量不超过V.

43. | 拓扑排序：如何确定代码源文件的编译依赖关系 - 继续

public class Graph{
  private int v;
  private LinkedList<Integer>[] adj;
  public Graph(int v){
    this.v = v;
    this.adj = new LinkedList<Integer>[v];
    for(int i=0;i<v;i++){
      adj[i] = new LinkedList<Integer>();
    }
  }
  //添加从顶点s到顶点t的一条边
  //因为是依赖关系,所以是有向图
  public void addEdge(int s, int t){
    adj[s].add(t);
  }
}

如何在有向无环图上,实现拓扑排序.
拓扑排序有2种实现方法: Kahn算法及 DFS深度优先搜索算法.

Kahn算法

Kahn算法实际用的是贪心算法思想
顶点的入度为0,说明该顶点不依赖任何其他顶点,可以立即执行.
Kahn实现步骤:
- 定义1个数组,统计图中所有顶点的入度,存储于该数组
- 定义1个队列,存储图中所有入度为0的顶点
- 从队列头部不断取入度为0的顶点,执行/打印.
  - 将该顶点对应的所有子顶点的入度-1
  - 若某个子顶点的入度变为0,则将该子顶点也加入队列
Kahn代码实现

public void topoSortByKahn(){
  int[] inDegree = new int[v];
  for(int i = 0; i<v; i++){
    for(int j=0;j<adj[i].size();j++){
      int curr = adj[i].get(j);
      inDegree[curr]++;
    }
  }
  Queue<Integer> q = new LinkedList<Integer>();
  for(int i=0;i<v;i++){
    if(inDegree[i] == 0){
      q.add(i);
    }
  }
  int curr;
  int child;
  while(!q.isEmpty()){
    curr = q.poll();
    System.out.println("当前编译:" + curr);
    for(int i=0;i<adj[curr].size();i++){
      //遍历当前顶点的所有子顶点
      child = adj[curr].get(i);
      //每个子顶点的入度-1
      inDegree[child ]--;
      //若子顶点入度变为0
      if(inDegree[child] == 0){
        q.add(child);
      }
    }
  }
}

DFS算法

DFS算法本质上是回溯算法
原始数据是顶点->多个子顶点
要答应整个依赖关系,需要知道每个顶点都依赖哪些父顶点, 根据原始的 curr->children 构建逆邻接表 curr->parents
每次打印1个顶点,都要先保证其 parents 都打印完毕,再打印自身.
DFS代码实现

public void dfsDeps(){
  boolean[] visited = new boolean[v];
  LinkedList<Integer>[] parents = new LinkedList<Integer>[v];
  for(int i =0;i<v;i++){
    parents[i] = new LinkedList<Integer>();
  }
  int child;
  for(int i=0;i<adj.length;i++){
    for(int j=0;j<adj[i].size();j++){
      child = adj[i].get(j);
      parents[child].add(i);
    }
  }
  //遍历parents,将每个顶点都打印一遍
  for(int i=0;i<v;i++){
    if(!visited[i]){
      printCurr(i,visited,parents);
    }
  }
}
private void printCurr(int curr,boolean[] visited,LinkedList<Integer>[] parents){
  if(visited[curr]){
    return;
  }
  //标记当前顶点已访问过
  visited[curr] = true;
  int parent;
  //获取当前顶点所有父顶点
  for(int i =0; i<parents[curr].size(); i++){
    parent = parents[curr].get(i);
    //打印父顶点
    printCurr(parent,visited,parents);
  }
  //所有父顶点打印完毕,再打印自身
  sysout: 当前编译项为: + curr;
}

kahn算法的时间复杂度O(E+V)/每个顶点被访问1次,每条边也被访问1次, Kahn的空间复杂度O(V);
DFS算法的空间复杂度是O(V),时间复杂度是O(E+V)/每个顶点被访问2次,每条边被访问1次.

每个顶点被访问2次: curr -> parents; parent -> parents;

拓扑排序的应用场景: 凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决.
检测图中是否存在环:
6.1: Kahn算法,如果最终打印的顶点个数数量少于顶点总量,说明图中成环,部分顶点始终无法达到入度为0
6.2: 如果是A推荐B,B推荐C,C推荐D,D推荐E,E又推荐A这样的环状结构,如何检测.
只要从A开始向下递推,每个访问过的人都记录下来,如果成环,同1个人会被访问2次.
A->B->C->D->E->A.
只要记录中出现1个人被访问2次,说明成环了.

private HaseSet<Integer> visited = new HashSet<Integer>();
private int findFinalRef(int userId){
  if(visited.contains(userId)){
    //说明同一用户被访问第2次,说明出现了环状结构
    return;
  }
  int refId = gainCurrUserRef(userId);
  if(refId == -1){
    //说明当前userId没有下一个推荐人,则返回自身
    return userId;
  }
  return findFinalRef(refId);
}

44. | 最短路径：地图软件是如何计算出最优出行路径的

Dijkstra算法相关文章

计算地图上两个地点的最优路径,可以将地图抽象成'图'这种结构.每个地点是图的1个顶点.两个地点之间的路是一条边,单向路就是A->B,双向路就是 A->B + B->A.
路的长度,就是每条边的权重.
地图就被抽象成1个有向有权图.
地图中两个地点的最短路径,变成有向有权图中2个顶点间的最短距离.
将地图抽象成图的代码

public class Graph{
  //邻接表
  private LinkedList<Edge>[] adj;
  //顶点个数
  private int v;
  public Graph(int v){
    this.v = v;
    this.adj = new LinkedList<Edge>[v];
    for(int i =0;i<v;i++){
      adj[i] = new LinkedList<Edget>();
    }
  }
  //添加一条边. 从s到t.
  public void addEdge(int s,int t, int w){
    this.adj[s].add(new Edge(s, t, w));
  }
  private class Edge{
    public int sid; //边的起始顶点编号
    public int tid; //边的终止顶点编号
    public int w; //边的权重
    public Edge(int sid, int tid, int w){
      this.sid = sid;
      this.tid = tid;
      this.w = w;
    }
  }
  //这个类专门为dijkstra算法实现的
  private class Vertex{
    //顶点id
    public int id;
    //从起始顶点 到这个顶点的 最短距离
    public int dist;
    public Vertex(int id, int dist){
      this.id = id;
      this.dist = dist;
    }
  }
}

一个顶点到另一个顶点的最短路径算法,最著名的是Dijkstra算法.

Dijkstra算法实现

//Java提供的优先级队列,没有提供更新单个元素的接口,所以需要自行实现1个
private class PriorityQueue{
  //需要根据Vertex.dist构建小顶堆
  private Vertex[] nodes;
  private int count;
  private PriorityQueue(int v){
    this.nodes = new Vertex[v + 1];
    this.count = v;
  }
  //待实现
  public Vertex poll(){}
  //待实现
  public void add(Vertex vertex){
  }
  //待实现: 更新结点的值,并且从下往上堆化, 使之重新符合小顶堆的定义
  public void update(Vertex vertex){
  }
  //待实现
  public boolean isEmpty(){
  }
}

//dijkstra算法实现
public void dijkstra(int s,int t){
  int[] pre = new int[v];
  Vertex[] vertexes = new Vertex[v];
  for(int i=0;i<v;i++){
    vertexes[i] = new Vertex(i,Integer.MAX_VALUE);
  }
  PriorityQueue queue = new PriorityQueue(v);
  boolean[] inqueue = new boolean[v];
  queue.add(vertexes[s]);
  inqueue[s] = true;
  while(!queue.isEmpty()){
    Vertex minVertex = queue.poll();
    if(minVertex.id == t){
      break;
    }
    for(int i=0;i<adj[minVertex.id].size();i++){
      Edge e = adj[minVertex.id].get(i);
      Vertex nextVertex = vertexes[e.tid];
      if(minVertex.dist + e.w < nextVertex.dist){
        nextVertex.dist = minVertex.dist + e.w;
        pre[nextVertex.id] = minVertex.id;
        if(inqueue[nextVertex.id]){
          queue.update(nextVertex);
        }else{
          queue.add(nextVertex);
          inqueue[nextVertex.id] = true;
        }
      }
    }
  }
  System.out.println("从s到t最短路径长度:" + vertexes[t].dist);
  //依次答应最短路径长度对应的每个顶点
  print(s, t, pre);
}
private void print(int s, int t, int[] pre){
  if(s == t){
    System.out.println("当前元素:" + t);
    return;
  }
  print(s, pre[t], pre);
  //打印t
  System.out.println("当前元素:" + t);
}

Dijkstra的时间复杂度

while循环次数: 最多是V次, V代表顶点的个数.
while循环内,每次for循环次数不同,V次总体for循环次数 <= E. E是图中边的数量.
优先级队列是1个小顶堆,每次poll,add或update,时间复杂度是O(logV)
整个Dijkstra的时间复杂度是 O(E*logV)

地图软件用的更多的是类似 A* 的启发式搜索算法，不过也是在 Dijkstra 算法上的优化.

45 | 位图：如何实现网页爬虫中的URL去重功能？

前置知识

位运算