具有n個頂點的圖形 - 如何打印所有可能的圖形組合

Question

假設我們將圖形中的頂點數設置爲n。 （我們可以通過用戶輸入等來設置）

我想打印使用邊緣連接頂點的所有可能情況。 （所以，我想打印n個頂點的所有可能（簡單）連接圖）。

Answer 1

一個簡單而簡單的解決方案是創建所有可能的圖形，並過濾出未連接的圖形。

創建一組所有可能的邊。這些有n(n-1)/2，這將是該集合的大小。

找到所需要的集合的power set。這個能量集代表了所有可能創建的圖形。

維基百科的文章還給出了一個algorithm用於計算一組集的冪集。 This post也討論了這個問題（java）

對於每個創建的子集 - 檢查它是否連接。它可以使用發現算法完成，如BFS。當且僅當BFS從單個（隨機）源開始時才發現所有頂點，該圖連通。