兩個用戶之間的連接

我運行我自己的網站，人們有能力擁有朋友。這是我如何存儲友誼：兩個用戶之間的連接

id1 | id2 
1 | 2 
1 | 3 
2 | 4

基本上用戶ID 1是朋友爲用戶ID 2和ID 3和用戶2是朋友的用戶ID 4.

我想要得到的是如何例如，連接1和4。目前，它是這樣的：

1 -> 2 -> 4

如果是大約4和3之間那就是：

4 -> 2 -> 1 -> 3

的想法是找到儘可能

的唯一途徑這兩個之間的快速鏈接我可以想到的是創造一個巨大的循環與大量的循環和類似的東西，可能會更好，更高效。

來源

2013-03-12 Nikola

聽起來像旅行商的變化？ – KevinDTimm 2013-03-12 17:23:38

這是不平凡的。看看[圖論]（http://en.wikipedia.org/wiki/Graph_theory）。 – engineerC 2013-03-12 17:30:59

你在友誼表中大概有多少條目？圖表的密度是多少，即大多數人有幾個朋友，或大多數人有幾百個朋友？是否需要找到絕對最短路徑，或者任何路徑都可以？你是否想找到路徑，不管它有多長，或者你可以停止，例如，最多5個鏈接？ id1'總是小於'id2'嗎？ – mellamokb 2013-03-12 18:18:32

最短的友誼路徑通常通過使用稱爲雙向搜索的算法找到。主要想法是將友誼網絡視爲無向圖，在這裏尋找2個節點之間的最短路徑。該算法同時從兩個節點開始搜索，發現已知節點的鄰居節點。當已知節點的兩個表面首先重疊時，找到最短路徑。

請注意，某些特殊情況需要處理，例如其中一個人在圖上的「孤島」，這樣的節點集未連接到其他節點（想想沒有任何社區與外界的關係）

底線它是一個不太大的while循環。

來源

2013-03-12 18:45:30 sw0rdf1sh

最好在兩個方向進行廣度優先搜索，即從兩個人都有問題，並找到連接或達到指定的深度限制時停止此過程。這個想法也是先到達更受歡迎的人（在執行BFS時）

來源

2013-08-09 03:13:12

RDBMS不擅長做這樣的事情。

你需要的是一個graph db，我強烈建議Neo4j，這是流行和開源。

來源

2013-08-09 03:23:08 adamsmith

我想先嚐試的是廣度優先搜索。

請注意，以下代碼無法修改，因爲我沒有檢查過語法錯誤。如你所見，query（）函數應該返回一個條目列表。它旨在給你一個想法。

/* Return one of the shortest friendship paths from f1 to f2. Returns false when 
* path is longer than limit or no path exists. 
* PROTOTYPE FIX IT YOURSELF 
*/ 
function friend_path($f1, $f2, $limit) { 
    $friended = array($f1 => false); // The tree of friendships leading to f1 
    $discovered_friends = array($f1); // List of friends to examine next 
    while($limit-- > 0) { 
     $interesting_friends = $discovered_friends; 
     $discovered_friends = array(); 
     foreach(query(" 
      SELECT id1 AS friender, id2 AS friendee 
      FROM friendships 
      WHERE id1 in (".join(',', $interesting_friends).") 
      ") as $discovered_link 
     ) { 
      $friendee = $discovered_link['friendee']; 
      $friender = $discovered_link['friender']; 
      if (!isset($friended[$friendee])) { 
       $discovered_friends []= $friendee; 
       $friended[$friendee] = $friender; 
       if ($friendee == $f2) { 
        return friend_path_track($friended, $friendee, $track); 
       } 
      } 
     } 
     if (count($discovered_friends) < 1) return false; 
    } 
    return false; 
} 

function friend_path_track($friended, $friendee, $track) { 
    $track []= $friendee; 
    if ($friended[$friendee]) === false) return array_reverse($track); 
    return friend_path_track($friended, $friended[$friendee], $track); 
}

此代碼爲簡化進行了優化。除了玩具數據庫之外，你應該做一個雙向搜索，在那裏你保留兩個列表，friended和friends（朋友的樹到f2）。您將擴展較短的列表，同時在另一個列表中查找匹配項。儘管你不能欺騙複雜性，所以你必須保持極低的迭代次數，以避免你喜歡垃圾服務器的聲音。

來源

2013-08-09 11:02:57 sba

這將與重量爲1的邊緣。有一個sample code來計算在一個社交網絡中的兩個朋友之間的連接在PHP

來源

2013-12-31 08:49:29 kb0000

兩個用戶之間的連接

回答

相關問題