поиск в ширину — проблема C ++ с пониманием BFS, чтобы найти кратчайший путь

У меня есть простой график, и мое назначение — найти кратчайший путь между двумя узлами. Я сделал все возможное, чтобы прочитать псевдокод 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 это структура из двух intх 1node и 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, чтобы найти путь от заданного значения к заданному ключу

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);
}
0

Другие решения

Других решений пока нет …