Cracking Coding Interview - 4.7 Build Order

Build Order: You are given a list of projects and a list of dependencies (which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

EXAMPLE

1
2
3
4


Input:
projects:      a, b, c, d, e, f
dependencies: (a, d), (f, b), (b, d), (f, a), (d, c) 
Output:        f, e, a, b, d, c

Hints: #26, #47, #60, #85, #125, #133

解法1（有bug）

这个题目可以认为是一张有向不循环的图，我们可以利用dependencies信息构建一个图，然后利用BFS（广度优先）的方法遍历这张图。

这张图的合法性其实在于是否出现循环，我们可以在遍历的时候判断是否某个节点出现两次来判断。

构建图的难点：

如何确定root节点
如何添加边

顺带一提，root节点不只1个，例子中f和e都是root节点

确定root节点的方式比较简单，如果这个节点没有指向它的边，那么它就是root

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


public class Node {
  private char project;
  private boolean referenced; // 是否有边指向它自己
  private List<Node> adjacents = new ArrayList<>();
  private boolean marked;     // BFS时用
}

public class Dependency {
  private char from;
  private char to;
}

public char[] buildOrder(char[] projects, Dependency[] dependencies) {
  List<Node> nodes = buildNodes(projects);
  buildGraph(nodes, dependencies);
  List<Node> roots = findRoots(nodes);
  if (roots.isEmpty()) {
    throw new IllegalException("circular dependencies");
  }
  return bfsTraverse(roots, projects.length);
}

// O(n)
private List<Node> buildNodes(char[] projects) {
  List<Node> res = new ArrayList<>();
  for (char p : projects) {
    res.add(new Node(p));
  }
  return res;
}

// O(n)
private void buildGraph(List<Node> nodes, Dependency[] dependencies) {
  Map<Char, Node> nodeMap = buildNodeMap(nodes);
  for (Dependency dep : dependencies) {
    Node from = nodeMap.get(dep.from);
    Node to = nodeMap.get(dep.to);
    to.referenced = true;
    from.adjacents.add(to);
  }
}

// O(n)
private List<Node> findRoots(List<Node> nodes) {
  List<Node> res = new ArrayList<>();
  for (Node n : nodes) {
    if (!n.referenced) {
      res.add(n);
    }
  }
  return res;
}

// 如果每个节点指向所有其他节点，那么复杂度是O(n^2)
// 如果图退化为链表，那么复杂度是O(n)
private char[] bfsTraverse(List<Node> nodes, int total) {
  List<Node> current = nodes;  
  char[] res = new char[total];
  int index = 0;
  while (!current.isEmpty()) {
    List<Node> next = new ArrayList<>();
    for (Node n : current) {
      res[index++] = n.project;
      if (n.marked) {
        throw new IllegalException("circular dependency: " + res);
      }
      n.marked = true;
      for (Node a : node.adjacents) {
        next.add(a);
      }
    }
    current = next;
  }
  return res;
}

如果遇到下面这种情况（都是从上往下的箭头），解法1存在bug：

1
2
3
4
5
6
7


      f
     /|\
    c | d
     \|/|
      a |
      |/
      e

正确的顺序应该是f、c、d、a、e，但是解法1采用广度优先，因此会变成f、c、a、d、e。造成这个错误的原因是没有判断某个节点的所有父节点是否都构建过了

解法2

A -> B 的意思是 B 依赖 A

找不依赖别人的节点，先构建它们
删掉它们到下级节点对它们的依赖（因为已经构建过了，那么这个依赖可以不需要了）
在它们的下级节点里重复1、2步骤

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83


public class Graph {
  private Map<String, Project> projectMap = new HashMap<>();
  private List<Project> nodes = new ArrayList<>();
  
  public void addProject(String name) {
    if (!projectMap.containsKey(name)) {
      Project p = new Project(name);
      nodes.add(p);
      nodes.put(name, p);
    }
  }
  public void addEdge(Edge edge) {
    Project from = nodes.get(edge.from);
    Project to = nodes.get(edge.to);
    if (from == null || to == null) {
      throw new RuntimeException();
    }
    from.addNeighbor(to);
  }
  public List<Project> getNodes() { ... };
}

public class Project {
  private Map<String, Project> projectMap = new HashMap<>();
  private List<Project> neighbors = new ArrayList<>();
  private String name;
  private int deps = 0;  // 自己依赖多少个其他项目
  public Project(String name) {
    this.name = name;
  }
  public void addNeighbor(Project p) {
    if (!projectMap.containsKey(p.name)) {
      projectMap.put(p.name, p);
      neighbors.add(p);
      p.incrementDeps();
    }
  }
  public void incrementDeps() {
    this.deps++;
  }
  public void decrementDeps() {
    this.deps--;
  }
  public List<Project> getNeighbors() { ... }
}

public class Edge {
  private String from;
  private String to;
}

public Project[] buildOrder(String[] projectNames, Edge[] edges) {
  Graph graph = buildGraph(projectNames);
  buildEdges(graph, edges); 
  
  Project[] order = new Project[projects.length];
  int end = projectOrder(order, projects, 0);
  int index = 0;
  while (index < order.length) {
    Project current = order[index];
    /* We have a circular dependency since there are no remaining projects with
     * zero dependencies. */
    if (current == null) {
      return null;
    }
    for (Project c : current.adjacents) {
      c.decrementDeps();
    }
    end = projectOrder(order, current.adjacents, end);
    index++;
  }
  
  return order;
}

private int projectOrder(Project[] projectOrder, List<Project> projects, int end) {
  for (Project p : projects) {
    if (p.deps == 0) {
      projectOrder[end++] = p;
    }
  }
  return end;
}

时间复杂度：O(P+D)，P是项目数，D是依赖数（在构建依赖的时候所用的循环）。

解法3

解法2只能发现有循环依赖，无法告诉循环到底是什么。

采用深度优先的方法（DFS）来做。

构建链条的是这样的：parent parent -> parent -> leaf（叶子节点，不被别人依赖的项目）
每次构建的时候都是把parent插入到child之前。
在处理这个节点前做一个标记，表示正在处理，当处理一个节点的时候发现它正在处理，那么就说明它处于一个循环中。
当发现这个节点已经处理过了，那么就跳过。

可以从任意节点开始处理，因为第4点保证了不会重复处理，第2点则保证了parent肯定在child之前。

看这个例子（所有箭头都是从上往下）：

1
2
3
4
5
6
7


      f         d
     /|\        |
    c | b       g
     \|/|\
      a | h
      |/
      e

比如我们先处理b：

1
2
3
4
5
6
7
8


DFS(b)
  DFS(h)
    build order = ..., h
  DFS(a)
    DFS(e)
      build order = ..., e, h
    build order = ..., a, e, h
  build order = ..., b, a, e, h

然后我们处理f：

1
2
3
4
5
6
7
8


build order = ..., b, a, e, h
DFS(f)
  DFS(c)
    DFS(a) skip
    build order = ..., c, b, a, e, h
  DFS(a) skip
  DFS(B) skip
  build order = ..., f, c, b, a, e, h

代码：

 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


public class Project {
  String name;
  List<Project> adjacents = new ArrayList<>();
}

public void buildOrder(List<Project> projects) {
  
  LinkedList<Project> order = new LinkedList<>();
  for (Project p : projects) {
    buildOrder(p, order);
  }
  return order;
}

private void buildOrder(Project project, LinkedList<Project> order) {
  if (project.isVisiting) {
    // 发现循环依赖
    order.insertFirst(project);
    throw new RuntimeException("Cyclic depedencies: " + order);
  }
  if (project.isCompleted) {
    // 该项目已经处理过了
    return;
  }
  project.isVisiting = true;
  for (Project c : p.adjacents) {
    buildOrder(c, order);
  }
  order.insertFirst(project);
  project.isFinished = true;
}

Cracking Coding Interview - 4.7 Build Order

解法1（有bug）

解法2

解法3

版权

评论

Cracking Coding Interview - 4.7 Build Order

解法1（有bug）

解法2

解法3

版权

相关文章

评论