トポロジーの順序付けの2種類の実現DFSと減一思想

package com.dugstudio.practiceBook;

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

/**
 * @Author JH
 * @CreateDate 18-6-7
 * @Description               ，             
 */
public class TopologicSort {
    /**
     *      DFS  
     * @param vertex   
     * @param edges         
     */
    private static List seril=new ArrayList();
    public void topoSortByDFS(int [] vertex,int[][] edges){

        boolean [] isVisited =new boolean[vertex.length];
        Stack stack =new Stack();
        for (int i=0;iboolean flag=false;
            for (int j=0;jif (edges[j][i]!=0){
                    flag=true;
                    break;
                }
            }//        
            if (flag==false){
                stack.push(vertex[i]);
                isVisited[vertex[i]]=true;
                topoSort(stack,vertex,isVisited,edges);
            }
        }
    }

    /**
     * DFS        ，       ，       ，      
     * @param stack
     * @param vertex
     * @param isVisited
     * @param edges
     */
    private void topoSort(Stack stack, int[] vertex, boolean[] isVisited, int[][] edges) {
            if (stack.isEmpty())return;
            while (!stack.isEmpty()){
                int i=0;
                for (;iif (!isVisited[i]&&edges[stack.peek()][i]!=0){
                        stack.push(vertex[i]);
                        isVisited[i]=true;
                        topoSort(stack,vertex,isVisited,edges);
                        break;
                    }
                }
                if (i==vertex.length){
                    seril.add(stack.pop());
                }
            }

    }

    /**
     *            ，         
     * @param vertex   
     * @param edges   
     */
    public void topoSortBySub(int [] vertex,int[][] edges){
        boolean [] isVisited =new boolean[vertex.length];
        for (int i=0;iboolean flag=false;
            for (int j=0;jfalse;j++){
                if (edges[j][i]!=0){
                    flag=true;
                    break;
                }
            }
            if (flag==false&&isVisited[vertex[i]]==false){
                seril.add(vertex[i]);
                isVisited[vertex[i]]=true;
                for (int k=0;k0;
                    edges[k][i]=0;
                }

                i=-1;
            }
        }
    }
    public static void main(String[] args) {
        int [] vertex={0,1,2,3,4,5};
        int [][] matrix={
                {0,0,1,0,0,0},
                {0,0,1,0,0,0},
                {0,0,0,1,1,1},
                {0,0,0,0,1,0},
                {0,0,1,0,0,0},
                {0,0,0,0,0,0}
        };
        int [] vertex1={0,1,2,3,4,5,6};
        int [][] matrix1={
                {0,1,1,0,0,0,0},
                {0,0,0,0,1,0,1},
                {0,0,0,0,0,1,0},
                {1,1,1,0,0,1,1},
                {0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0},
                {0,0,0,1,1,1,0}
        };
        TopologicSort t=new TopologicSort();
        t.topoSortByDFS(vertex,matrix);
       // t.topoSortBySub(vertex,matrix);
        // t.topoSortByDFS(vertex1,matrix1);
        //t.topoSortBySub(vertex1,matrix1);
        System.out.println("    ：");
        System.out.println(seril);
        System.out.println("      ：");
        for(int i=seril.size()-1;i>=0;i--){
            System.out.print(seril.get(i)+"  ");
        }
    }

}