топологического порядка с использованием BFS

Question

Следующий вопрос был найден в Sedgewick и Уэйн книги об алгоритмах в Java:

4.2.19 топологическую сортировку и BFS. Объясните, почему следующий алгоритм не обязательно создает топологический порядок: запустите BFS и пометьте вершины, увеличив расстояние до их соответствующего источника.

Я пытался доказать, что нашел встречный пример. Но каждый раз, когда я пытаюсь, я получаю топологический порядок. Я имею в виду, я не понимаю, почему это не работает: если источник вершины приходит перед ним, почему бы нам не иметь топологический порядок?

Я думаю, чтобы доказать это, нам нужно найти вершину, к которой он пришел раньше, но я не мог.

У кого-нибудь есть контрпример? Заранее спасибо!

PS: это не домашнее задание

@Edit: Я попробовал гамильтонов путь, как 1 < - 2 < - 0 < - 3 < - 4, что дает 0 3 4 2 1 , но изменение позиций 0 3 и 4 дает мне топологический порядок (но в том порядке, в котором я получил, это не так). Тогда я не уверен, что это или нет топологический порядок.

Answer 1

Вы не можете использовать BFS, потому что узел с более высоким рангом может иметь край инцидента с более низким рангом. Вот пример:

Предположим, вы запустили BFS у источника (A).

С предложенным алгоритмом узел D приходил к узлу C, что явно не является топологическим порядком. Вам действительно нужно использовать DFS.

Answer 2

Counter-пример:

A -> B 
A -> C 
B -> C 

BFS, начиная с A может найти узлы в порядке A-B-C или A-C-B, но только один из них является топологическим рода.

Answer 3

Да, вы можете сделать топологическую сортировку используя BFS. На самом деле я вспомнил, как только мой учитель сказал мне, что если проблема может быть решена с помощью BFS, никогда не решите ее решить DFS. Поскольку логика для BFS проще, чем DFS, большую часть времени вы всегда будете нуждаться в прямом решении проблемы.

Вы должны начать с узлами которого полустепень захода является , то есть никакие другие узлы не непосредственно к ним. Обязательно сначала добавьте эти узлы к вашему результату. Вы можете использовать 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; 
}