在C++中使用CLRS實現廣度優先搜索STL

-2

我想實現CLRS中提供的廣度優先搜索算法。我是STL新手，需要幫助添加邊緣功能。這裏我試圖推送相鄰列表中的節點。在C++中使用CLRS實現廣度優先搜索STL

enum eNodecolor{ 
    WHITE, 
    GREY, 
    BLACK 
}; 

struct sVertex{ 
    int  m_iValue; 
    eNodecolor m_visited; 

public: 

    sVertex(int iValue) { 
     m_iValue = iValue; 
    } 


}; 


class CGraph { 
private: 

    std::map<sVertex, vector<sVertex*> > m_mapAdjList; 
    int m_iNoOfVertices; 

public: 

    CGraph(int iNoOfVertices) { 
     m_iNoOfVertices = iNoOfVertices; 

    } 

    void addEdge(int iDataForSource, int iDataForDestination); 

    ~CGraph(void){} 

    void bfs(); 
}; 

/* user will call function add edge with source data and destination data. */ 

void CGraph::addEdge(int iDataForSource, int iDataForDestination) { 



     // check if vertex exists in map if not create it 
     // Question: How can I check here if data for source exists in map. 
     // if not exists create vertex 
    sVertex* src = new sVertex(iDataForSource); 
    sVertex* dst = new sVertex(iDataForDestination); 
    vector<sVertex*> edge(m_iNoOfVertices); 
    edge.push_back(dst); 
    src->m_visited = WHITE; 

    std::pair<std::map<sVertex, vector<sVertex*> >::iterator,bool> ret; 

    m_mapAdjList.insert(pair<sVertex,vector<sVertex*> >(*src,edge)); 



    ret = m_mapAdjList.insert (std::pair<sVertex, vector<sVertex*> >(src, dst)); 

} 

}

如何在C++中使用STL實現相關列表？

問題是我最初的設計是對的？如果不指引我正確的方向。

我提供的示例代碼

感謝

來源

2015-02-09 venkysmarty

還有另一個關於代碼評論的StackExchange網站。 – 2015-02-09 13:45:23

@AbhinavGauniyal問題說：「我是STL新手，需要幫助添加邊緣功能。」代碼審查**需要工作代碼**。這個問題不屬於Code Review。 – 2015-02-09 13:48:24

@SimonAndréForsberg，這就是爲什麼我提出了一個評論，而不是答案，我正在閱讀這些線'問題是我的最初設計是正確的？如果不能指引我走向正確的方向。 ':) – 2015-02-09 13:51:03

我看到兩件事情在您的實現

您使用動態內存，但是這是不是真的有必要。只需添加頂點到std::vector
```
std::map<sVertex, std::vector<sVertex> > m_mapAdjList; 
```
你總是創建一個新條目，覆蓋舊的，如果它已經在圖中存在。所以首先檢查一下，如果一個頂點已經存在於圖中。你addEdge()可能看起來像
```
void CGraph::addEdge(int iDataForSource, int iDataForDestination) { 
    sVertex src(iDataForSource), dst(iDataForDestination); 
    auto &edge = m_mapAdjList[src]; 
    edge.push_back(dst); 
} 
```
而你需要一個合適的比較操作符sVertex，當然。

來源

2015-02-09 14:11:31

在C++中使用CLRS實現廣度優先搜索STL

回答

相關問題