給定一組頂點，如何生成一個具有接近最小量邊的強連通有向圖？

Question

我想對我的圖類的dijkstras算法執行測試。爲此，我生成一個包含幾千個頂點的圖，然後通過隨機添加數千個邊來連接圖，直到圖連接。然後，我可以反覆在任意兩個隨機頂點之間運行搜索，並確保它們之間存在路徑。問題是，我經常以一個接近密集的圖表結尾，因爲我使用的是鄰接列表表示，導致我的搜索算法非常慢。

問題： 鑑於V，你如何生成強連接，向圖，具有比密級圖在同一個頂點顯著少邊將有一組頂點？

，我想簡單地做以下：整個圖形

vertex 1 <--> vertex 2, vertex 2 <--> vertex 3, ..., vertex n-1 <--> vertex n 

然後隨機加入像N/10的邊緣，但是這似乎並不像未來與隨機圖結構的最佳方式測試我的搜索算法。

Answer 1

一種方法是維護一組強連通的組件（從|V|單頂點組件開始），並且在每次迭代中，通過連接每個組件的隨機頂點將它們的一些隨機子集合併成單個連接組件到下一個的隨機頂點，形成一個循環。

這將傾向於生成非常稀疏的圖，所以根據您的使用情況，您可能還想要拋出一些額外的隨機邊緣。

編輯：直覺上，我想你會想要使用指數分佈時決定在一次迭代中合併多少個組件。不過，我沒有任何真正的支持。

Answer 2

我不知道是否有這樣做的更好的辦法，但至少這似乎工作：

• 我想補充E（導演）隨機頂點之間的邊緣。這將生成幾個頂點集羣。
• 然後，我需要連接這些集羣以形成一個集羣鏈，這樣可以確保從一個集羣我可以到達任何其他集羣。爲此，我可以將每個簇的隨機頂點標記爲「主」頂點，並將主頂點連接起來形成一個循環。因此，您有一個由集羣組成的強連通有向圖（尚未有頂點）。最後一個主設備應該連接回第一個主設備，從而創建一個循環。
• 現在，爲了將它變成由頂點組成的強連通有向圖，我需要使每個羣集本身成爲一個強連通的有向圖。但是，如果我從集羣的主節點開始運行DFS，並且每次找到一個葉時，都會從該葉節點添加一條邊到其主頂點，這很容易。請注意，DFS不能遍歷集羣外部。

我認爲這可能會起作用，雖然拓撲結構不會是真正的隨機性，但它會像一個由連接在一起的較小圖形組成的大循環一樣循環。但根據您需要測試的算法，這可能派上用場。

編輯：

• 後，如果您想擁有更隨機的拓撲結構，可以在不同集羣的頂點之間添加隨機的邊緣。這不會使規則失效，併爲您的算法創建更復雜的路徑來遍歷。