友谊图BFS

Question

使用BFS在无向图中找到最短路径。鉴于人们的姓名和他们的朋友，我正在创建一张友谊图。我试图实现的方法是通过朋友从人a到人b的最短介绍。我真的不知道从哪里开始BFS。我需要建议或seudo代码或任何会让我开始的东西。我知道BFS我需要一个队列，但并不真正如何以及从哪里开始。给出的输入是两个人的名字，我需要使用BFS来找到从人a到人b的最短介绍路径。

public void getIntro(String name, String name2) { 



} 

Answer 1

BFS最短路径是Dijkstra算法。维基百科有一个很好的解释：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

我用这个算法的道路网格，但它会为你工作了，虽然你不能使用将节点的物理位置作为最佳路径的线索。

从开始人，开发四通八达的路径，直到两条路径相遇。然后你有最短的路径。将路径列表保存在一个列表中，其中最短的列表在最上面，最长的列在最下面。始终扩展最短的列表 - 最上面的列表。从排序中删除它。为所有连接的节点创建新的路径，除了您来自的节点和已经在路径中的节点。 （如果他们在一条路上，那条路至少和你要创造的路一样好，所以不要打扰。）当两个人的路径相遇时，你有一个很好的答案。当所有未完成的路径都是连接路径长度的一半时，那么这样的连接就是最好的连接。在你的情况下，你的边缘没有距离，你可能有几个最好的解决方案。

基本上，你正在创造两个球体围绕每个人，并扩大他们，直到他们接触。路径中的每个节点都应该有一个指向路径中前一个节点的指针加上一个长度。因此，对节点（具有此信息）的引用也是对路径的引用。

其他一些答案可能会微调此解决方案（当然，有些可能会更好），但我最想指出同时从两个人工作的优势。我见过很多算法，它们基本上从一个人扩展一个球体（使用你的具体例子），直到它包含另一个人。单个球体的总体积将比两个球体的总体积大得多。

（奇数球的概念，怎么好像在你的情况，你有没有物理位置在所有甚至工作。）

你应该能够做一些巧妙的搭配排序列表，给你一次只会有两个排序值。 （你从1开始，然后将它们一个接一个地切换到2，然后切换到3）等等。如果按路径长度和按名称排序，则可以使用java.util.TreeSet。这样会比较慢，但每次都会给出相同的确切解决方案。 （如果A连接到B和C并且连接到D，ABD和ACD的长度相同并且在正确（或错误）的情况下，则一次运行可以使用ABD作为最佳路径的一部分，并且下一次可以使用ACD。讨厌这个）。然而，图中有很多人，你可能会发现速度对于一个可用程序来说是至关重要的。