2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Прошу помощи в улучшении программы(С/С++)
Сообщение21.04.2013, 12:40 
Задача: в заданном орграфе найти минимальное подмножество вершин, из которых достижимы все остальные
Например: Изображение
Ответом будет: 1,3,5
код: [ скачать ] [ спрятать ]
Используется синтаксис C
#include <stdio.h>
#include <vector>
#include <conio.h>
#include <locale.h>
FILE *f1;

void createUsed(std::vector<bool> *used, int vertex)//создание вектора использованных вершин
{
        for(int i = 0; i < vertex; i++)
                (*used).push_back(false);
}

void zeroUsed(std::vector<bool> *used, int vertex)//обнуление вектора использованных вершин
{
        for(int i = 0; i < vertex; i++)
                (*used)[i] = false;
}

bool inEdges(std::vector<int> *edges, int vertex, int current)//ввод графа
{
        int start = -1, end = -1;
        while(fscanf(f1, "%d %d", &start, &end)!= EOF)
        {
                if(start > vertex || end > vertex || start == 0 || end == 0)
                {
                        printf("Граф введен не павильно (указаны ребра до не существующих вершин)");
                        return false;
                }
                if(start == end)
                        continue;
                if(start == current)
                        (*edges).push_back(end);
        }
        (*edges).push_back(0);
        return true;
}

void deepSearch(int curent, std::vector<std::vector<int>>graph,std::vector<bool>*used)//поиск в глубину
{
        /*curent - текущая вершина из которой ведется поиск*/
        int x = -1;//х - следующая вершина из которой ведется поиск
        (*used)[curent - 1] = true;//запись текущей вершины в список использованных
        for(int k = 0;graph[curent - 1][k]; k++)//цикл, в котором проходятся все доступные вершины из данной
        {
                x = graph[curent - 1][k];//присвоение х  значения возможной вершины
                if(!(*used)[x-1])//если х не пройден
                        deepSearch(x, graph, used);//осуществить поиск из вершины х
        }
}

void endProg(int vertex, std::vector<std::vector<int>>graph,std:: vector<bool>*used)
{
        int flag = 0, count = 0;//flag - величина, используемая для проверки вершины на принадлежность искомому множеству, count - количество вержин в искомом подмножестве (необходимо для идентификации пустого множества)
        for(int i = 1; i <= vertex; i++)
        {
                deepSearch(i, graph, used);//поиск в глубину
                for(int k = 0; k < vertex; k++)//проверка вершины
                {
                        if((*used)[k])//посчет количества вершин, достижимых из данно
                                flag++;
                        else
                                break;
                }
                zeroUsed(used, vertex);//обнуление списка использованных, для следующего поиска
                if (flag == vertex)//вывод ответа
                {
                        printf("%d ", i);
                        count++;
                }
                flag = 0;//обнуление величины для проверки
        }
        if(!count)
                printf("0");
}

void main()
{
        setlocale(LC_CTYPE, "Russian");
        std::vector<std::vector<int>>graph;//здесь граф
        std::vector<int>edge;//ребра, доступные из текущей вершины
        std::vector<bool> used;
        f1 = fopen("count.txt","r");
        int vertex = -1;
        fscanf(f1,"%d", &vertex);
        if(vertex < 0)
        {
                printf("Кoличество вершин не может быть отрицательным!");
                goto end;
        }
        fclose(f1);
        createUsed(&used, vertex);//обнуление использованных

        f1 = fopen("input.txt", "r");
        for(int i = 0; i < vertex; i++)
        {
                if(!inEdges(&edge, vertex, i + 1))
                        goto end;
                graph.push_back(edge);
                edge.clear();
                fseek(f1, 0, SEEK_SET);
        }
        fclose(f1);
        endProg(vertex, graph, &used);
        end:
        _getch();
}

