示例有向图和拓扑排序代码 [已关闭]

以下是维基百科页面上拓扑排序的第一个算法的简单实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

public class Graph {

  static class Node{
    public final String name;
    public final HashSet<Edge> inEdges;
    public final HashSet<Edge> outEdges;
    public Node(String name) {
      this.name = name;
      inEdges = new HashSet<Edge>();
      outEdges = new HashSet<Edge>();
    }
    public Node addEdge(Node node){
      Edge e = new Edge(this, node);
      outEdges.add(e);
      node.inEdges.add(e);
      return this;
    }
    @Override
    public String toString() {
      return name;
    }
  }

  static class Edge{
    public final Node from;
    public final Node to;
    public Edge(Node from, Node to) {
      this.from = from;
      this.to = to;
    }
    @Override
    public boolean equals(Object obj) {
      Edge e = (Edge)obj;
      return e.from == from && e.to == to;
    }
  }

  public static void main(String[] args) {
    Node seven = new Node("7");
    Node five = new Node("5");
    Node three = new Node("3");
    Node eleven = new Node("11");
    Node eight = new Node("8");
    Node two = new Node("2");
    Node nine = new Node("9");
    Node ten = new Node("10");
    seven.addEdge(eleven).addEdge(eight);
    five.addEdge(eleven);
    three.addEdge(eight).addEdge(ten);
    eleven.addEdge(two).addEdge(nine).addEdge(ten);
    eight.addEdge(nine).addEdge(ten);

    Node[] allNodes = {seven, five, three, eleven, eight, two, nine, ten};
    //L <- Empty list that will contain the sorted elements
    ArrayList<Node> L = new ArrayList<Node>();

    //S <- Set of all nodes with no incoming edges
    HashSet<Node> S = new HashSet<Node>(); 
    for(Node n : allNodes){
      if(n.inEdges.size() == 0){
        S.add(n);
      }
    }

    //while S is non-empty do
    while(!S.isEmpty()){
      //remove a node n from S
      Node n = S.iterator().next();
      S.remove(n);

      //insert n into L
      L.add(n);

      //for each node m with an edge e from n to m do
      for(Iterator<Edge> it = n.outEdges.iterator();it.hasNext();){
        //remove edge e from the graph
        Edge e = it.next();
        Node m = e.to;
        it.remove();//Remove edge from n
        m.inEdges.remove(e);//Remove edge from m

        //if m has no other incoming edges then insert m into S
        if(m.inEdges.isEmpty()){
          S.add(m);
        }
      }
    }
    //Check to see if all edges are removed
    boolean cycle = false;
    for(Node n : allNodes){
      if(!n.inEdges.isEmpty()){
        cycle = true;
        break;
      }
    }
    if(cycle){
      System.out.println("Cycle present, topological sort not possible");
    }else{
      System.out.println("Topological Sort: "+Arrays.toString(L.toArray()));
    }
  }
}

我基于维基百科页面上的第二个替代方案进行了实现：http://en.wikipedia.org/wiki/Topological_sorting

public class Graph {

    Hashtable<Node, ArrayList<Node>> adjList = new Hashtable<Node, ArrayList<Node>>();
    ArrayList<Node> nodes = new ArrayList<Node>();
    LinkedList<Node> topoSorted;

    public Graph() {}

    public void add(Node node) { 
        if (adjList.contains(node)) { 
            return;
        } else { 
            adjList.put(node, new ArrayList<Node>());
            nodes.add(node);
        }
    }

    public void addNeighbor(Node from, ArrayList<Node> list) { 
        for (Node to: list) { 
            addNeighbor(from, to);
        }
    }

    public void addNeighbor(Node from, Node to) { 
        if (!adjList.containsKey(from)) { 
            add(from);
        }
        if (!adjList.containsKey(to)) { 
            add(to);
        }
        adjList.get(from).add(to);
        to.inDegree++;
        to.inNodes.add(from);
    }

    public void remove(Node node) { 
        for (Node n: nodes) { 
            for (Node x: adjList.get(n)) { 
                if (x.equals(node)) removeNeighbor(n, x);
            }
        }
        adjList.remove(node);
        nodes.remove(node);
    }

    public void removeNeighbor(Node from, Node to) { 
        adjList.get(from).remove(to);
        to.inDegree--;
        to.inNodes.remove(from);
    }

    public void resetVisited() { 
        for (Node node: nodes) { 
            node.visited = false;
        }
    }

    public boolean hasEdge(Node from, Node to) { 
        return adjList.get(from).contains(to) ? true : false;
    }

    /**
     * for DAGS only
     * @throws Exception
     */
    public void topologicalSort() throws Exception { 
        /* L <-- Empty list that will contain the sorted elements */
        topoSorted = new LinkedList<Node>();

        /* Use set to keep track of permanently visited nodes
         * in constant time. Does have pointer overhead */
        HashSet<Node> visited = new HashSet<Node>();

        /* while there are unmarked nodes do */
        for (Node n: nodes) { 

            /* select an unmarked node n
             * visit(n)
             */
            if (!visited.contains(n)) visit(n, visited);
        }
    }

    /* function: visit(node n) */
    public void visit(Node node, HashSet<Node> set) throws Exception { 
        /* if n has a temporary mark then stop (not a DAG) */
        if (node.visited) { 
            throw new Exception("graph cyclic");

        /* if n is not marked (i.e. has not been visited) then... */
        } else { 

            /* mark n temporarily [using boolean field in node]*/
            node.visited = true;

            /* for each node m with an edge n to m do... */
            for (Node m: adjList.get(node)) { 

                /* visit(m) */
                if (!set.contains(m)) visit(m, set);            
            }

            /* mark n permanently */
            set.add(node);

            /* unmark n temporarily */
            node.visited = false;

            /* add n to head of L */
            topoSorted.addFirst(node);
        }
    }

    public void printGraph() { 
        for (Node node: nodes) { 
            System.out.print("from: " + node.value + " |  to: ");
            for (Node m: adjList.get(node)) { 
                System.out.print(m.value + " ");
            }
            System.out.println();
        }
    }

    public void instantiateGraph() { 
        Node seven = new Node("7");
        Node five = new Node("5");
        Node three = new Node("3");
        Node eleven = new Node("11");
        Node eight = new Node("8");
        Node two = new Node("2");
        Node nine = new Node("9");
        Node ten = new Node("10");

        addNeighbor(seven, eleven);
        addNeighbor(seven, eight);
        addNeighbor(five, eleven);
        addNeighbor(three, eight);
        addNeighbor(three, ten);
        addNeighbor(eleven, two);
        addNeighbor(eleven, nine);
        addNeighbor(eleven, ten);
        addNeighbor(eight, nine);

        try {
            topologicalSort();
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        for (Node node: topoSorted) { 
            System.out.print(node.value + " ");
        }   
    }

    public class Node { 
        String value; 
        boolean visited = false;
        int inDegree = 0;
        ArrayList<Node> inNodes = new ArrayList<Node>();


        public Node (String value) { 
            this.value = value;
        }
    }

    public static void main(String[] args) { 
        Graph g = new Graph();
        g.instantiateGraph();
    }
}