實現加權圖

Question

說我有以下的鄰接矩陣：

A B C D 
A 0 9 0 5 
B 9 0 0 0 
C 0 0 0 2 
D 5 0 2 0 

這將如何實際上可以實施？我意識到我可以使用二維數組來表示頂點之間的加權邊，但我不知道如何表示頂點。

int edges[4][4]; 
string vertices[4]; 

是這樣做的嗎？頂點數組中的索引對應於邊數組中的行索引。

Answer 1

可以使用二維std::map

使用這種方法允許矩陣增長和收縮當過你想要的。

#include <map> 
#include <string> 
#include <iostream> 

int main() 
{ 
    std::map<std::string, std::map<std::string, int>> vertices; 

    vertices["A"]["A"] = 0; vertices["A"]["B"] = 9; vertices["A"]["C"] = 0; vertices["A"]["D"] = 5; 
    vertices["B"]["A"] = 9; vertices["B"]["B"] = 0; vertices["B"]["C"] = 0; vertices["B"]["D"] = 0; 
    vertices["C"]["A"] = 0; vertices["C"]["B"] = 0; vertices["C"]["C"] = 0; vertices["C"]["D"] = 2; 
    vertices["D"]["A"] = 5; vertices["D"]["B"] = 0; vertices["D"]["C"] = 2; vertices["D"]["D"] = 0; 

    std::cout << vertices["A"]["A"] << std::endl; 
    std::cout << vertices["A"]["B"] << std::endl; 
} 

Answer 2

通過鄰接矩陣的索引作爲頂點是常見的做法。

Answer 3

對於大多數的意圖和目的它通常是更有效的來表示圖形作爲adjentacy列表：

std::vector< std::list<int> > graph; 

所以圖[i]是我的所有相鄰頂點。好處是，在處理圖時，我們通常要穿過我的鄰居。另外，對於大型稀疏圖，空間複雜度要低得多。這當然也可以擴展到包括權重的東西，如：

std::vector< std::list<std::pair< int, int> > > graph; 

或更復雜的類型，定義類型的頂點......

編輯：如果您需要指數爲字符串，這很容易通過選擇爲std ::地圖，而不是的std ::向量來完成：

std::map< std::string, std::list<std::pair< std::string /*vertex*/, int/*weight*/> > > graph; 

但它從原來的職位，你只是想圖索引到頂點的名字，在這種情況下，我與去出現第一個soluion，但也保持頂點名稱映射到索引：

std::vector< std::pair< std::string/*name*/, std::list<std::pair< int /*index*/, int/*weight*/> > > > graph; 

Answer 4

如果圖中有固定數量的頂點。您可以將頂點聲明爲枚舉，並使用枚舉的頂點名稱直接爲數組索引。我認爲它使映射更清晰一些。

enum VERTEX 
{ 
    A = 0, 
    B, 
    C, 
    D, 
    LAST = D 
}; 

int edge[LAST+1][LAST+1]; 
edge[A][A] = 0; 
edge[A][B] = edge[B][A] = 9; 
edge[A][C] = edge[C][A] = 0; 
// etc. 

這讓事情通過允許你卻如此容易理解使用數組沒有任何查找點球簡單快捷。