# 拓扑排序的两种实现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 ListInteger seril=new ArrayListInteger();
public void topoSortByDFS(int [] vertex,int[][] edges){

boolean [] isVisited =new boolean[vertex.length];
StackInteger stack =new StackInteger();
for (int i=0;ivertex.length;i++){
boolean flag=false;
for (int j=0;jvertex.length;j++){
if (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(StackInteger stack, int[] vertex, boolean[] isVisited, int[][] edges) {
if (stack.isEmpty())return;
while (!stack.isEmpty()){
int i=0;
for (;ivertex.length;i++){
if (!isVisited[i]edges[stack.peek()][i]!=0){
stack.push(vertex[i]);
isVisited[i]=true;
topoSort(stack,vertex,isVisited,edges);
break;
}
}
if (i==vertex.length){
}
}

}

/**
* 基于减一思想的拓扑排序，删除没有入边的源点
* @param vertex 点集
* @param edges 边集
*/
public void topoSortBySub(int [] vertex,int[][] edges){
boolean [] isVisited =new boolean[vertex.length];
for (int i=0;ivertex.length;i++){
boolean flag=false;
for (int j=0;jvertex.lengthisVisited[vertex[i]]==false;j++){
if (edges[j][i]!=0){
flag=true;
break;
}
}
if (flag==falseisVisited[vertex[i]]==false){
isVisited[vertex[i]]=true;
for (int k=0;kvertex.length;k++){
edges[i][k]=0;
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)+"  ");
}
}

}``````
• 02:07
• 01:37
• 01:14
• 02:26
• 01:23