VPF::Вершинное покрытие графа - Форум программистов

WindWalker

Дата 18.12.2009, 11:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 18.12.2009

Репутация: нет
Всего: нет

Здравствуйте!
подскажите, что нужно добавить в этот код что бы прога находила вершинное покрытие? (минимальное число верш, из которых можно достич все остальные)
хотя бы какие нить идеи соображения, я даже примерно не знаю как это должно выглядеть.

Код


#include<iostream.h>
#include<fstream.h>
#include<windows.h>


int **ssh, n;    
/*
gr    -матрица смежности направленного графа.
n    -количество вершин в графе.
*/

main()
{
    char m[80];
    ifstream finp("graf.dat");//объявление объекта связанного с файлом
    int i, j;//счёчики.

    finp>>n;//считываем из файла количество вершин

    //создаём указатель на двумерный масив
    ssh=new int *[n];
    for (i=0; i<n; i++)
        ssh[i]=new int[n];

    //обнуляем массив смежности графа
    for (i=0; i<n; i++)
    for (j=0; j<n; j++)
        ssh[i][j]=0;

    //считываем граф из файла
    while (!finp.eof())
    {
        finp>>i>>j;
        ssh[i][j]=1;
    }

    //выводим граф на экран
    CharToOem("Информация из файла:",m);
    cout<<m<<endl;
    CharToOem("Количество школ:",m);
    cout<<m;
    cout<<n<<endl;
    for (i=0; i<n; i++)
    for (j=0; j<n; j++)
        if (ssh[i][j]==1)
        cout<<i<<"=>"<<j<<endl;
return 0;
}

teanik

Дата 18.12.2009, 21:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 15.12.2009

Репутация: нет
Всего: нет

Эта задача NP-сложная. vertex cover Т.е. эффективного алгоритма решения нет.
Решить её можно полным перебором.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »