Генерация всех максимальных независимых множеств графа
Добавлено: 17 дек 2012, 14:38
Здравствуйте,обращаюсь к вам по поводу проблемы с написанием курсовой работы на тему "Генерация независимых множеств " на языке С++. Дело в том,что я прочитал внимательно алгоритм,на Паскале для такой задачи, пытался запрограммировать все на С++,написал такие же функции(пока что не писал меню программы),но проблема возникла в том,что на языке С++, в отличие от языка Паскаль нет удобного SEt.Там есть std::set,но мне не удобно его использовать.Я выбрал динамические массивы для использования, но имеются некоторые ошибки в теле функций.Посмотрите,пожалуйста,мой код:
Код: Выделить всё
#include<iostream>
using namespace std;
#include<conio.h>
#include<math.h>
#include<locale>
#include<algorithm>
const int N=10;
int **A=new int *[N];
int Ss[N];
void print(int k)
{
int i;
for(i=0;i<k;i++)
{
cout<<Ss[i];//вывод решения на экран
}
}
int number(int **A)
{
int i,cnt;
cnt=0;
for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if (A[i][j]==i)
cnt++;
return cnt;
}
}
}
void Find(int k,int *Qp=new int[N],int * Qm=new int [N])
{
int *Gg=new int[N];
int i;
if(Qp==NULL && Qm==NULL)
print(k);
if(Qm!=NULL)
if(Qp==NULL && Qm==NULL)
print(k);
else Gg=Qp;
/*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
i=0;
while(i<N)
{
for(int j=0;j<N;j++)
{
if (Gg[i]=i)
{
Ss[k]=i;
Find(k+1,Qp-i-A[i][j],Qm-i-A[i][j]);
/*Изменение Qp,Qm для этого уровня (значения k) и соотвественно,изменеие множества кандидатов Gg-"черный ящик Б"*/
Qp=Qp-i;
Qm=Qm+i;
Gg=Qp *(A[i][j]);/*Здесь я хочу продемонстрировать пересечение множества Qp и вершины множества A[i](двумерный массив,отображаюший множество вершин,смежных с i-той вершиной*/
}
i++;
}
}
int delt=N+1;
for(int j=0;j<N;j++)
{
if (Qm[j]==j)
if(number(A[i][j] * Qp)<delt)/*Здесь также видимо неправильно я отобразил пересечение*/
{
i=j;
delt=number(A[j]*Qp);/*Здесь также видимо неправильно я отобразил пересечение*/
}
Gg=Qp* A[i];/*Здесь также видимо неправильно я отобразил пересечение*/
}
/*Окончательная логика "черного ящика А"*/
}
int main()
{
setlocale(LC_ALL,"Rus");
int choice;
cout<<(" Меню программы ")<<endl;
cout<<("------------------------")<<endl;
cout<<("1.Создать граф")<<endl;
cout<<("2.Ввести множества смежных вершин")<<endl;
cout<<("3.Вывести на экран множества независимых вершин графа")<<endl;
cout<<("3.Вывести независимые множества графа")<<endl;
cout<<("4.Выход.");
switch(choice)
case 1:{
cout<<"Введите множества смежных вершин для каждой из графа : "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<A[i][j];
cin>>A[i][j];
}
}
}
break;
getch();
}