Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Программа на С++.Графы.Удаление вершин в графе

86K
20 декабря 2012 года
morozixa939
2 / / 20.12.2012
Помогите, плиз....с написание программы на С++.....Суть программы: в каком порядке нужно удалять вершины графа, чтобы не нарушать связность графа.
392
21 декабря 2012 года
cronya
421 / / 03.01.2009
Удаляет ту вершину графа, которая не нарушит связей между всеми остальными. Если граф построен правильно, удаляются все вершины.
Вообщем разбирайтесь :)
Код:
#include <iostream>
#include <fstream>

using std::cout;
using std::endl;
using std::system;
using std::ifstream;

struct Graph
{
    int name;  
    int* links;
    int size;  
    Graph *next, *prev;
}*head, *tail;

void ReadFromFile(ifstream &File);
void AddGraphTop(char* Line, int count);
int* ParseGraphLinks(char* Line, int size);
int SpaceCount(char* Line);
void ViewGraphFromHead();
void ViewGraphFromTail();
void RemoveGraphTop();
Graph* FindBigGraphTop();
void DeleteGraphFromList(Graph* point);
void SetToNullDeletedTopGraph();
Graph* TryToDelete();
int ListCount();
void FreeMemmory();


int main()
{
    setlocale(LC_ALL, "Russian");
    ifstream File("Graph.txt");
    if(!File.is_open())
    {
        cout<<"Не могу открыть файл"<<endl;
        system("pause");
        return -1;
    }
    head = tail = NULL;
    ReadFromFile(File);
    RemoveGraphTop();
    //ViewGraphFromHead(); 
    FreeMemmory();
    File.close();
    cout << endl;
    system("pause");
    return 0;
}

void ReadFromFile(ifstream &File)
{
    int count = 1;
    char* Line = new char[];   
    while(!File.eof())
    {
        File.getline(Line,30,'\n');
        AddGraphTop(Line, count);
        count++;
    }
}

void AddGraphTop(char* Line, int count)
{
    int size = SpaceCount(Line) + 1;
    if(head == NULL)
    {
        Graph* ptr = new Graph();
        ptr->name = count;
        ptr->size = size;
        ptr->links = ParseGraphLinks(Line,size);       
        ptr->next = ptr->prev = NULL;
        head = tail = ptr;
    }
    else
    {
        Graph* ptr = new Graph();
        ptr->name = count;
        ptr->size = size;
        ptr->links = ParseGraphLinks(Line,size);       
        tail->next = ptr;
        ptr->prev = tail;
        ptr->next = NULL;
        tail = ptr;
    }  
}

int* ParseGraphLinks(char* Line, int size)
{  
    int* Array = new int[size];
    int len = strlen(Line);
    int jdx = 0, kdx = 0;
    char numer[7];
    for(int idx = 0; idx <= len; idx++)
    {
        if(Line[idx] != ' ' && idx != len)
        {
            numer[jdx] = Line[idx];
            jdx++;
        }
        else
        {
            if(kdx < size)
            {
                numer[jdx] = '\0';
                Array[kdx] = atoi(numer);
                kdx++;             
                jdx = 0;
            }
        }
    }
    return Array;
}

int SpaceCount(char* Line)
{
    int count = 0;
    int len = strlen(Line);
    for(int idx = 0; idx < len; idx++)
    {
        if(Line[idx] == ' ') count++;
    }
    return count;
}

void ViewGraphFromHead()
{
    Graph* ptr = head;
    while(ptr!=NULL)
    {
        cout << ptr->name << endl;
        ptr = ptr->next;
    }
}

void ViewGraphFromTail()
{
    Graph* ptr = tail;
    while(ptr!=NULL)
    {
        cout << ptr->name << endl;
        ptr = ptr->prev;
    }
}

void FreeMemmory()
{
    Graph* ptr = head,* tmp = NULL;
    if(head != NULL)
    {
        while(ptr->next != NULL)
        {
            tmp = ptr->next;
            delete[] ptr->links;
            delete[] ptr;
            ptr = tmp;
        }
        delete[] ptr->links;
        delete[] ptr;
        head = tail = NULL;
    }
}

void RemoveGraphTop()
{
    Graph* ToDel = NULL;
    do
    {
        ToDel = NULL;
        if(head != NULL)
        {
            ToDel = TryToDelete();
            if(ToDel != NULL)
            {
                cout<<"Удалена вершина с именем: "<<ToDel->name<<endl;
                DeleteGraphFromList(ToDel);
                SetToNullDeletedTopGraph();
            }
            else
            {
                cout<<"Ошибка в построении графа, проверьте входной файл!!!"<<endl;
            }
        }
        SetToNullDeletedTopGraph();    
    }
    while(ToDel != NULL);  
}

