Да, вы можете сделать топологическую сортировку, используя BFS. На самом деле я вспомнил, как только мой учитель сказал мне, что если проблема может быть решена BFS, никогда не решите ее решить DFS. Поскольку логика для BFS проще, чем DFS, большую часть времени вы всегда будете нуждаться в прямом решении проблемы.
Как YvesgereY и IVlad отметили, что вам нужно начать с узлами которого полустепень заход является , то есть никакие другие узлы не непосредственно к ним. Обязательно сначала добавьте эти узлы к вашему результату. Вы можете использовать HashMap для сопоставления каждого узла с его неопределенностью и очереди, которая очень часто встречается в BFS, чтобы помочь вашему обходу. Когда вы проводите опрос узла из очереди, его соседям нужно уменьшить на 1, это как удалить узел из графика и удалить границу между узлом и его соседями. Каждый раз, когда вы сталкиваетесь с узлами с индексом 0, предложите их очереди для проверки своих соседей позже и добавьте их в результат.
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> result = new ArrayList<>();
if (graph == null || graph.size() == 0) {
return result;
}
Map<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>();
Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
//mapping node to its indegree to the HashMap, however these nodes
//have to be directed to by one other node, nodes whose indegree == 0
//would not be mapped.
for (DirectedGraphNode DAGNode : graph){
for (DirectedGraphNode nei : DAGNode.neighbors){
if(indegree.containsKey(nei)){
indegree.put(nei, indegree.get(nei) + 1);
} else {
indegree.put(nei, 1);
}
}
}
//find all nodes with indegree == 0. They should be at starting positon in the result
for (DirectedGraphNode GraphNode : graph) {
if (!indegree.containsKey(GraphNode)){
queue.offer(GraphNode);
result.add(GraphNode);
}
}
//everytime we poll out a node from the queue, it means we delete it from the
//graph, we will minus its neighbors indegree by one, this is the same meaning
//as we delete the edge from the node to its neighbors.
while (!queue.isEmpty()) {
DirectedGraphNode temp = queue.poll();
for (DirectedGraphNode neighbor : temp.neighbors){
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0){
result.add(neighbor);
queue.offer(neighbor);
}
}
}
return result;
}
Да, это можно сделать. https://www.quora.com/Can-topological-sorting-be-done-using-BFS –