В основном использовал язык Си(такое требование), но есть вкрапления С++ (vector)
Я хочу улучшить свою программу. Некоторую "защиту от дурака" я уже поставил (нельзя ввести отрицательное кол-во вершин, нельзя создать ребра до не существующих вершин, "петли" игнорируются). Но есть еще "слабые места".
например, при вводе у меня исходный файл пробегается n раз, я не отсекаю одинаковые ребра - это то что с первого не вооруженного взгляда видно + я думаю, что там еще что-то есть:)
А если не знаете, чем ее можно улучшить, то хоть скажите, на каком тесте она может "упасть" или не правильный ответ дать:)

 
 
 
 Re: Прошу помощи в улучшении программы(С/С++)
Сообщение25.04.2013, 22:00 
Аватара пользователя
А ту ли задачу Вы решаете?

Как я понимаю, в Вашем примере будет три минимальных подмножества вершин из которых достижимы все остальные вершины, а именно {1}, {3}, {5}.
Подмножество {1,3,5} не будет минимальным.

Также не совсем понятно должны ли все прочие вершины быть достижимы из каждой вершины искомого подмножества, либо достаточно достижимости хотя бы из одной вершины этого подмножества?

-- 25 апр 2013, 23:12 --

Полагаю, что Вам нужен второй случай.
И, например, в графе
Изображение
искомым подмножеством будет {1,3}.

 
 
 
 Re: Прошу помощи в улучшении программы(С/С++)
Сообщение27.04.2013, 14:25 
это я уже понял, ваш вариант толкования верен. Просто изначально мне ее не так истолковали, и теперь мне нужна программа именно на ваш вариант толкования.
Точнее она у меня уже есть
код: [ скачать ] [ спрятать ]
Используется синтаксис C
#include <stdio.h>
#include <conio.h>
#include <locale.h>
int vertexCount = -1;//количество вершин графа
FILE *f;
bool detected = false;//true, если найдена ошибка

bool all_used (bool *used, int *x)//проверяет все ли использованы, и возвращает номер не использованной вершины
{
        for(int i = 0; i < vertexCount; i++)//проход по списку использованных, пока не будет найдена следующая вершина
                if(used[i] == false)
                {
                        *x = i + 1;//запись в переменную значения следующей вершины
                        return false;
                }
                return true;//если вершина не найдена, возвращает, что весь граф просмотрен
}

bool **create_array_for_special_vertexes()
{
        bool **isolated = new bool *[2];//массив проверяющий "особые" вершины
        isolated[0] = new bool [vertexCount];//создание этого массива
        isolated[1] = new bool [vertexCount];//продолжение создания
        for(int i = 0; i < 2; i++)
                for(int j = 0; j < vertexCount; j++)
                {
                        isolated[i][j] = false;
                }
                return isolated;
}

void zero_used(bool *used)//зануление массива использованных вершин
{
        for(int i = 0; i < vertexCount; i++)
                used[i] = false;
}

bool belong(int *graph, int vertex)//подпрограмма, которая проверяет принадлежность текущего ребра списку (необходима для удаления мульти-ребер)
{
        for(int i = 0; i < vertexCount; i++)
                if(graph[i] == vertex)
                        return true;
        return false;
}

int *graphInc(int current, int *graph, bool **isolated)//ввод массивов из которых будет собран граф
{
        int start = -1, end = -1, i = 0;
        graph = new int [vertexCount - 1];//выделение памяти под часть графа
        while(fscanf(f, "%d %d", &start, &end)!= EOF)
        {
                if(start == end)//отсечение петель
                        continue;
                if(start > vertexCount || end > vertexCount || start == 0 || end == 0)//проверка корекстности введеных данных
                {
                        printf("Граф введен не павильно (указаны ребра до не существующих вершин)");
                        detected = true;//метка, что из подпрограммы был осуществлен досрочный выход
                        goto exit;//выход
                }
                if(start == current && !belong(graph, end))//ввод вершин (если мультиграф, и это ребро уже существует, то не вводит его)
                {
                        isolated[0][start - 1] = true;//отметка в "специальном" массиве, что из данной вершины выходят ребра
                        isolated[1][end - 1] = true;//отметка, что в данную вершину входят ребра
                        graph[i] = end;//помещение конца ребра в массив
                        i++;
                }
        }
        graph[i] = 0;//ввод признака конца в ребра
        exit://точка выхода из подпрограммы, если найдена ошибка в исходных данных
        return graph;
}

