2 3
6
1 4 5
0
6
3 5
Программа на С++.Графы.Удаление вершин в графе
Помогите, плиз....с написание программы на С++.....Суть программы: в каком порядке нужно удалять вершины графа, чтобы не нарушать связность графа.
Вообщем разбирайтесь :)
Код:
#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;
}
}
#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;
}
}
Код:
Код:
Удалена вершина с именем: 2
Удалена вершина с именем: 1
Удалена вершина с именем: 4
Удалена вершина с именем: 3
Удалена вершина с именем: 6
Удалена вершина с именем: 5
Для продолжения нажмите любую клавишу . . .
Удалена вершина с именем: 1
Удалена вершина с именем: 4
Удалена вершина с именем: 3
Удалена вершина с именем: 6
Удалена вершина с именем: 5
Для продолжения нажмите любую клавишу . . .