0

私は単純なグラフを持っており、私の課題は 2 つのノード間の最短経路を見つけることです。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; vertexは 2 つintの 1)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);
           }
        }
    }
}

私の実装には何か問題があるはずです。私はただ何が何であるかを見ていません。

更新: マルチマップ アプローチを使用してこれを解決しました。詳細な説明は次のとおりです: MultiMap をトラバースして、指定された値から指定されたキーへのパスを検索します。

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 に答える