在加權圖中查找邊緣

我有一個包含四個節點的圖，每個節點代表一個位置，它們像二維網格一樣佈局。每個節點都有一個連接（邊緣）給所有（根據位置）相鄰的節點。每條邊都有一個重量。在加權圖中查找邊緣

下面是由A，B，C，d和邊緣的權重表示由數字指示的節點：

欲結構的容器和用於切換節點共享的算法最重的邊緣。然後重置該邊的重量。每次執行算法時，節點（位置）都不能切換一次以上。

例如，處理上面的，最高的權重是邊緣BD，所以我們切換這些。由於沒有節點可以多次切換，因此B或D中涉及的所有邊都將被重置。

然後，下一個最高權重是唯一的邊緣左側，切換這些會給我們最終佈局：C，d，A，B。

我目前正在運行一個相當可怕的實現。我存儲一長串邊緣，它們（可能）連接的節點持有四個值，其重量值和節點本身的位置。每次請求時，我都會循環整個列表。

我正在用C++寫這篇文章，STL的某些部分可以幫助加快速度嗎？另外，如何避免重複數據？節點位置當前在五個對象中。該節點本身和四個節點表示與它的連接。

總之，我想幫助：

可以這樣的方式來構造，使得沒有數據重複？
意識到這個問題？如果有任何這樣的名字，告訴我，我可以谷歌的主題更多的信息。
快速算法總是很好。

來源

2009-07-24 Mizipzor

假設邊緣僅在網格位置之間正交連接，網格本身是正方形，則邊緣的數量可以由2n（n + 1）給出，其中n = sizex-1 = sizey-1 ...如果它幫助。來源：http：//www.research.att.com/~njas/sequences/A046092 – Mizipzor 2009-07-24 21:10:02

至於名稱，這是一個頂點覆蓋問題。最佳頂點覆蓋是具有可靠的近似解決方案的NP難度，但您的問題更簡單。您正在嚴格的邊緣選擇標準下查看僞最大值。具體來說，一旦選擇了一條邊，每一條連接的邊被移除（表示要移除要交換的頂點）。

例如，下面是一個標準的貪婪方法：

0）的邊緣進行排序;保留鄰接信息
而邊緣保持：
1）選擇最高邊緣
2）從列表中刪除所有相鄰邊緣
ENDWHILE

選定邊的列表給出了頂點交換。
時間複雜度爲O（排列頂點+頂點上的線性通道），通常會歸結爲O（排序頂點），這可能由O（V * log（V））決定。

保留鄰接信息的方法取決於圖屬性;看到你友好的本地算法文本。爲了簡單起見，可以從一個鄰接矩陣開始。

與鄰接信息一樣，大多數其他速度改進將最適用於某種形狀的圖形，但具有時間與空間複雜度的權衡。

例如，您的問題陳述似乎意味着頂點以正方形模式佈局，從中可以派生出許多有趣的屬性。例如，該系統非常容易並行化。此外，鄰接信息將是高度規則的，但在大圖大小時稀疏（大多數頂點不會相互連接）。這使得鄰接矩陣給出了很高的開銷;您可以將鄰接存儲在4元組數組中，因爲它可以保持快速訪問，但幾乎可以完全消除開銷。

來源

2009-07-24 21:28:13

「邊緣着色爲每個邊緣指定一種顏色，使得沒有兩個相鄰邊緣共享相同的顏色」（http：//en.wikipedia。組織/維基/ Graph_coloring）。對我來說就像我只對兩種「顏色」感興趣，處理和不處理。「相鄰邊緣不共用顏色」問題應該以什麼方式考慮？ – Mizipzor 2009-07-24 21:39:43

如果您有更大的圖表，請查看boost graph庫。它爲您提供了良好的圖形和基本迭代器的數據結構，用於不同類型的圖遍歷

來源

2009-07-24 21:16:14 Janusz

在加權圖中查找邊緣

回答

相關問題