1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 public class Node {
 5     // 序号
 6     public int no;
 7     // 后接节点列表
 8     public List<Node> nextList = new ArrayList<Node>();
 9     // 前接节点列表
10     public List<Node> preList = new ArrayList<Node>();
11     // 初始前必经节点（全体节点）
12     public List<Node> dominatorList = new ArrayList<Node>();
13 
14     public Node(int no) {
15         this.no = no;
16     }
17 
18     public void addNext(Node n){
19         nextList.add(n);
20         n.preList.add(this);
21     }
22     
23     public String toString(){
24         return no+"";
25     }
26 }

import java.util.ArrayList;
import java.util.List;


public class Dominator {

    public static void main(String[] args) {
        //初期化所有节点   并设置节点间连接关系
        List<Node> nodeList = getNodeList(12);
        // 计算前必经节点
        doDominator(nodeList);
        //打印必经节点列表
        printResult(nodeList);

    }

    // 打印必经结果
    public static void printResult(List<Node> nodeList) {
        for (int i = 0; i < nodeList.size(); i++) {
            Node node = nodeList.get(i);
            System.out.println("*******************");
            System.out.println("node" + (i + 1));
            printNodeListNo(node.dominatorList);
        }
    }
    
    //打印节点NO
    public static void printNodeListNo(List<Node> nodeList) {
        System.out.println("------");
        for (int i = 0; i < nodeList.size(); i++) {
            if (i != 0) {
                System.out.print(",");
            }
            System.out.print(nodeList.get(i).no);
        }
        System.out.println();
    }

    // 计算必经节点
    public static void doDominator(List<Node> nodeList) {
        //迭代次数
        int n = 1;
        //判断状态是否稳定Flag
        boolean changed = true;
        while (changed) {
            System.out.println("迭代次数:" + n++);
            changed = false;
            for (int i = 0; i < nodeList.size(); i++) {
                Node node = nodeList.get(i);
                List<Node> lastDominatorList = new ArrayList<Node>();
                lastDominatorList.addAll(node.dominatorList);
                List<Node> temList = new ArrayList<Node>();

                for (Node preNode : node.preList) {
                    List<Node> preDomList = preNode.dominatorList;
                    if (temList.isEmpty()) {
                        temList.addAll(preDomList);
                    } else {
                        temList.retainAll(preDomList);
                    }
                }
                temList.add(node);
                int lastSize = lastDominatorList.size();
                lastDominatorList.retainAll(temList);
                if (lastSize != lastDominatorList.size()) {
                    node.dominatorList = temList;
                    changed = true;
                }
            }
        }
    }



    //初期化所有节点   并设置节点间连接关系
    public static List<Node> getNodeList(int size) {
        List<Node> nodeList = new ArrayList<Node>(size);
        for (int i = 0; i < size; i++) {
            Node node = new Node(i + 1);
            nodeList.add(node);
        }
        Node node1 = nodeList.get(0);
        Node node2 = nodeList.get(1);
        Node node3 = nodeList.get(2);
        Node node4 = nodeList.get(3);
        Node node5 = nodeList.get(4);
        Node node6 = nodeList.get(5);
        Node node7 = nodeList.get(6);
        Node node8 = nodeList.get(7);
        Node node9 = nodeList.get(8);
        Node node10 = nodeList.get(9);
        Node node11 = nodeList.get(10);
        Node node12 = nodeList.get(11);
        // 节点之间关系设定
        node1.addNext(node2);
        //
        node2.addNext(node3);
        node2.addNext(node4);
        //
        node3.addNext(node2);
        //
        node4.addNext(node2);
        node4.addNext(node5);
        node4.addNext(node6);
        //
        node5.addNext(node7);
        node5.addNext(node8);
        //
        node6.addNext(node7);
        //
        node7.addNext(node11);
        //
        node8.addNext(node9);
        //
        node9.addNext(node8);
        node9.addNext(node10);
        //
        node10.addNext(node5);
        node10.addNext(node12);
        //
        node11.addNext(node12);
        //初期化前必经节点的列表
        for (int i = 0; i < nodeList.size(); i++) {
            nodeList.get(i).dominatorList.addAll(nodeList);
        }
        return nodeList;
    }

}