график дружбы BFS

Question

поиск кратчайшего пути в неориентированном графе с использованием BFS. Я создаю график дружбы с именами людей и с которыми они дружат. Метод, который я пытаюсь реализовать, - это кратчайший ввод от человека к человеку через друзей. Я не знаю, с чего начать с BFS. Мне нужен совет или код seudo или что-нибудь, что поможет мне начать. Я знаю, для BFS мне нужна очередь, но на самом деле не так, как и с чего начать .. Вводимые данные представляют собой два имени людей, и мне нужно использовать BFS, чтобы найти кратчайший путь введения от человека к человеку b. .

public void getIntro(String name, String name2) { 



} 

Answer 1

Кратчайший путь BFS - алгоритм Дейкстры. Wikipedia имеет большое объяснение: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 2

Рассмотрите этот псевдокод, так как я не пробовал компилировать или запускать его. Предполагая, что этот класс существует

public class Node { 
    public String name; 
    public ArrayList<Node> friends; 
} 

Тогда в другом классе, предположим, эти методы

// find a node from the person's name 
public Node findNode(String name) { 
    // ... 
} 

public ArrayList<String> findIntros(String name1, String name2) { 
    Node nodeToFind = findNode(name2); 
    Queue<Node> queue = new Queue<Node>(); 
    Node startNode = findNode(name1); 
    queue.push(startNode); 

    // keep track of people we've already visited so we don't end up in an infinite loop 
    // also use this to track back how we got to a node 
    Map<Node, Node> visitedFrom = new HashMap<Node, Node>(); 
    visitedNodes.put(startNode, null); 

    while (!queue.isEmpty()) { 
    Node currentNode = queue.pop(); 

    if (currentNode.equals(nodeToFind)) { 
     // walk backwards through the visited nodes to find the path 
     ArrayList<String> intros = new ArrayList<String>(); 
     intros.add(currentNode.name); 

     for(;currentNode != null; currentNode = visitedNodes.get(currentNode)) { 
     intros.add(currentNode.name); 
     } 

     Collections.reverse(intros); 
     return intros; 
    } 

    for (Node friend : currentNode.friends()) { 
     if (!visitedNodes.hasKey(friend)) { 
     queue.push(friend); 
     visitedNodes.put(friend, currentNode); 
     } 
    } 
    } 

    System.out.println("no route found"); 
    return null; 
} 

Answer 3

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

Начиная с и люди, развивают дорожки во всех направлениях, пока не встречаются два пути. Тогда у вас есть кратчайший путь. Сохраните список путей в списке, отсортированном с самым коротким сверху и самым длинным внизу. Всегда расширяйте кратчайший список - тот, что сверху. Удалите его из сортировки. Создайте новые пути ко всем подключенным узлам, кроме тех, с которых вы пришли, и всех тех, которые уже находятся в пути. (Если они находятся на пути, этот путь, по крайней мере, такой же хороший, как тот, который вы создали бы, поэтому не беспокойтесь.) Когда пройдут пути от двух людей, у вас есть хороший ответ. Когда все ваши незавершенные пути составляют половину длины пути соединения, такие соединения, какие у вас есть, являются лучшими. В вашем случае, без каких-либо расстояний на краях, у вас, вероятно, будет несколько лучших решений.

По существу, вы создаете две сферы вокруг каждого человека и расширяете их до тех пор, пока они не коснутся. Каждый узел в пути должен иметь указатель на предыдущий узел в пути плюс длину. Следовательно, ссылка на узел (который имеет эту информацию) также является ссылкой на путь.

Некоторые другие ответы могут точно настроить это решение (конечно, некоторые из них могут быть лучше), но Я больше всего хотел указать преимущества работы с обоими людьми одновременно. Я видел много алгоритмов, которые в основном расширяют сферу от одного человека (для использования вашего конкретного примера), пока он не включит другой. Общий объем единой сферы будет намного больше, чем у двух сфер.

(Odd как понятие сферы, кажется, работает даже в вашем случае, когда вы не имеете никаких физических мест вообще.)

Вы должны быть в состоянии сделать что-нибудь умное с отсортированного списка, учитывая, что вы будет иметь только два значения сортировки за раз. (Вы начинаете с них, затем переключаете их один за другим на два, затем на тройки и т. Д.). Вы можете использовать java.util.TreeSet, если вы отсортировали по длине пути и по имени. Это будет медленнее, но каждый раз даст то же точное решение. (Если A подключается к B и C, и они подключаются к D, ABD и ACD имеют одинаковую длину и при правильных (или неправильных) обстоятельствах, один запуск может использовать ABD как часть наилучшего пути, а следующий может использовать ACD. ненавижу это.) Однако, с большим количеством людей на вашем графике, вы можете обнаружить, что скорость чрезвычайно важна для полезной программы.