#include <iostream>
using namespace std;
const int n=4;
class Graph
{
public:
int countnow;
struct data
{
int node,v;
data *next;
}**GM;
Graph();
~Graph();
void EnterMas(char*);
void Add(int, int, int);
void BFS(bool*, int, int, bool*);
void Delpoint(int);
};
int k;
Graph::Graph()
{
countnow=n;
GM=new data*[n];
for (int i=0; i<n; i++)
GM[i]=NULL;
}
Graph::~Graph()
{
data* temp;
for (int i=0; i < n; i++)
while(GM[i])
{
temp=GM[i];
temp=temp->next;
delete temp;
}
if (GM)
delete[] GM;
}
void Graph::EnterMas(char *filename)
{
data *temp=new data;
FILE *f;
int i,j,p,s;
temp=GM[0];
if ((f = fopen(filename, "r")) == NULL)
{
cout << "Error" << endl;
system("pause >> void");
return;
}
cout<<"Cïèñîê ñìåæíîñòè ãðàôà: "<<endl;
for (i=0; i<n; i++)
{cout <<"Âåðøèíà "<<i+1<<": ";
for (j=0; j<n; j++)
{
fscanf(f, "%d", &p);
if (p<9999)
{Add(p,i,j);}
}
cout<<endl;
}
/*while (temp->next)
{cout<<n<<temp->node;temp=temp->next;}*/
fclose(f);
}
void Graph::Add(int p, int i, int j)
{
data *temp = new data;
temp->node = j;
temp->v = p;
temp->next = NULL;
cout<<j+1<<" ";
if (GM[i])
{
data *end = GM[i];
while (end->next)
end = end->next;
end->next = temp;
}
else
GM[i] = temp;
}
void Graph::BFS(bool *visited, int unit, int point, bool* flag)
{
data *temp=GM[unit];
int *queue=new int[n];
int count=0, head=0,i,j;
for (i=0; i<n; i++)
queue[i]=0;
queue[count++]=unit;
visited[unit]=true;
while (head<count)
{
unit=queue[head++];
if ((unit+1)==point)
flag[k]=1;
cout<<unit+1<<" ";
/*for (i=0; i<n; i++)
if (GM[unit][i] && !visited[i])
{
queue[count++]=i;
visited[i]=true;
}*///i=0;
for (temp=GM[unit];temp;temp=temp->next)
if ((temp->v<9999)&& !visited[temp->node])
{
queue[count++]=temp->node;
visited[temp->node]=true;
}
}
k++;
cout <<endl;
delete []queue;
}
void Graph::Delpoint(int del)
{
FILE *f;
int i,j;
if ((f = fopen("result.txt", "w")) == NULL)
{
cout << "Error" << endl;
system("pause >> void");
return;
}
for (i=del; i<countnow-1; i++)
for (j=0; j<countnow; j++)
GM[i][j]=GM[i+1][j];
for (j=del; j<countnow-1; j++)
for (i=0;i<countnow;i++)
GM[i][j]=GM[i][j+1];
countnow--;
for (i=0; i<countnow; i++)
{
for (j=0; j<countnow; j++)
fprintf(f,"%d ",GM[i][j]);//cout<<" "<<GM[i][j];
fprintf(f,"\n");//cout<<endl;
}
fclose(f);
return;
}
int main(int argc, char *argv[])
{
setlocale(LC_ALL, "Rus");
int start=0,point,del=0,count=0,i,j;
bool *visited=new bool[n],*flag=new bool[n];
char filename[100];
if (argc == 1)
{
cout << "Ââåäèòå èìÿ ôàéëà" << endl;
cin >> filename;
}
else
strcpy(filename, argv[1]);
Graph U;
U.EnterMas(filename);
for (i=0; i<n; i++)
flag[i]=0;
cout<<"Çàäàéòå âåðøèíó: "<<endl; cin>>point;
while(k<n)
{
for (j=0; j<n; j++)
visited[j]=0;
cout<<"Ñòàðòîâàÿ âåðøèíà >> "; cout<< ++start<<endl;
cout<<"Ïîðÿäîê îáõîäà: ";
U.BFS(visited, start-1, point,flag);
}
for (i=0; i<n; i++)
if (flag[i]==0)
{
cout <<"Íóæíî óäàëèòü âåðøèíó " <<i+1<<endl;
U.Delpoint(i);
cout <<"Âåðøèíà "<<i+1<<" óäàëåíà"<<endl;
}
cout <<"Ïîëó÷åííàÿ ìàòðèöà â ôàéëå result.txt"<<endl;
delete []visited;
delete []flag;
system("pause");
return 0;
}