爲我的圖形數據實現BFS的問題struct

這裏是我從頭開發的圖形數據結構的設計。現在要實施BFS，我正在考慮使用STL的某些部分來減輕更多的負擔。 Here is 爲我的圖形數據實現BFS的問題struct

我使用的算法從Cormen的書。對於喜歡顏色一些算法的一部分[U]，距離[U]等等，我想到使用地圖。但我不能決定我是否應該使用地圖像>>std::map<node<T>*, Node_struct_data_like_color_etc>或 std::map<data_type_which_node_contains, Node_struct_data_like_color_etc>

此外，上述地圖將不得不適應與算法中的其他部分一樣 for(all_adjacent_vertex_v_of_u)等

我很抱歉，我的問題可能會看起來含糊不清，但不能解釋得更好。

來源

2011-08-09 Mr.Anubis

什麼阻止您將顏色等數據存儲在節點中？如果顏色等屬性與節點相關聯，我認爲這是合乎邏輯的。 – 2011-08-09 19:05:08

嗯..但我不想編輯圖形結構，而不是僅僅添加BFS功能 –

爲什麼不呢？如果您的節點不存儲節點屬性（如顏色），它們存儲的是什麼？ – aib

一次，我試圖做類似的事情。我做的錯誤是我沒有定義函數對象來排序map的元素時，我將指針存儲爲索引類型的節點。所以當你設計你的BFS的時候應該考慮這個，當把顏色/其他屬性作爲value_type在節點指針作爲索引類型的映射中。

讓您計劃實施映射應該是這個樣子

std::map<Node_t*,NodeProperty_t*,SortNode> 

struct SortNode{ 
operator()(Node_t*,Node_t*){ 
//... 
} 
}

來源

2011-08-09 19:23:40

所以你更喜歡你所說的設計，而不是'std :: map ' –

是的......它與你的'std :: map *，Node_struct_data_like_color_etc>'類似一個SortNode參數，最好只保留指向'Node'而不是'Node'的指針 –

我寫了這個簡單的BFS如果它可以幫助

//simple bfs assuming graph is of the form vecotr<int> g 
int q[20000]; 
int vis[20000]; 

void bfs(int v_) 
{ 
    int top = 0; 
    memset(vis, 0, sizeof(vis)); 
    vis[v_] = 1; 
    q[top++]=v_; 
    while(top) 
    { 
     int v = q[--top]; 
     for(vector<int>::iterator it = g[v].begin(); it!= g[v].end(); ++it) 
     { 
      int u = *it; 
      if(!vis[u]) 
      { 
       q[top++]=u; 
       vis[u] = 1; 
      } 
     } 
    } 
}

來源

2011-08-09 19:10:50 FUD

我不需要代碼，但設計幫助:( –

你需要幫助什麼部分excatly ..是它的圖形表示，在這種情況下，你可以有一個類名爲節點，其中包含一個向量鄰接和你想要的其他屬性喜歡的顏色等 – FUD

你可能想看看Boost Graph Library爲靈感，甚至只是使用它。

請注意，它支持屬性映射（如您建議的第一個映射）和自定義節點類（@Grigory Javadyan和我的建議）。

來源

2011-08-09 19:52:38 aib

爲我的圖形數據實現BFS的問題struct

回答

相關問題