#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define max_member 100
class graph;
class list;
class node
{
int data; // chua vi tri cua dinh lien ket thu data tren mang cac danh sach head
node *next;
public:
node(int a=-1)
{
data = a;
next = 0;
}
friend class list;
friend class graph;
};
class list
{
node *head;
public:
list()
{
head = 0;
}
~list()
{
while(head)
{
node *temp= head;
head = head->next;
delete temp;
}
}
bool set_contact(int a)
{
node *p= new node(a);
if(!p)
return false;
if(!head)
head = p;
else
{
node *temp = head;
while(temp->next&&temp->next->data>a)
{
if(temp->data == a)
return false;
temp = temp->next;
}
p->next = temp->next;
temp->next = p;
}
return true;
}
bool remove_contact(int a)
{
if(head)
{
node *temp = head;
if(temp->data == a)
{
head = head->next;
delete temp;
return true;
}
else
while(temp)
{
if(temp->next->data ==a)
{
node *p = temp->next;
temp = temp->next->next;
delete p;
return true;
}
temp = temp->next;
}
}
return false;
}
void view_contact()const
{
if(head)
{
node *temp = head->next;
cout<<"Dinh : "<<(head
->data+1)<<"\t"; while(temp)
{
cout<<(head
->data+1)<<"-"<<(temp
->data+1)<<" "; temp = temp->next;
}
}
}
friend class graph;
list operator = (const list &a)
{
if(head)
{
while(head)
{
node *temp= head;
head = head->next;
delete temp;
}
head = 0;
}
if(a.head)
{
head = new node(a.head->data);
node *p =head, *q=a.head->next;
while(q)
{
p->next = new node(q->data);
p=p->next;
q=q->next;
}
}
return *this;
}
};
class graph
{
list rank[max_member];
int member;
public:
graph()
{
member = -1;
}
void set_member(int a)
{
member = a;
for(int i=0;i<a;i++)
{
rank[i].head= new node(i);
}
}
void insert_member()
{
member++;
}
void remove_member(int a)
{
a--;
if(a<=member&&a>=0)
{
for(int i=0;i<=member;i++)
if(i!=a)
rank[i].remove_contact(a);
for(int i=a;i<member;i++)
rank[i]=rank[i+1];
rank[member].~list();
member--;
}
}
void add_contact(int a,int b)
{
a--;b--;
if(a<=member&&a>=0)
{
rank[a].set_contact(b);
}
}
void remove_contact(int a,int b)
{
a--;b--;
if(a<=member&&a>=0)
{
rank[a].remove_contact(b);
}
}
void view_graph()const
{
if(member>=0)
{
for(int i = 0;i<=member;i++)
{
rank[i].view_contact();
}
}
}
void dft_graph()const
{
bool check[max_member];
for(int i=0;i<=member;i++)
check[i]=false;
for(int i=0;i<member;i++)
{
if(!check[i])
{
if(i
<member
&&i
>0)cout<<" -> ";cout<<(i
+1); dft_func(i,check);
}
}
}
void dft_func(int i,bool check[])const
{
check[i] = true;
node *temp = 0;
if(rank[i].head->next)
temp = rank[i].head->next;
else
return;
while(temp)
{
if(!check[temp->data])
{
cout<<" -> "<<(temp
->data+1); dft_func(temp->data,check);
}
temp = temp->next;
}
}
void bft_graph()const
{
bool check[max_member],read[max_member];
for(int i=0;i<=member;i++)
check[i]=read[i]=false;
for(int i=0;i<member;i++)
{
if(!check[i])
{
if(i
<member
&&i
>0)cout<<" -> ";cout<<(i
+1); check[i]=true;
node *temp = rank[i].head->next;
while(temp)
{
cout<<" -> "<<(temp
->data+1); read[temp->data]=true;
temp = temp->next;
}
temp = rank[i].head->next;
while(temp)
{
if(!check[temp->data])
bft_func(temp->data,check,read);
temp=temp->next;
}
}
}
}
void bft_func(int i,bool check[],bool read[])const
{
check[i] = true;
node *temp = 0;
if(rank[i].head->next)
temp = rank[i].head->next;
else
return;
while(temp)
{
if(!check[temp->data]&&!read[temp->data])
{
cout<<" -> "<<(temp
->data+1); bft_func(temp->data,check,read);
}
temp = temp->next;
}
}
};
void main()
{
graph a;
int n,m;
/*cout<<"\n Moi nhap so dinh cua do thi: ";cin>>n;
a.set_member(n);
cout<<"\n Nhap vao -1 de thoat.\n";
while(1)
{
cout<<"\n Nhap vao dinh xet moi quan he:";cin>>n;
cout<<" Co quan he voi dinh: "; cin>>m;
if(n<0||m<0)
break;
else
a.add_contact(n,m);
}
clrscr();*/
a.set_member(7);
a.add_contact(1,5);
a.add_contact(1,2);
a.add_contact(2,5);
a.add_contact(2,4);
a.add_contact(5,3);
a.add_contact(4,3);
a.add_contact(5,7);
a.add_contact(5,6);
a.add_contact(7,6);
a.add_contact(6,3);
a.add_contact(3,4);
a.add_contact(5,2);
a.add_contact(5,4);
a.add_contact(4,2);
a.add_contact(1,7);
/* a.set_member(5);
a.add_contact(1,2);
a.add_contact(1,4);
a.add_contact(1,5);
a.add_contact(2,1);
a.add_contact(2,3);
a.add_contact(2,4);
a.add_contact(2,5);
a.add_contact(3,2);
a.add_contact(3,4);
a.add_contact(4,1);
a.add_contact(4,2);
a.add_contact(4,3);
a.add_contact(4,5);
a.add_contact(5,1);
a.add_contact(5,2);
a.add_contact(5,4);*/
cout<<"\n Cac moi quan he tren do thi vua nhap la: \n\n"; a.view_graph();
cout<<"\n\n Duyet DFT \n"; a.dft_graph();
cout<<"\n\n Duyet BFT \n"; a.bft_graph();
getch();
}