拓扑排序（一）

以前不知道什么是拓扑排序，最近补充了一下知识才算是知道怎么回事。

概念如下：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

说起来比较复杂，其实应用很为广泛。比如生活中的一些事情都是拓扑排序的结果。

比如，早上吃饭前需要刷牙，洗脸，等等就可以表示成下图。

刷牙->吃饭

洗脸->吃饭

吃饭->上班

穿衣->上班

排序的结果就是 刷牙->洗脸->吃饭->穿衣->上班，这么一个过程。拓扑排序可以形象的表示各个子过程之间的关系。有了这个例子觉得编译器中依赖解析什么的都先对这些东西判断是否存在环吧。

package q1175;

import java.util.Scanner;
import java.util.Set;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Iterator;

/**
 * Author: Ethan(Baiyp) <br />
 * Date: 2015/7/9. <br />
 */
public class Main {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      while (in.hasNext()) {
         String input;
         input = in.next();

         int n = Integer.parseInt(input);
         input = in.next();
         int m = Integer.parseInt(input);
         input = in.next();
         int k = Integer.parseInt(input);
         input = in.next();
         int initValue = Integer.parseInt(input);

         Graph g = new Graph(n);

         g.init(k, initValue);

         while (m-- > 0) {
            input = in.next();
            int start = Integer.parseInt(input);
            input = in.next();
            int end = Integer.parseInt(input);
            g.insertEdge(new Edge().setStart(start).setEnd(end));
         }
         g.topoSort();
         System.out.println(g.getTotal());
      }
   }

   private static class Graph {
      private Map<Integer, Set<Edge>> edgeMap;
      private Map<Integer, Vertex> vertexMap;
      private int total;

      public Graph(int num) {
         total = 0;
         edgeMap = new HashMap<Integer, Set<Edge>>();
         vertexMap = new HashMap<Integer, Vertex>();
         for (int i = 1; i <= num; i++) {
            edgeMap.put(i, new HashSet<Edge>());
            vertexMap.put(i, new Vertex().setIndex(i).setWeight(0));
         }
      }

      public void insertEdge(Edge edge) {
         int index = edge.getEnd().getIndex();
         edgeMap.get(index).add(edge);
      }

      public void init(int key, int value) {
         vertexMap.get(key).setWeight(value);
      }

      public void topoSort() {
         for (int i = 0; i < vertexMap.size(); i++) {
            int temp = vertexMap.get(i + 1).getWeight();
            Set<Edge> set = edgeMap.get(i + 1);
            Iterator<Edge> iterator = set.iterator();

            while (iterator.hasNext()) {
               Edge e = iterator.next();
               temp += vertexMap.get(e.getStart().getIndex()).getWeight();
            }

            init(i + 1, temp);
            total += temp;
         }
      }

      public int getTotal() {
         return total;
      }
   }

   /**
    * Directed Edge
    */
   private static class Edge {
      private Vertex start;
      private Vertex end;

      public Edge setStart(int start) {
         this.start = new Vertex().setIndex(start).setWeight(0);
         return this;
      }

      public Edge setEnd(int end) {
         this.end = new Vertex().setIndex(end).setWeight(0);
         return this;
      }

      public Vertex getStart() {
         return start;
      }

      public Vertex getEnd() {
         return end;
      }
   }

   private static class Vertex {
      private int index;
      private int weight;

      public int getIndex() {
         return index;
      }

      public Vertex setIndex(int index) {
         this.index = index;
         return this;
      }

      public int getWeight() {
         return weight;
      }

      public Vertex setWeight(int weight) {
         this.weight = weight;
         return this;
      }
   }
}

其中的Edge为一条边，为有向边，整个图也是通过对边的映射，对顶点的映射来完成。其中顶点中包含的weight就是拓扑排序中的权重，只需要在写一个compareTo接口，就可以使用泛型针对其进行排序了。

图中对边的索引为通过结束顶点来对边进行索引，因为有向边的结束顶点的权重为其起始顶点的权重之和。