Довго возився з програмою пошук в ширину, й після довго проведеного часу в інтернеті та спроби самому написати забив, та пошукав ще, нарешті це дало результат:
Ось код який я знайшов, спробую його прокоментувати настільки я розібрався.
// AlgoritmWuruna.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <queue>
#include <stdexcept>
#include <vector>
using namespace std;
struct graph {
graph(size_t nodes)
: m_adjacency_list(nodes) {
}
size_t number_of_nodes() const {
return m_adjacency_list.size();
}
std::vector<size_t> const& neighbours_of(size_t node) const {
return m_adjacency_list.at(node);
}
void add_edge(size_t from, size_t to) {
std::vector<size_t>& al = m_adjacency_list.at(from);
if (to >= m_adjacency_list.size())
throw std::runtime_error("Tried to add edge to non-existant node");
for (size_t i = 0; i < al.size(); ++i) if (al[i] == to) return;
al.push_back(to);
}
private:
std::vector<std::vector<size_t>> m_adjacency_list;
};
/*
1--2--3
| | |
4--5--6
| | |
7--8--9
|
0
*/
int main() {
// generate your grid
graph g(10);
g.add_edge(1, 2);
g.add_edge(1, 4);
g.add_edge(2, 1);
g.add_edge(2, 3);
g.add_edge(2, 5);
g.add_edge(3, 2);
g.add_edge(3, 6);
g.add_edge(4, 1);
g.add_edge(4, 5);
g.add_edge(4, 7);
g.add_edge(5, 2);
g.add_edge(5, 4);
g.add_edge(5, 6);
g.add_edge(5, 8);
g.add_edge(6, 3);
g.add_edge(6, 5);
g.add_edge(6, 9);
g.add_edge(7, 4);
g.add_edge(7, 8);
g.add_edge(7, 0);
g.add_edge(8, 5);
g.add_edge(8, 7);
g.add_edge(8, 9);
g.add_edge(9, 6);
g.add_edge(9, 8);
g.add_edge(0, 7);
// do the bfs
std::vector<size_t> reached_by(g.number_of_nodes(), g.number_of_nodes());
std::queue<size_t> q;
size_t start = 0;
size_t target = 3;
reached_by[start] = start;
q.push(start);
while (!q.empty()) {
size_t node = q.front();
q.pop();
for (size_t i = 0; i < g.neighbours_of(node).size(); ++i) {
size_t candidate = g.neighbours_of(node)[i];
if (reached_by[candidate] == g.number_of_nodes()) {
reached_by[candidate] = node;
if (candidate == target) break;
q.push(candidate);
}
}
}
if (reached_by[target] == g.number_of_nodes())
std::cout<<"No path to "<<target<<" found!"<<std::endl;
else {
std::cout<<"Path to "<<target<<": ";
for (size_t node = target; node != start; node = reached_by[node])
std::cout<<node<<" <- ";
std::cout<<start<<std::endl;
}
cin.get();
}
Немає коментарів:
Дописати коментар