圖論 - 切換樹成員

Question

我不能決定，如何在C++中定義圖。

現在，我有2維數組：

A - B,D 
B - A 
C - D 
D - A,C 

但是我的麻煩是當我想切換一些圖的 「成員」（例如d和A）。我知道我需要這樣的事情（我可以​​手動從圖形圖像）：

A - C,D 
B - D 
C - A 
D - A,B 

但我居然不知道，怎麼寫的算法，這將是能夠改變二維數組的順序，因爲它不像重新排序一維數組那麼簡單。

Answer 1

有兩種常見的方式來表示數據中的圖形。第一個是一組對，其中第一個和第二個都是頂點。如果對存在，則存在邊緣btween該對中的兩個頂點：

std::set<std::pair<int, int> > setMyGraph; 

第二使用稱爲鄰接矩陣的數據結構。該矩陣列出行和列上的頂點，並且如果頂點x和頂點y之間存在邊，則位置（x，y）保持爲真。否則它會成爲錯誤。

vector<vector<bool> > vMyGraph; 

Answer 2

如果你只是想找一種方法來表示你的圖表，以便完成你的工作，可以考慮boost :: graph。

當我允許用戶將一個頂點拖動到另一個頂點以合併它們時，我必須做些輕微的相似操作。我做這件事的方式，你可能需要做同樣的事情，就是跟蹤邊緣，將它們的描述存儲在臨時（我有數據附加到圖表中），刪除其中一個頂點（你會可能不得不這樣做），然後重建需要重建的圖的部分......但現在不同了。

Answer 3

如果您使用索引而不是指針來引用鄰居，那麼您可以簡單地交換A和D並保持邊緣不變。換句話說，從

0 (A) - 1, 3 
1 (B) - 0 
2 (C) - 3 
3 (D) - 0, 1 

2D陣列更改爲

0 (D) - 1, 3 
1 (B) - 0 
2 (C) - 3 
3 (A) - 0, 1 

編輯：無論使用指針或沒有，你的曲線圖是由各自含有的值的節點序列（A描述，本例中的B，C或D）以及對鄰居節點的引用。這些引用可以是索引到節點數組（如我的示例中）或指向鄰居節點的指針。不管鄰居引用的表示如何，您只需交換值並保持鄰居引用不變。