Có, bạn có thể thực hiện phân loại topo bằng cách sử dụng BFS. Thật ra tôi đã nhớ khi giáo viên nói với tôi rằng nếu vấn đề có thể được giải quyết bằng BFS, không bao giờ chọn giải quyết nó bằng DFS. Vì logic cho BFS đơn giản hơn DFS, phần lớn thời gian bạn sẽ luôn muốn có giải pháp đơn giản cho vấn đề.
Như YvesgereY và IVlad đã đề cập, bạn cần phải bắt đầu với các nút trong đó indegree là , có nghĩa là không có các nút khác chỉ đạo đối với họ. Hãy chắc chắn để thêm các nút này vào kết quả của bạn trước tiên.Bạn có thể sử dụng một HashMap để ánh xạ mọi nút với sự không rõ ràng của nó, và một hàng đợi rất thường thấy trong BFS để hỗ trợ truyền tải của bạn. Khi bạn thăm dò ý kiến một nút từ hàng đợi, sự chênh lệch của hàng xóm của nó cần phải được giảm xuống 1, điều này giống như xóa nút khỏi biểu đồ và xóa cạnh giữa nút và các nút lân cận. Mỗi khi bạn đi qua các nút với 0 không đồng ý, hãy cung cấp cho họ hàng đợi để kiểm tra hàng xóm của họ sau đó và thêm họ vào kết quả.
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;
}
Nguồn
2017-07-08 12:52:15
Có, nó có thể được thực hiện. https://www.quora.com/Can-topological-sorting-be-done-using-BFS –