Мне нравится знать, что моя текущая реализация топологической сортировки с использованием DFS в ориентированном графе верна. Я использовал 2d массив для представления графика и дек для стека. Пожалуйста, поделитесь своими знаниями со мной, поскольку я все еще изучаю теорию графов, коды следующие:
public void topSort (int[][] edges)
{
HashSet<Integer> visited = new HashSet<>();
ArrayDeque<Integer> deque = new ArrayDeque();
for (int i:edges[0] ) {
if(visited.add(i))
deque.add(i);
}
for (int i:edges[1] ) {
if(visited.add(i))
deque.add(i);
}
while (!deque.isEmpty())
{
System.out.print(deque.removeFirst() +" ");
}
}
public static void main(String[] args) {
//edge list
int [][] edgeList={
{1,1, 2,2, 4,4},
{2, 4,3,4,3,5 }
};
TopologicalSort ts = new TopologicalSort();
ts.topSort(edgeList);
}
}