bool stok_head(int current, bool **special)//проверяет, является ли заданная вершина головой стока (возвращает true, если это так)
{
        return !(special[0][current - 1]) && special[1][current - 1];
}

void deepSearch(int curent, int **graph, bool *used)//поиск в глубину
{
        /*curent - текущая вершина из которой ведется поиск*/
        int x = -1;//х - следующая вершина из которой ведется поиск
        used[curent - 1] = true;//запись текущей вершины в список использованных
        for(int k = 0;graph[curent - 1][k]; k++)//цикл, в котором проходятся все доступные вершины из данной
        {
                x = graph[curent - 1][k];//присвоение х  значения возможной вершины
                if(!used[x - 1])//если х не пройден
                        deepSearch(x, graph, used);//осуществить поиск из вершины х
        }
}

void tryToDoSmtng(bool *used, bool **special, int **graph)//поиск минимального подмножества
{
        int next = 0;
        while(!all_used(used, &next))
        {
                if(!stok_head(next, special))
                {
                        deepSearch(next, graph, used);
                        printf("%d ", next);
                }
                else
                        used[next - 1] = true;
        }
}

void clean(bool *used, bool **special, int **graph)//удаление мусора
{
        delete used;
        delete graph;
        delete special;
}

void main()
{
        setlocale(LC_CTYPE, "rus");
        f = fopen("count.txt", "r");
        fscanf(f, "%d", &vertexCount);
        fclose(f);
        /*Проверка частных случаев на основе кол-ва вершин*/
        if (vertexCount < 0)//ошибка: отрицательное количество вершин графа
        {
                printf("Число вершин графа не может быть отрицательным");
                goto exit;
        }
        if(!vertexCount)//проверка на пустоту
        {
                printf("Граф пуст!");
                goto exit;
        }
        if(vertexCount == 1)//частный случай графа (1 вершина)
        {
                printf("1");
                goto exit;
        }
        /*окончание проверки*/

        bool *used = new bool[vertexCount];//массив использованных вершин
        zero_used(used);//обнуление массива использованных
        f = fopen("input.txt" , "r");//файл с графом
        int **graph = new int *[vertexCount];//массив сожержащий граф (в виде списка ребер)

        bool **special = create_array_for_special_vertexes();//содержит краткую информацию о каждой вершине (наличие входящих и выходящих ребер)

        /*ввод графа*/
        for(int i = 0; i < vertexCount; i++)
        {
                graph[i] = graphInc(i+1, graph[i], special);
                fseek(f, 0, SEEK_SET);
                if(detected)//если выход был осуществлен досрочно, то выход из программы
                        goto exit;
        }
        fclose(f);
        /*окончание ввода графа*/

        tryToDoSmtng(used, special, graph);//выполнение поставленной задачи

        exit://точка досрочного выхода их программы, если найдена ошибка или частный случай
        /*Удаление мусора, после выполнения поставленной задачи*/
        clean(used, special, graph);
        _getch();
}

И теперь мне необходимо эту программу улучшить:)

 
 
 
 Re: Прошу помощи в улучшении программы(С/С++)
Сообщение29.04.2013, 20:33 
Аватара пользователя
StopCry в сообщении #716233 писал(а):
void clean(bool *used, bool **special, int **graph)//удаление мусора
{
delete used;
delete graph;
delete special;
}

Э-э-э . . .
Вы уверены, что здесь не должно быть:
delete[] used;
delete[] graph;
delete[] special;
?

Да и массивы
Код:
isolated[0] = new bool [vertexCount];//создание этого массива
isolated[1] = new bool [vertexCount];//продолжение создания
надо бы вернуть в кучу.

Хотя, конечно, программа всё равно закрывается, и ОС сама вернёт себе все ресурсы (в расчёте на это можно обойтись и без clean).
Но если не закрывается, то утечка памяти налицо.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group