Graph* FindBigGraphTop()
{
    Graph* bGraph = NULL, *ptr = head;
    int count = 0, PrCount = -1;
    while(ptr != NULL)
    {
        count = ptr->size;
        Graph *btr = head;
        while(btr != NULL)
        {
            for(int idx=0; idx < btr->size; idx++)
            {
                if(ptr->name == btr->links[idx])
                {
                    count++;
                }
            }
            btr = btr->next;
        }
        if(count > PrCount)
        {
            PrCount = count;
            bGraph = ptr;
        }
        ptr = ptr->next;
    }
    return bGraph;
}

void DeleteGraphFromList(Graph* point)
{
    /*Если есть хоть одна запись*/
    if(point != NULL)
    {
        /*Если только одна запись*/
        if(point->next == NULL && point->prev == NULL)
        {
            delete[] point->links;
            delete[] point;
            head = tail = NULL;
        }
        else
        {
            /*Если запись в первая или последняя*/
            if(point == head || point == tail)
            {
                /*Если запись первая*/
                if(point == head)
                {
                    Graph* tmp = point->next;
                    delete[] point->links;
                    delete[] point;
                    head = tmp;
                    tmp->prev = NULL;
                }
                /*Если запись последняя*/
                if(point == tail)
                {
                    Graph* tmp = point->prev;
                    delete[] point->links;
                    delete[] point;
                    tail = tmp;
                    tmp->next = NULL;
                }
            }
            /*Если запись в середине*/
            else
            {
                Graph* before = point->prev, *after = point->next;
                delete[] point->links;
                delete[] point;
                before->next = after;
                after->prev = before;
            }
        }
    }
}

Graph* TryToDelete()
{
    Graph* ToDelete = NULL, *ptr = head;
    int count = ListCount();
    if((ptr->next == NULL && ptr->prev == NULL) || count < 3)
    {
        if(count == 2)
        {
            ptr = ptr->next;
        }
        ToDelete = ptr;
        return ToDelete;
    }
    else
    {
        while(ptr != NULL)
        {
            int GraphLen = ptr->size;
            if(GraphLen ==  1 && ptr->links[0] == 0)
            {
                ToDelete = ptr;
                break;
            }
            bool* Check = new bool[GraphLen];
            bool wFlag = false;
            for(int idx = 0; idx < GraphLen; idx++)
            {
                Graph* btr = head;
                bool flag = false;
                if(ptr->links[idx] == 0)
                {
                    Check[idx] = true;
                }
                else
                {
                    while(btr != NULL)
                    {              
                        if(btr != ptr && ptr->links[idx] != btr->name)
                        {
                            int len = btr->size;                   
                            for(int jdx=0; jdx < len; jdx++)
                            {
                                if(btr->links[jdx] == ptr->links[idx])
                                {
                                    flag = true;
                                    Check[idx] = true;
                                    break;
                                }                          
                            }
                        }
                        if(flag == false)
                        {
                            btr = btr->next;
                            Check[idx] = false;
                        }
                        else
                        {
                            break;
                        }              
                    }
                }
            }
            for(int idx=0; idx < GraphLen; idx++)
            {
                if(Check[idx] == false)
                {
                    wFlag = true;
                }
            }
            delete[] Check;
            if(wFlag == false)
            {
                ToDelete = ptr;
                break;
            }      
            ptr = ptr->next;       
        }
        return ToDelete;
    }
   
}

int ListCount()
{
    Graph* ptr = head;
    int count = 0;
    while(ptr != NULL)
    {
        count++;
        ptr = ptr->next;
    }
    return count;
}

void SetToNullDeletedTopGraph()
{  
    int count = ListCount();
    Graph* ptr = head;
    int* Name = new int[count];
    int i = 0; 
    while(ptr != NULL)
    {
        Name[i] = ptr->name;
        ptr = ptr->next;
        i++;
    }
    ptr = head;
    while(ptr != NULL)
    {
        int pLen = ptr->size;
        for(int idx=0; idx < pLen; idx++)
        {
            bool flag = false;
            for(int jdx=0; jdx < count; jdx++)
            {
                if(ptr->links[idx] == Name[jdx])
                {
                    flag = true;
                    break;
                }              
            }
            if(flag == false)
            {
                ptr->links[idx] = 0;
            }
        }
        ptr = ptr->next;
    }
}
входной файл Graph.txt с описанным графом(строка - это номер вершины графа, начинается с 1; в каждой строке описывается пути от вершины графа к другим вершинам; 0 - не имеет соединений от самой вершины графа к другой вершине графа)
 
Код:
2 3
6
1 4 5
0
6
3 5
Результат:
 
Код:
Удалена вершина с именем: 2
Удалена вершина с именем: 1
Удалена вершина с именем: 4
Удалена вершина с именем: 3
Удалена вершина с именем: 6
Удалена вершина с именем: 5

Для продолжения нажмите любую клавишу . . .
Рисунок графа:

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог