Новичок
Профиль
Группа: Участник
Сообщений: 37
Регистрация: 12.11.2011
Репутация: нет
Всего: нет
|
Есть алгоритм Прима построения дерева из графа. Считает всё правильно, но вывод начальных результатов не верный, не могу понять почему, должно всё правильно выдавать...а нет. Должен быть результат: 0 (0,1) 1 (1,2) 2 (2,8) 2 (2,5) 5 (5,6) 6 (6,7) 2 (2,3) 3 (3,4) | Код |
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
typedef pair<int, int> pii; //(B,величина ребра.)
typedef vector<vector<pii> > Graph; //A(B,величина ребра.)
long long prim(Graph &g, vector<int> &pred) //функцыя алгоритму
{
int n = g.size(); //розмір графу
pred.assign(n, -1); //очистка вектора
vector<bool> vis(n);
vector<bool> vis_2(n); //
vector<int> prio(n, INT_MAX); //створення вектору з кількістю величини графа
//і присвоєння всім максимального числа INT_MAX (константа)
prio[0] = 0; //обнулення першого елементу
priority_queue<pii, vector<pii> , greater<pii> > q; //контейнер сортуванння
q.push(make_pair(0, 0)); //добавка нульового елементу
long long res = 0; //вага дерева
priority_queue<pii, vector<pii> , greater<pii> > po;
po.push(make_pair(0, 0));
cout<<"Szukame minimalne drzewo rozpinajace grafa z 9 wierzcholkow"<<endl;
cout<<"V={0,1,2,3,4,5,6,7,8} i 14 krawedz"<<endl;
cout<<"E="<<endl;
cout<<"(a,b)={4}"<<endl;
cout<<"(b,c)={8}"<<endl;
cout<<"(c,d)={7}"<<endl;
cout<<"(d,e)={9}"<<endl;
cout<<"(e,f)={10}"<<endl;
cout<<"(f,g)={2}"<<endl;
cout<<"(g,h)={1}"<<endl;
cout<<"(h,a)={8}"<<endl;
cout<<"(h,i)={7}"<<endl;
cout<<"(c,i)={2}"<<endl;
cout<<"(g,i)={6}"<<endl;
cout<<"(c,f)={4}"<<endl;
cout<<"(d,f)={14}"<<endl;
cout<<"(b,h)={11}"<<endl;
cout<<endl;
while (!q.empty()) //Поки вектор не пустий
{
int d = q.top().first; //перший елемент перша пара вектора
int u = q.top().second; //перший елемент друга пара вектора
q.pop(); //видалення першого елементу вектора
int pocz=po.top().second;
po.pop();
if (vis[u])
continue;
vis[u] = true;
res += d; //додавання ваги дерева
for (int i = 0; i < (int) g[u].size(); i++) //цикл для всіх звязків даного вузла
{
int v = g[u][i].first; //вузол першого сполучення
if (vis[v])
continue;
int nprio = g[u][i].second; //вага першого сполучення вузла
if (prio[v] > nprio) //
{
prio[v] = nprio; //добавлення ваги першому сполученню дерева
pred[v] = u; //добавлення до вектора другої пари вектора
q.push(make_pair(nprio, v)); //добавлення нового елементу
po.push(make_pair(nprio, u));
}
}
if (u!=0)
{
cout<<pocz<<" ("<<pocz<<",";
cout<<u<<") ";
}
}
return res;
}
int main() {
Graph g(9);
g[0].push_back(make_pair(1, 4));
g[0].push_back(make_pair(7, 8));
g[1].push_back(make_pair(0, 4));
g[1].push_back(make_pair(2, 8));
g[1].push_back(make_pair(7, 11));
g[2].push_back(make_pair(1, 8));
g[2].push_back(make_pair(3, 7));
g[2].push_back(make_pair(8, 2));
g[2].push_back(make_pair(5, 4));
g[3].push_back(make_pair(2, 7));
g[3].push_back(make_pair(4, 9));
g[3].push_back(make_pair(5, 14));
g[4].push_back(make_pair(3, 9));
g[4].push_back(make_pair(5, 10));
g[5].push_back(make_pair(4, 10));
g[5].push_back(make_pair(6, 2));
g[5].push_back(make_pair(2, 4));
g[5].push_back(make_pair(3, 14));
g[6].push_back(make_pair(5, 2));
g[6].push_back(make_pair(7, 1));
g[6].push_back(make_pair(8, 6));
g[7].push_back(make_pair(6, 1));
g[7].push_back(make_pair(8, 7));
g[7].push_back(make_pair(1, 11));
g[7].push_back(make_pair(0, 8));
g[8].push_back(make_pair(7, 7));
g[8].push_back(make_pair(2, 2));
g[8].push_back(make_pair(6, 6));
vector<int> prio;
long long res = prim(g, prio);
cout<<"\nWaga minimalnego drzewa rozpinajacego rowna sie: "<<res<<endl;
cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
|
|
Проблема с алгоритмом Прима, ошибка начальных результатов 
Дата 18.12.2011, 03:03 (
Загрузка ...
