Генерация Всех Независимых Множеств Графа

Тема в разделе "C/C++/C#", создана пользователем vladis222, 17 дек 2012.

  1. vladis222

    vladis222 Active Member

    Регистрация:
    6 дек 2011
    Сообщения:
    31
    Симпатии:
    0
    Здравствуйте,обращаюсь к вам по поводу проблемы с написанием курсовой работы на тему "Генерация независимых множеств " на языке С++. Дело в том,что я прочитал внимательно алгоритм,на Паскале для такой задачи, пытался запрограммировать все на С++,написал такие же функции(пока что не писал меню программы),но проблема возникла в том,что на языке С++, в отличие от языка Паскаль нет удобного SEt.Там есть std::set,но мне не удобно его использовать.Я выбрал динамические массивы для использования, но имеются некоторые ошибки в теле функций.Посмотрите,пожалуйста,мой код:
    Код (C++):
    #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();

    }
     
  2. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    ошибки будут потом, используй set.
    приводи коды и описания ошибок.

    Добавлено:
    Код (Text):
    const int N=10;
    int **A=new int *[N];
    int Ss[N];
    не используй глобальных переменных.

    то что ты написал вообще работать не должно. new выполняется во время выполнения, для этого этот код должен быть засунуто в какую-то функцию. Надеяться на то что компилятор оптимизирует этот бред не стоит.
     
  3. vladis222

    vladis222 Active Member

    Регистрация:
    6 дек 2011
    Сообщения:
    31
    Симпатии:
    0
    У меня есть написанный код при помощи set,но он обнаруживает ошибки. Вот он:
    Код (C++):
    #include<iostream>
    using namespace std;
    #include<conio.h>
    #include<math.h>
    #include<locale>
    #include<set>
    const int N=10;
    multiset <int > A[N];
    void Print(int k)
    {
    int i;
    int Ss[N];//Решение хранится в этом массиве
    for(i=0;i<k;i++)
    {
    cout<<Ss[i];//вывод решения на экран
    }
    }
    void Find(int k,set<int> Qp,set <int> Qm)
    {
    set<int> Gg;
    int i;
    if(Qp.empty()==true && Qm.empty()==true)
    Print(k);
    /*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
    i=0;
    while(i<=N)
    if (Gg.find(i)!=Gg.end())
    {
    Ss[k]=i;
    Find(k+1,Qp.erase(A[i],i))/*Ошибка в удалении множества вершин смежной с данной и самой вершины, я не знаю как это записать,я объявил А как multiset(в нем хранятсямножества вершин,смежной с i-той вершиной.*/
    }
    }
    int Number( set <int> A)
    {
    int i;
    int cnt;
    cnt=0;
    for(i=1;i<N;i++)
    {
    if(A.find(i)!=A.end())
    cnt++;
    return cnt;
    }
    }

    void Find(int k,set<int>Qp,set<int>Qm)
    {
    set<int>Gg;
    int delt=N+1;
    int i;
    int j;
    if (Qp.empty()==true && Qm.empty()==true)
    Print(k);
    if(Qm.size()!=0)
    if (Qp.empty()==true && Qm.empty()==true)
    Print(k);
    else
    Gg=Qp;
    for(j=1;j<=N;j++)
    {
    if (Qm.find(j)!=Qm.end())
    if (Number (A[j].find(j))*Qp < delt )/*Здесь я не знал как изображить пересечение вершин,смежных с i-той и множества Qp*/
    {
    i=j;
    delt=Number(A.find(j)*Qp);
    }
    Gg=Qp*A.find(i);
    }
    //черный ящик А
    exit(-1);
    //формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm
    i=1;
    while(i<N)
    {
    if(Gg.find(i)!=Gg.end())
    {
    Ss[k]=i;
    Find(k+1,Qp.erase(A.find(i),i),Qm.erase(A[N].find(i),i));
    //Черный ящик Б//
    i++;
    }
    }
    }
    int Number( set <int> A)
    {
    int i;
    int cnt;
    cnt=0;
    for(i=1;i<N;i++)
    {
    if(A.find(i)!=A.end())
    cnt++;
    return cnt;
    }
    }

    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();

    }
     
  4. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    2 первых ошибки:
    Код (Text):
    void Find(int k, set<int> Qp, set <int> Qm) {
    set<int> Gg;
    int i;
    if (Qp.empty() == true && Qm.empty() == true)
    Print(k);
    /*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
    i = 0;
    while (i <= N)
    if (Gg.find(i) != Gg.end()) {
    Ss[k] = i;
    Find(k + 1, Qp.erase(A[i], i))/*Ошибка в удалении множества вершин смежной с данной и самой вершины, я не знаю как это записать,я объявил А как multiset(в нем хранятсямножества вершин,смежной с i-той вершиной.*/
    }
    }
    а что ты хочешь? - у тебя Ss не объявлено, std::set тут непричем. Компилятор тебе сообщает об ошибке - значит надо исправлять.

    это следующая строка в приведенном коде. И тут, как и в прошлый раз, компилятор тебе нормально сообщает об ошибке.
    http://www.cplusplus.com/reference/set/set/erase/
    а ты что за ерунду пихаешь в erase? - он принимает 2 итератора или значение удаляемого узла, ты передаешь значение и еще какую-то ерунду.

    2 последних ошибки связаны с:
    Код (Text):
    multiset <int > A[N];
    //...
    cout << A[i][j];
    объявлен массив множеств
    A - валидно, ты получаешь i-тое множество
    но ты не можешь дергать элемент множества через оператор [] (элементы во множестве располагаются не в том порядке, в которым ты их туда поместил - если тебе надо что-то другое, используй не множества, а списки или вектора)

    ну и стопицот ошибок между первыми и последними я пропустил, компилятор пишет синим по белому, я думаю ты сам прочитаешь и исправишь.

    Добавлено:
    если добавишь 2 одинаковых элемента в set - то добавится лишь первый (потому что это множество), но в массив добавилось бы оба элемента
     
  5. vladis222

    vladis222 Active Member

    Регистрация:
    6 дек 2011
    Сообщения:
    31
    Симпатии:
    0


    Вот исправил что-то, но все равно есть проблемы. Вот исправленный код:
    Код (C++):
    #include<iostream>
    using namespace std;
    #include<conio.h>
    #include<math.h>
    #include<locale>
    #include<set>
    #include<algorithm>
    #include<iterator>
    const int N=10;
    multiset <int > A[N];
    set<int>::iterator it;
    set<int>::iterator it2;
    set<int>::iterator it3;
    int Ss[N];//Решение хранится в этом массиве

    void Print(int k)
    {
    int i;
    int Ss[N];
    for(i=0;i<k;i++)
    {
    cout<<Ss[i];//вывод решения на экран
    }
    }

    int Number( set <int> A)
    {
    int i;
    int cnt;
    cnt=0;
    for(i=1;i<N;i++)
    {
    if(A.find(i)!=A.end())
    {
    cnt++;
    return cnt;
    }
    }
    }

    void Find(int k,set<int>Qp,set<int>Qm)
    {
    set<int>Gg;
    set <int> out;
    set <int> out2;
    int delt=N+1;
    int i;
    int j;
    it=set_intersection(A[j].begin(),A[j].end(),Qp.begin(),Qp.end(),out.begin());
    it2=set_intersection(Qp.begin(),Qp.end(),A[i].begin(),A[i].end(),out2.begin());

    /* if (Qp.empty()==true && Qm.empty()==true)
    Print(k);
    if(Qm.size()!=0)
    if (Qp.empty()==true && Qm.empty()==true)
    Print(k);
    else
    Gg=Qp;*/

    for(j=1;j<=N;j++)
    {
    if (Qm.find(j)!=Qm.end())
    if (Number(out)<delt)/*Здесь я не знал как изображить пересечение вершин,смежных с i-той и множества Qp*/
    {
    i=j;
    delt=Number(out);
    }
    Gg=out2;
    }


    //черный ящик А
    exit(-1);
    //формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm
    i=0;
    while(i<N)
    {
    if(Gg.find(i)!=Gg.end())
    {
    Ss[k]=i;
    Qp.erase(i);
    Qm.erase(i);
    if()
    /*Отладил почти только не понимаю,как удалить из множества Qm,элементы принадлежащие множеству A[i],это нужно для функции Find*/

    }

    }

    }

    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++)
    {
    cout<<"Для "<<i<<"вершины : ";
    cin>>A[i];
    }


    getch();

    }
    Вопросы:1)Как удалить из множества Qp вершины множества A?Как так задать чтобы компилятор понял что я хочу... 2)Как ввести множества смежностей для каждой вершины,если нельзя напрямую обратиться к вершине в множестве?
     
  6. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36

    я ж приводил ссылку: http://www.cplusplus.com/reference/set/set/erase/
    и вобще, пользуйся поиском, я не понимаю как ты там код пишешь и почему ты думаешь что компилятор должен как-то угадать что ты хочешь.

    да мы с компилятором вместе не можем угадать что ты хочешь ) формулируй нормально.


    ЗЫ. ты какой алгоритм реализовать пытаешь?

    Добавлено:


    Код (Text):
    for (auto val : A[i])
    Qm.erase(val);
    не проверял, но вроде бы должно работать
     
  7. vladis222

    vladis222 Active Member

    Регистрация:
    6 дек 2011
    Сообщения:
    31
    Симпатии:
    0
    Алгоритм Брона-Кэрбоша

    Добавлено:
    А скажите,пожалуйста val это тип set?

    Добавлено:
    Ну просто вначале я хочу ввести множества смежностей для каждой из вершин множества А.И немного затрудняюсь,как это сделать в коде...
     
  8. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    это тип int

    Добавлено:
    Код (Text):
    for (auto val : A[i])
    Qm.erase(val);
    замени на:
    Код (Text):
    for (std::set<int>::iterator it = A[i].begin(); A[i].end() != it; ++it)
    Qm.erase(it);
    если компилятор c++11 не поддерживает
     
  9. vladis222

    vladis222 Active Member

    Регистрация:
    6 дек 2011
    Сообщения:
    31
    Симпатии:
    0
    Спасибо большое,отладил код,ничего уже не подчеркивает,просто при запуске возникают 2 ошибки:
    1)Ошибка 2 error C3892: std::_Tree_const_iterator<_Mytree>::eek:perator *: невозможно присваивать значения переменной, которая объявлена как константа c:\program files\microsoft visual studio 10.0\vc\include\algorithm 4494 mnva 1
    2)Ошибка 3 error C3892: std::_Tree_const_iterator<_Mytree>::eek:perator *: невозможно присваивать значения переменной, которая объявлена как константа c:\program files\microsoft visual studio 10.0\vc\include\algorithm 4494 mnva 1

    Вот новый код:
    Код (C++):
    #include<iostream>
    using namespace std;
    #include<conio.h>
    #include<math.h>
    #include<locale>
    #include<set>
    #include<algorithm>
    #include<iterator>
    const int N=10;
    multiset <int > A[N];
    set<int>::iterator it;
    multiset<int>::iterator it2;
    multiset<int>::iterator it3;

    int Ss[N];//Решение хранится в этом массиве

    void Print(int k)
    {
    int i;
    int Ss[N];
    for(i=0;i<k;i++)
    {
    cout<<Ss[i];//вывод решения на экран
    }
    }

    int Number( set <int> A)
    {
    int i;
    int cnt;
    cnt=0;
    for(i=1;i<N;i++)
    {
    if(A.find(i)!=A.end())
    {
    cnt++;
    return cnt;
    }
    }
    }

    void Find(int k,multiset<int>Qp,multiset<int>Qm)
    {
    multiset<int>Gg;
    set <int> out;
    multiset <int> out2;
    int delt=N+1;
    int i;
    int j;
    it=set_intersection(A[j].begin(),A[j].end(),Qp.begin(),Qp.end(),out.begin());
    it2=set_intersection(Qp.begin(),Qp.end(),A[i].begin(),A[i].end(),out2.begin());

    if (Qp.empty()==true && Qm.empty()==true)
    Print(k);
    if(Qm.size()!=0)
    if (Qp.empty()==true && Qm.empty()==true)
    Print(k);
    else
    Gg=Qp;
    for(j=1;j<=N;j++)
    {
    if (Qm.find(j)!=Qm.end())
    if (Number(out)<delt)
    {
    i=j;
    delt=Number(out);
    }
    Gg=out2;
    }


    //черный ящик А
    exit(-1);
    //формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm
    i=0;
    while(i<N)
    {
    if(Gg.find(i)!=Gg.end())
    {
    Ss[k]=i;
    Qp.erase(i);
    Qm.erase(i);
    for (it3=A[i].begin();A[i].end()!=it3;++it)
    Qp.erase(it3);
    for (it3=A[i].begin();A[i].end()!=it3;++it)
    Qm.erase(it3);
    Find(k+1,Qp,Qm);

    }

    }

    }

    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++)
    {
    cout<<"Для "<<i<<"вершины : ";

    }break;

    }



    getch();
    }
     
  10. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Qp.erase(it3);
    попробуй на
    Qp.erase(*it3);
    заменить
     
  11. vladis222

    vladis222 Active Member

    Регистрация:
    6 дек 2011
    Сообщения:
    31
    Симпатии:
    0
    попробовал, но ошибки есть, мне кажется насколько я понял,что когда я объявлял переменную для создания пересечения множеств,то допустил какие-то ошибки,правда вот не знаю,как теперь написать без ошибок,посмотрите пожалуйста.
     
  12. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    тут он компактно описан: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%BE%D1%88%D0%B0
    тут есть реализация на С++ : http://dictionary.sensagent.com/%D0%B0%D0%...88%D0%B0/ru-ru/
    и эта реализация встретилась мне на 3 из 5 первых ссылок гугла по запросу "брона кербоша С++".

    А ты тут вообще чем-то не тем занимаешься, смотреть на сотни строк твоего ужасного кода желания нет. Я думаю проще написать с нуля чем твой код исправить.
     
Загрузка...
Похожие Темы - Генерация Всех Независимых
  1. vladis222
    Ответов:
    4
    Просмотров:
    1.686
  2. vladis222
    Ответов:
    0
    Просмотров:
    1.014
  3. lmike
    Ответов:
    3
    Просмотров:
    633
  4. framd
    Ответов:
    1
    Просмотров:
    782
  5. DamirAstana
    Ответов:
    11
    Просмотров:
    1.874

Поделиться этой страницей