刪除G（j，i）條目

Question

我正在解決一個圖形問題。它是一個無向圖。假設有4個頂點（1,2,3,4）並且頂點鏈接如下。

1,2 
1,3 
1,4 
2,1 
3,1 
4,1 

G（I，J）和G（j，i）兼具如上存在（G-圖表，I - 源頂點，J-destincation頂點）。現在，我需要從中刪除所有G（j，i）。這可能是有效的方式。

我試着將所有的頂點插入到一個數組中，並將頂點插入到另一個數組中。類似於

a[0] = 1 and b[0] = 2 
a[1] = 1 and b[1] = 3 
so on.. 

但是，我很難刪除G（j，i）條目。我有3個問題。

1. 是否有任何有效的algoirthm其除去重複項（此處重複我說，bcoz G（I，J）= G（j，i）中。

2. 代替使用陣列，是否有任何數據結構，其能夠執行此操作更容易。

3. 其數據結構通常用於圖形的問題。

Answer 1

的曲線通常被表示或者處於一個djacency矩陣形式或鄰接表。

設N =該＃節點，且m =邊緣＃，和節點的ID是從0標記的整數 - （N-1）

在鄰接矩陣，則基本上具有一個二維大小爲nx n的數組。如果在節點i和j之間沒有邊緣，則索引[i][j]處的值爲0，否則爲非零。如果圖形未加權，矩陣通常是二進制的（0表示無邊，1表示邊），您可以使用布爾值矩陣來節省空間。如果圖形是無向的，則觀察矩陣將是對稱的，因爲在[i][j]處的邊緣指示在[j][i]處的邊緣。但是，如果空間效率是一個問題，並且圖的邊緣是稀疏的，那麼無論邊的數量如何，數據結構將花費O（n^2），浪費的空間將會很多。

替代方案是一個鄰接表，它需要O（n + m）空間。這裏我們可以有一個1D數組，其中數組的每個元素都是一個容器（比如鏈表或哈希集合）。陣列的第i個容器包含連接到節點的節點的ID。

爲了解決你有「EdgeList都」的格式刪除重複的問題，似乎你想要一個無向圖，這意味着從i的邊緣j意味着從j到i邊緣。在鄰接矩陣中，這可以通過簡單地設置[i][j] = [j][i] = true來完成。在鄰接列表中，使用set容器將是最好的，因爲set保證沒有重複的邊緣。因此，當您在您的邊界列表中看到i到j之間的邊緣時，您只需索引i個單元格並添加j，並索引到第j個單元格中並添加i。稍後當您看到j到i時，您也會這樣做，但將重複值添加到散列集中將不會執行任何操作。