24.11.2011, 00:23 | #1 (permalink) |
Member
Регистрация: 24.02.2011
Сообщений: 25
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Помогите изменить алгоритм
Код:
#include <stdlib.h> #include <iostream> #include <string.h> #include <vector> #include <windows.h> #include <iomanip> using namespace std; struct branch { int s; int e; int w; void clear() { s=0,e=0,w=0; } }; //Функция проверки графа на связность int isconnected(vector < vector <int> > matrix) { int s = matrix.size(), i=0, j=0, k=0, got=0; int * n=new int[s]; for (i=0; i<s; i++) n[i]=0; n[0]=1; i=0; do { got = 0; i++; for(j=0;j<s;j++) if(n[j]==i) for(k=0;k<s;k++) if(matrix[j][k]&&!n[k]) { got++; n[k]=i+1; } }while(got); for (i=0; i<s; i++) if (!n[i]) { delete[] n; return 0; } delete[] n; return 1; } //функция для поиска минимального дерева. Результат возвращается в массиве. vector <branch> tree(vector <vector <int> > weight) { int s = weight.size(), i=0, j=0, k=0, occ=0; int * n=new int[s]; for (i=0; i<s; i++) n[i]=0; vector<branch> result; branch tmp; tmp.w = 0; //Выбираем наименьшее ребро графа как первую ветвь дерева. for(i=0;i<s;i++) for(j=i+1;j<s;j++) if (weight[i][j]&&((weight[i][j]<tmp.w)||!tmp.w)) { tmp.w = weight[i][j]; tmp.s=i; tmp.e=j; } result.push_back(tmp); //выбрали, сохранили n[tmp.s]=1; n[tmp.e]=1; occ=2; //n - массив использованных вершин while(occ<s) { tmp.clear(); for(i=0;i<s;i++) if (n[i]!=0)//Ищем минимальное ребро среди тех, которые образуют дерево при прибавлении к текущему. for (j=0;j<s;j++)//Проходимся по вершинам, которые уже в дереве, и ищем ребро, соединённое с ними if (weight[i][j]&&((weight[i][j]<tmp.w)||!tmp.w)&&!n[j]) { tmp.w = weight[i][j]; tmp.s=i; tmp.e=j; } result.push_back(tmp); n[tmp.e]=1; occ++; } delete[] n; return result; } //Подготовка кириллической строки для печать в консоли string cyr(string str) { char * temp; temp=new char[str.size()+1]; strcpy(temp, str.c_str()); CharToOem(temp,temp); string result = temp; delete[] temp; return result; } int main (void) { string str; vector <int> tmpvec; vector<branch> tr; int n, i, j; cout << cyr("Введите количество вершин: ") << endl; cin >> n; if(n<2) { cout << cyr("Минимального остовного дерева не существует") << endl; system("pause"); return 0; } vector <vector <int> > weight(n); //матрица сопряжённости cout << cyr("Введите вес ребра между вершинами:")<<endl; for (i=0; i<n;i++) weight[i].assign(n,0); for (i=0;i<n;i++) for(j=i;j<n;j++) { do { cout<< i+1 << '-' << j+1 << ": "; cin >> weight[i][j]; weight[j][i]=weight[i][j]; if(weight[i][j]<0) cout << cyr("Неверное значение, повторите ввод:") <<endl; } while(weight[i][j]<0); } if (!isconnected(weight)) { cout << cyr("Граф несвязный!")<< endl; } else { //если все проверки выполнены, заполняем вектор tr tr = tree(weight); cout << endl << cyr("Мин. остовное дерево:")<< endl; //выводим минимальное остовное дерево в виде таблицы cout << cyr("Начало|Конец|Вес") << endl <<"------|-----|---" <<endl; for(i=0;i<tr.size();i++) cout << setw(6)<< tr[i].s+1 << "|" << setw(5)<< tr[i].e+1 << "|" << setw(3)<< tr[i].w << endl; system("pause"); return 0; } system("pause"); return 1; } |
24.11.2011, 00:23 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Возможно в этих темах уже есть ответы Помогите изменить иконку на вход в сайт Алгоритм Помогите, над изменить вход пользователей в систему Алгоритм с возвратом Помогите написать алгоритм и блок-схему |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|