Как получить все узлы в пути из первого поиска по ширине графа - PullRequest
Новая
       40

Как получить все узлы в пути из первого поиска по ширине графа

0 голосов
/ 23 мая 2018

Предположим, у нас есть простой график, подобный следующему:

enter image description here

Было легко найти путь от начального узла до конечного узла с глубиной-первымпоиск, но я застрял, пытаясь сделать то же самое с поиском в ширину.Мой код выглядит следующим образом: 

public List<String> getPathBreadth(String name1, String name2) {
    Node node1 = getNode(name1);
    Node node2 = getNode(name2);
    if (node1 == null || node2 == null) {
        return null;
    }
    return getPathBreadth(node1, node2, new HashSet<String>(), new LinkedList<Node>());
}

private List<String> getPathBreadth(Node start, Node destination, HashSet<String> visited, Queue<Node> queue) {
    List<String> path = new ArrayList<String>();
    if (start == destination) {
        path.add(start.name);
        return path;
    }
    visited.add(start.name);
    queue.offer(start);
    while (queue.size() > 0) {
        Node cur = queue.poll();
        for (String friend : cur.friends) {
            if (visited.contains(friend)) {
                continue;
            }
            visited.add(friend);
            if (getNode(friend) == destination) {
                path.add(friend); // I got the final node, I could also add cur, but how do I get the previous nodes along the path
                return path;
            }
            queue.offer(getNode(friend));
        }
    }
    return path;
}

Предположим, мы хотим перейти от John к Linda, поэтому я хочу вернуть что-то вроде [Linda, Robert, John] или [Linda, Patrica, John], но лучшее, что я могу сделатьна данный момент это получить последний и второй до последних узлов.В этом случае они Linda и Robert.Как мне получить все предыдущие узлы по пути?

1 Ответ

0 голосов
/ 24 мая 2018

Чтобы сделать код пригодным для использования, добавьте определение Node и дерево (тестовые данные).(см. mcve ).Я думаю, что проблема здесь: 

if (getNode(friend) == destination) {
                path.add(friend); 
                return path;
 }

Единственный узел, который вы добавили к пути в последнем.Попробуйте: 

path.add(friend);     
if (getNode(friend) == destination) {                
     return path; //or better: break;
}

К сожалению, я не могу запустить и проверить его.

Примечание:visited.add(friend) Возвращает true, если в этом наборе еще не было другаитак: 

if (visited.contains(friend)) {
   continue;
}
visited.add(friend);

можно заменить на 

 if (! visited.add(friend)) {
     continue;
 }
...