友誼圖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。討厭這個）。然而，圖中有很多人，你可能會發現速度對於一個可用程序來說是至關重要的。