Неділя, 21.04.2019, 23:48
Гость

Мішатронік

Автор - Кренцін Михайло

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Чи знаєте вы Java
Всього відповідей: 2
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0




Пошук у ширину

Даний алгоритм призначений для пошуку найкоротшого шляху в графі, де ребра мають одиничну вагу.

vector< vector<int> >g(N);

int bfs(int s,int toto) //s - стартова вершина, toto - кінцева
{    
queue<int> q; //черга, необхідно написати #include<queue>
vector<bool> used (N); // вектор відвіданих вершин
vector<int> d (N), p (N); // вектори відстаней та шляху

q.push (s); //черга
used[s] = true;//відвідали вершину
p[s] = 1; //в цю вершину ми прийшли
d[s]=0; // відстань у початкову точку=0
while (!q.empty()) {   //чи є елементи в черзі
    int v = q.front(); //перший елемент в черзі
    q.pop(); //видалення першого елемента черги
    for (size_t i=0; i<g[v].size(); ++i) {  //цикл по суміжних вершинах
        int to = g[v][i];
        if (!used[to]) {
            used[to] = true;
            q.push (to);
            d[to] = d[v] + 1; //покращення результату
            p[to] = v; //шлях
        }
    }
}

return d[toto]; //шукана відстань
}


 

 

Форма входа
Пошук
Календар
«  Квітень 2019  »
ПнВтСрЧтПтСбНд
1234567
891011121314
15161718192021
22232425262728
2930
Друзі сайту
Погода у Вінниці


Єдина Країна! Единая Страна!