0

我有一个简单的图表，我的任务是找到两个节点之间的最短路径。我已经尽力阅读了 BFS 伪代码和示例，但它只是没有点击。

我的节点存储在邻接列表中，（目前我不关心边权重）这是数据的视觉效果：第一列是向量元素，它最左边的行是另一个向量。向量元素编号表示对应节点的编号。

=====================================
0  |  (1, 100), (3, 50), (7, 100)
1  |  (0, 100), (4, 50), (5, 10) 
2  |  (3, 1000), (4, 200), (6, 1000) 
3  |  (0, 50), (2, 1000) 
4  |  (1, 50), (2, 200), (6, 100) 
5  |  (1, 10), (6, 50), (7, 2000) 
6  |  (2, 1000), (4, 100), (5, 50) 
7  |  (0, 100), (5, 2000)

我正在尝试通过我在维基百科上找到的伪代码来实现 BFS，但我没有得到它。我的邻接列表存储在一个向量中：vector<vector <vertex> > adjList; vertexis a struct of two int1)node和 2 weight)

我的实现非常基本：

vector<vector <vertex> > adjList;      // the vector adjacency list

// the start and end vertices are passed into the function
int startV;     //num of start node
int endV;       //num of destination node

bool visited = false, done = false;    //control         

vector<int> marked, path;              // holds visited and final path

Queue<int> Q;                          // Q for BFS
Q.push(startV);                        // enqueue BFS

while (!Q.empty() && !done) {

    int t = Q.front(); Q.pop();        // mark and pop(back)
    marked.push_back(t);               // push back start node onto marked

    if (t == endV)                     // if t is our destination
        done = true;                   // done, get out of here

    size_t adjE = adjList[t].size();   // degree of this node

    for (int i = 0; i < adjE; i++) {

        int u = adjList[t][i].node;    // visit each adjacent node

        for (int j = 0; j < marked.size(); j++) {

           if (marked[j] == u)         // test if node has been marked
               visited = true;  
           }
                                       // check if this node has
           if (!visited) {             // already been visited
              marked.push_back(u);     // if not enqueue
              Q.push(u);
           }
        }
    }
}

我知道我的实现一定有问题。我只是没有看到是什么。

更新： 我通过使用多地图方法解决了这个问题。详细解释在这里：Traverse MultiMap to Find Path from a given Value to a given Key

4

1 回答 1

0

visited我认为您关于查找节点的逻辑是不正确的。尝试

...
int u = adjList[t][i].node;

visited = false;
for (int j = 0; j < marked.size(); j++) {
    // std::find() does essentially all this for you. Check it out.
    if (marked[j] == u) {
        visited = true;
    }
}

if (!visited) {
    marked.push_back(u);
    Q.push(u);
}
于 2013-03-08T01:25:26.463 回答