图的拓扑排序算法

1. 在图中找到所有入度为 0 的点输出
2. 把所有入度为 0 的点在图中删掉，继续找入度为 0 的点输出 周而复始
3. 图的所有点都被删除后，依次输出的顺序就是拓扑排序

题目 #

拓扑排序

给定一个有向图，图节点的拓扑排序定义如下:

对于图中的每一条有向边 A -> B , 在拓扑排序中 A 一定在 B 之前.拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.针对给定的有向图找到任意一种拓扑排序的顺序

class DirectedGraphNode {
  int label;
  List<DirectedGraphNode> neighbors;

  DirectedGraphNode(int x) {
    label = x;
    neighbors = new ArrayList<DirectedGraphNode>();
  }
}

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
  HashMap<DirectedGraphNode, Integer> indegreeMap = new HashMap<>();
  for (DirectedGraphNode cur : graph)
    indegreeMap.put(cur, 0);

  for (DirectedGraphNode cur : graph) {
    for (DirectedGraphNode next : cur.neighbors)
      indegreeMap.put(next, indegreeMap.get(next) + 1);

  }
  Queue<DirectedGraphNode> zeroQueue = new LinkedList<>();
  for (DirectedGraphNode cur : indegreeMap.keySet()) {
    if (indegreeMap.get(cur) == 0)
      zeroQueue.add(cur);
  }

  ArrayList<DirectedGraphNode> ans = new ArrayList<>();
  while (!zeroQueue.isEmpty()) {
    DirectedGraphNode cur = zeroQueue.poll();
    ans.add(cur);
    for (DirectedGraphNode next : cur.neighbors) {
      indegreeMap.put(next, indegreeMap.get(next) - 1);
      if (indegreeMap.get(next) == 0)
        zeroQueue.offer(next);
    }
  }
  return ans;
}

思路二 DFS #

点次思想

public static class Record {
  public DirectedGraphNode node;
  public long nodes;

  public Record(DirectedGraphNode n, long o) {
    node = n;
    nodes = o;
  }
}

public static Record f(DirectedGraphNode cur, HashMap<DirectedGraphNode, Record> order) {
  if (order.containsKey(cur)) {
    return order.get(cur);
  }
  // cur的点次之前没算过！
  long nodes = 0;
  for (DirectedGraphNode next : cur.neighbors) {
    nodes += f(next, order).nodes;
  }
  Record ans = new Record(cur, nodes + 1);
  order.put(cur, ans);
  return ans;
}

public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
  HashMap<DirectedGraphNode, Record> order = new HashMap<>();
  for (DirectedGraphNode cur : graph) {
    f(cur, order);
  }
  ArrayList<Record> recordArr = new ArrayList<>();
  for (Record r : order.values()) {
    recordArr.add(r);
  }
  recordArr.sort((o1, o2) -> {
    return o1.nodes == o2.nodes ? 0 : (o1.nodes > o2.nodes ? -1 : 1);
  });
  ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();
  for (Record r : recordArr) {
    ans.add(r.node);
  }
  return ans;
}

思路三：（最优解） #

X 的最大深度大于 Y 则 X 的拓扑序小于 Y

 public static class Record {
  public DirectedGraphNode node;
  public int deep;

  public Record(DirectedGraphNode n, int o) {
    node = n;
    deep = o;
  }
}

public static Record f(DirectedGraphNode cur, HashMap<DirectedGraphNode, Record> order) {

  if (order.containsKey(cur)) {
    return order.get(cur);
  }
  int follow = 0;
  for (DirectedGraphNode next : cur.neighbors) {
    follow = Math.max(follow, f(next, order).deep);
  }
  Record ans = new Record(cur, follow + 1);
  order.put(cur, ans);
  return ans;
}

public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
  HashMap<DirectedGraphNode, Record> order = new HashMap<>();
  for (DirectedGraphNode cur : graph) {
    f(cur, order);
  }
  ArrayList<Record> recordArr = new ArrayList<>();
  for (Record r : order.values()) {
    recordArr.add(r);
  }
  recordArr.sort((o1, o2) -> {
    return o2.deep - o1.deep;
  });
  ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();
  for (Record r : recordArr) {
    ans.add(r.node);
  }
  return ans;
}