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

2021-05-12  本文已影响0人  幻海流心

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

  1. 编译器如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序：
    使用 '图' 这种数据结构的 '拓扑排序算法' 解决.
  2. 什么是拓扑排序
  1. 拓扑排序的原理很简单,重要的是拓扑排序的实现.
  2. 如何确定代码源文件的编译依赖关系:
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);
  }
}
  1. 如何在Graph这个有向无环图上,实现拓扑排序,有2种算法: Kahn算法 和 DFS深度优先搜索算法.
  2. 看Kahn算法 和 DFS深度优先搜索算法 之前,首先回顾下之前的'图'相关知识.

43前置知识: 图

  1. 图
  1. 带权图
  1. 图的存储方法: 邻接矩阵 和 邻接表.
  2. 使用 邻接矩阵 存储图
$$\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}

  1. 使用 邻接表 存储图


    使用邻接表存储图
  1. 使用图,存储微博的用户之间关系
    针对微博用户关系，假设我们需要支持下面这样几个操作：判断用户 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)。
  //最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效
}
  1. 深度优先搜索算法 和 广度优先搜索算法 , 都是基于 '图' 这种数据结构.
  2. 广度优先搜索/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);
  }
}

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);
}
  1. 深度优先搜索 / DFS / Depth-First-Search
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.

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);
}

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深度优先搜索算法.

  1. 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);
      }
    }
  }
}
  1. 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;
}
  1. kahn算法的时间复杂度O(E+V)/每个顶点被访问1次,每条边也被访问1次, Kahn的空间复杂度O(V);
  2. DFS算法的空间复杂度是O(V),时间复杂度是O(E+V)/每个顶点被访问2次,每条边被访问1次.
  1. 拓扑排序的应用场景: 凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决.
  2. 检测图中是否存在环:
    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. | 最短路径：地图软件是如何计算出最优出行路径的

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

  1. 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);
}
  1. Dijkstra的时间复杂度
  1. 地图软件用的更多的是类似 A* 的启发式搜索算法，不过也是在 Dijkstra 算法上的优化.

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

前置知识

  1. 位运算
上一篇下一篇

猜你喜欢

热点阅读