Github 儲存庫 - 解決方案
今天的挑戰相當激烈，而且有些簡單（或至少第 1 部分是這樣）。
收集三重奏中的所有連接，其中任何三角形計算機都以 t 開頭。其實很簡單，然後數一下三角形的數量。
為了實現這一點，我們建立一個節點映射 -> 連接（鄰居），所以我們的連接物件看起來類似於：
connections = {
'kh': {'tc', 'dr'},
'tc': {'kh', 'dr', 'zx'},
'dr': {'kh', 'tc', 'xy'},
'zx': {'tc'},
'xy': {'dr', 'tz'},
'tz': {'xy'}
}
為了獲得三重奏，我們可以迭代連接，並檢索它們的鄰居 - 請記住，在 Python 中，連接中的節點將循環遍歷鍵，而不返回值。要存取這些值，我們需要使用鍵（節點）透過索引連接[節點]來存取它們。
對於每對鄰居節點，它都會產生組合。例如：
如果節點 = 'kh' 且鄰居 = {'tc', 'dr'}，則這些對是 ('tc', 'dr')。它檢查兩個鄰居（neighbor1 和 neighbor2）是否也相互連接（透過connections[neighbor1]）。
如果它們相連，則節點、neighbor1 和 neighbor2 之間存在三角形。
三角形已排序並添加到集合中以避免重複。
然後使用
找出任何節點以 t 開頭的所有連接
triangles_with_t = [triangle for triangle in triangles if any(
node.startswith('t') for node in triangle)]
在第 2 部分中，我們需要找到最大的互連計算機集。當使用像設定這樣的圖形時，互連的節點我們稱為團。
讓我們使用 Bron-Kerbosch 演算法來分解它。 Bron-Kerbosch 演算法用於尋找圖中最大的群組（稱為派系）。在這種情況下，圖只是由邊（連接）連接的節點（如電腦）的集合。以下是該演算法的工作原理以及它與解決我們的難題的關係。
派係是一組節點，其中每個節點都直接連接到其他每個節點。
想像一下您正在參加一個聚會，每個人都認識小組中的其他人。如果連一個人都不認識其他人，那就不是一個小團體。
在我們的謎題中，目標是找到 LAN 方最大的互連電腦群組。這個團體是最大的派系。
子集是較大組中較小的部分，例如：
如果最大的集團是 (A,B,C,D)，那麼較小的子集可能是 A,B,CorB C D`，它們都連結在一起。 這些子集仍然是派系，因為子集中的所有節點都是連接的。
對於大輸入來說，透過蠻力找到最大的派系（嘗試每個可能的組別）是很慢的。例如，如果有 3,000 台計算機，則有數十億個可能的群組需要檢查。
Bron-Kerbosch 演算法透過以下方式加快此過程：
從較小的群體（子集）開始並擴大它們。
當一個群體無法發展成更大的派系時就儘早停止。
避免重複檢查相同的子集。
Bron-Kerbosch 演算法遞歸地工作，這意味著它不斷調用自身來逐步建立派系。其工作原理如下：
輸入：
R：一組可能形成團伙的節點（從空開始）。
P：仍然可以加入派系的節點清單（從所有節點開始）。
X：我們已經檢查過的節點清單（從空開始）。
步驟：
如果 P 和 X 都為空：
R 是一個最大團（你不能在其中增加更多節點）。將 R 儲存為結果。
否則：
從 P 中選取一個節點並將其新增至 R 。
更新 ？和 ？僅包含連接新 R 的節點。
使用新的 R、P 和
再次呼叫演算法
X.
完成後，將節點從 P 移動到 X（已處理）。
重複此操作，直到處理完所有節點，確保找到所有派別而無需進行冗餘檢查。
輸入：假設我們有一個電腦連線列表，例如：
蟒蛇
A-B
A-C
B-C
B-D
C-D
這些連接代表一個圖，其中節點（電腦）透過邊（電線）連接。
目標：找到最大的電腦群組，其中每台電腦都直接連接到其他每台電腦。
流程：
演算法從較小的群體（子集）開始，並嘗試將它們發展成派系。
如果一個群體無法進一步發展（最大派系），它就會停止。
在所有派系中，它確定了最大的派系。
輸出：
例如，最大的派係是
{B、C、D}。
子集呢？
在謎題的背景下：
派系的子集（例如 {B,C,D} 中的 {B,C}）並不有趣，因為它們比最大的派系小。
演算法透過追蹤已處理的節點 (X) 來避免子集的冗餘檢查。
Clique：一個群組，其中每個節點都連接到每個其他節點。
子集：取自較大派系的較小群體。
布朗-克博什：
尋找圖表中的所有派系。
專注於最大的派系，而不是在較小的子集上浪費時間。
謎題解答：
使用此演算法找到 LAN 方最大的互連計算機組。
我希望這可以幫助您理解解決方案，了解 Bron-Kerbosch 演算法，並了解有關 Python 語法的新知識。
一如既往，請隨時關注我，或在 Twitter 上聯繫我。
結果是最大的派系，這就是謎題的答案。
Bron-Kerbosch 遞歸調用，傳入一些修改後的屬性 r |節點、p 和連接[節點]。
Python 中
r |節點 - 使用我們正在建構的團 (r) 中目前節點集中的所有節點以及我們正在新增的另一個節點建立一個新集。
p &connections[node] - 這將建立一個新集，其中僅包含以下節點：
都在 p（仍可以作為團的一部分的節點集）。
也在connectionsnode中。
說明：
& 是集合的交集運算子。
connections[node] 是直接連接到節點的節點集合。
p &connections[node] 的意思是「找到 p 和 Connections[node] 之間的公共節點。」
以上是代碼日區域網路派對的到來的詳細內容。更多資訊請關注PHP中文網其他相關文章！
