在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

回答

相关问题