Phân tích thiết kế giải thuật

           ĐỒ THỊ VÀ CÂY



Phần Code ở Phía dưới.....



I ĐỒ THỊ
1 Khái Niệm
+ gồm các đỉnh và các cạnh nối các đỉnh
+ V tập các đỉnh, nút
+ E tập các cạnh trường hợp vô hướng
+ A....................................... có hướng

+ Bậc của đỉnh v(trong  vô hướng)  là số cạnh liên thuộc với nó ki hiệu:  deg(v)
+ deg+ (v)   số cung đi ra khỏi đỉnh        trong đồ thị có hướng
+ deg-  (v)   số cung đi vao đỉnh             trong đồ thị có hướng

+ Đường đi: tập điểm nối 2 đỉnh của đồ thị
+ Chu Trình: Đường đi có đỉnh đầu và đỉnh cuối trùng với nhau
+ Đồ thị liên thông: là đồ thị luôn tìm được đường đi giữa 2 đỉnh bất kỳ

2 Biểu diễn đồ thị :
+ Ma trận kề,trọng số:

+ Danh sách cạnh

+ Danh sách kề













                 
+ Ma trận liên thuộc

3 Thuật toán tìm kiếm

 a, Theo CHIỀU SÂU

...............................................................................

.................................................................................................

b, Theo CHIỀU RỘNG

.......................................................................................

.........................................................................................................................

c, Duyệt các Thành phần Liên thông

..............................................................................................

........................................................................................................

............................................................................................................

...........................................................

d, Tìm đường đi giữa 2 đỉnh Đồ thị

...........................................................................................

.............................................................................................

e, Đường đi và chu trình Euler

........................................................................................

..........................................................................

..........................................................................................
Định Lý: 

...........................................................................
THUẬT TOÁN: CHU TRÌNH EULER

........................................................................................
Ví Dụ:

....................................................................................

...........................................................................................................
THUẬT TOÁN: ĐƯỜNG ĐI EULER

.......................................................................................

.................................................................................................


f,...................................... Haminton

..........................................................

...........................................................

.................................................................

..................................................................

......................................................................

******ĐỊNH LÝ******

4 Đường đi ngắn nhất
a,Thuật toán gán Nhãn

...............................................

...................................................

.....................................................

b,Thuật toán Dijkstra

...........................................................

..........................................................

II CÂY

1 Định nghĩa

2 Ứng Dụng
2.1 Cây Nhị Phân Tìm Kiếm

2.2 Cây Quyết Định (AI nói kỹ)

chia 2 bên rồi cân, bên nào nhẹ hơn thì chọn bên đấy rồi cân lên
2.3 Duyệt Cây

2.3.1

2.3.2

 2.3.3

 2.3.4

2.4 Cây Khung và Thuật toán xây dựng cây khung
2.4.1 Định nghĩa
G là đồ thị vô hướng không liên thông, T con của G là cây khung nếu:
+ T là 1 cây
+ tập Đỉnh của T bằng tập Đỉnh của G

=> sau khi xóa 3 cạnh ta đã đk 1 cây khung

2.4.2 Thuật toán tim cây khung theo chiều sâu, rông

2.4.2.1 chiều sâu

 2.4.2.2 chiều rộng

2.4.3 Cây Khung Nhỏ Nhất (gần tương tự đường đi ngắn nhất)
Tìm cây khung có tổng độ dài các cạnh là ngắn nhất

2.4.4 Cách Tim cây khung nhỏ nhất

2.4.4.1 Thuật toán Kruskal

Giải mã Thuật toán:

=> link huong dan: https://lhchuong.wordpress.com/2014/10/03/thuat-toan-kruskal-tim-cay-bao-trum-nho-nhat/

2.4.4.2 Thuật toán Prim

Giải mã thuật toán

=> Link Huong dan :   https://lhchuong.wordpress.com/2014/10/02/thuat-toan-prim-tim-cay-bao-trum-nho-nhat/
Ví dụ: 

CODE phần đồ thị:

+ file text:
6
0 0 0 0 0 2
0 0 4 6 8 0
0 4 0 9 0 15
0 6 9 0 16 0
0 8 0 16 0 22
2 0 15 0 22 0

+  Code:
////TOAN ROI RAC PHAN DO THI/////
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<math.h>
using namespace std;

typedef struct Node{
int data;
Node *next;
};
//////cai dat Queue/////////
typedef struct Queue
{
Node *Head;
Node *End;
};
void Tao_queue(Queue &Q)
{
Q.Head=NULL;
Q.End=NULL;
}
bool isEmpty(Queue Q)
{
if(Q.Head==NULL)
{
return true;
}
else
{
return false;
}
}

Node *Tao_node(int x)
{
Node *temp=(Node*)malloc(sizeof(Node));
temp->next=NULL;
temp->data=x;
return temp;
}

void Put(Queue &Q, int x) //them vao cuoi
{
Node *temp=Tao_node(x);
if(isEmpty(Q)){
Q.Head = Q.End = temp;
}
else{
Q.End->next = temp;
Q.End = temp;
}
}

int Get(Queue &Q)  //Lay phan tu dau va xoa
{
if(isEmpty(Q)){
printf("Danh sach rong !");
return 0;
}
else{
int x;
Node *temp,*temp1;
temp = Q.Head;
temp1= temp->next;
x = temp->data;
while((temp->next)!= NULL){
temp = temp->next;
}
Q.Head=temp1;
Q.End = temp;
return x;
}
}
///////////het cai dat queue////////
///////// cai dat Stack////////

typedef struct Stack // kieu ngan xep stack
{
Node *Top;
};

void Tao_stack(Stack &S) // tao srack rong
{
S.Top = NULL;
}

int isEmpty(Stack S)
{
return (S.Top==NULL);
}

int do_dai(Stack S) // do dai cua stack
{
Node *temp=S.Top;
int i=0;
while(temp!=NULL)
{
i++;
temp=temp->next;
}
return i;
}

void Push(Stack &S, int x) //dua vao trong stack
{
Node *temp=Tao_node(x);
temp->next=S.Top;
S.Top=temp;
}

int Peek(Stack S) //xem stack
{
return S.Top->data;
}

char Pop(Stack &S) //lay ra stack
{
char x;
if(!isEmpty(S))
{
x = S.Top->data;
S.Top=S.Top->next;
}
return x;
}
//////////het cai dat Stack/////////
////////Nhap tu File//////////
void Nhap(int &soDinh,int Data[10][10])
{
fstream f;
f.open("dothi.txt");
f>>soDinh;
for(int i=0;i<soDinh;i++)
{
for(int j=0;j<soDinh;j++)
{
f>>Data[i][j];
}
}
}
// Tim kiem theo chieu sau
void DFS(int Data[10][10],int n,int v,bool ChuaXet[10])// duyet theo chieu sau
{
cout<<" "<<v;//xet dinh v
ChuaXet[v]=false;
for(int u=0;u<n;u++)// xet cac dinh ke voi v => vi dung de quy chieu Stack
{                    // nen khong can tao Stack
if(Data[u][v]!=0 && ChuaXet[u])
{
cout<<"<->";
DFS(Data,n,u,ChuaXet);
}
}
}
/////tim kiem theo chieu rong
void BFS(int Data[10][10],int n,int u,bool ChuaXet[10])
{
Queue Q;
Tao_queue(Q);
Put(Q,u);//nap u vao hang doi
ChuaXet[u]=false;// doi trang thai u
while (!isEmpty(Q))
{
int p=Get(Q);// lay dinh p tu hang doi
cout<<" . "<<p; // tham dinh p

// duyet dinh ke voi p roi nhet vao hang doi
for(int v=0;v<n;v++)
{
if(Data[v][p]!=0 && ChuaXet[v])// v la dinh ke voi u
{
Put(Q,v);
ChuaXet[v]=false;
}
}
}
}
////duyet cac thanh phan lien thong///
void BFS_LT(int Data[10][10],int n,int u,int ChuaXet[10],int solt)
{
Queue Q;
Tao_queue(Q);
Put(Q,u);//nap u vao hang doi

//solt=solt+1; cong o ngoai roi
cout<<"Lien thong thu: "<<solt<<endl;
ChuaXet[u]=solt;// doi trang thai u
while (!isEmpty(Q))
{
int p=Get(Q);// lay dinh p tu hang doi
cout<<" . "<<p; // tham dinh p

// duyet dinh ke voi p roi nhet vao hang doi
for(int v=0;v<n;v++)
{
if(Data[v][p]!=0 && ChuaXet[v]==0)// v la dinh ke voi u
{
Put(Q,v);
ChuaXet[v]=solt;
}
}
}
}
// TIM DUONG DI GIUA DINH CUA DO THI//
void BFS_DD(int Data[10][10],int n,int u,bool ChuaXet[10],int Truoc[10])
{
//da cai dat cho cac gia tri truoc[i] deu = -1 o ngoai
Queue Q;
Tao_queue(Q);
Put(Q,u);//nap u vao hang doi
ChuaXet[u]=false;// doi trang thai u
while (!isEmpty(Q))
{
int p=Get(Q);// lay dinh p tu hang doi
// duyet dinh ke voi p roi nhet vao hang doi
for(int v=0;v<n;v++)
{
if(Data[v][p]!=0 && ChuaXet[v])// v la dinh ke voi u
{
Put(Q,v);
ChuaXet[v]=false;
Truoc[v]=p;// ngon
}
}
}
// duong di la mac dinh: dau la 1, cuoi la 5
cout<<"Duong di la: "<<endl;
cout<<"1->";
for(int i=0;i<n;i++)
{
if(Truoc[i]==-1) continue;
cout<<Truoc[i]<<"->";
}
cout<<"5";
}

///TIM CHU TRINH EULER///
//neu tat ca cac dinh deu bac chan=> co chu trinh euler=> dinh ly=> cam cai
bool Kiem_Tra_CC_Euler(int Data[10][10],int n)
{
int i,j,s;
for(int i=0;i<n;i++)
{
s=0;
for(int j=0;j<n;j++)
{
if(Data[i][j]!=0){
s+=1;
}
}
if(s%2!=0)  return false;// bac khong chan
}
return true;
}

void Euler_Cycle(int Data[10][10],int n)
{
Stack S;
Tao_stack(S);
int CE[15],countCE=0;
// mac dinh chon dinh u ban dau =0
Push(S,0);// them dinh vao Stack

while(!isEmpty(S))
{
int u=Pop(S);//lay ra tu Stack
bool movingCE=true;
for(int v=0;v<n;v++)
{
if(Data[u][v]==0) continue;

movingCE=false;// dinh u chua doc lap chua the them CE
Push(S,v);
Data[u][v]=Data[v][u]=0;//loai lien thuoc u,v( xoa canh noi u,v)
}
if(movingCE){
CE[countCE]=u;
countCE++;
}
}
///xuat chu trinh Euler
for(int i=0;i<countCE;i++)
{
cout<<CE[i]<<"=>";
}
}

////TIM DUONG DI EULER///////
//co duong di EULer => chi co 2 dinh bac le=> dinh ly=> ko cai
bool Kiem_Tra_DD_Euler(int Data[10][10],int n,int &u)// lay vi tri dinh bac le
{
int i,j,s,d=0;
for(int i=0;i<n;i++)
{
s=0;
for(int j=0;j<n;j++)
{
if(Data[i][j]!=0){
s+=1;
}
}
if(s%2!=0) {
d++;
u=i;
}
}
if(d!=2) return false;
return true;
}
//sau do duyet giong nhu tim chu trinh euler se ra dk duong di euler
// voi diem xuat phat la u tim dk o ham kiem tra

//=> de tim het cac duong di Euler=> ta tim 1 duong dau tien
// bien doi sang cac duong tiep bang de quy
//vi du tu A noi sang B hoac C=> chon dk B roi=> chuyen sang C

//i la vi tri xet neu co the thay dinh B bang C khong => tim duong di moi
void DDEuler(int b[10],int m,int Data[10][10],int n,int i)
{
for(int j=0;j<n;j++)
{
if(Data[b[i-1]][j]!=0 )
{                             
int k=Data[b[i-1]][j];
Data[b[i-1]][j]=Data[j][b[i-1]]=0;
b[i]=j;

if(i==m){// den dich roi=> xuat duong di euler
for(int i=0;i<m;i++)
{
cout<<b[i]<<"=>";
}
}

else{
DDEuler(b,m,Data,n,i+1);
}

// tra  lai bo du lieu nhu ban dau
Data[b[i-1]][j]=Data[j][b[i-1]]=k;
}
}
}

//////Hamington///////////
/// thoi bo

//////////TIM DUONG DI NGAN NHAT/////// thuat toan Dijkstra
void Dijkstra(int Data[10][10],int n,int s)// s la dinh ban dau
// tim duong di ngan nhat tu s toi cac dinh con lai d[v],truoc[v] dung nhu cu
{
int d[10],truoc[10],countT=n;
bool T[10];// danh dau cac dinh da dan nhan thanh cong(nhan be nhat)
//gan mac tam thoi tu s toi cac dinh con lai
for(int v=0;v<n;v++)
{
T[v]=false;
if(Data[v][s]!=0){
d[v]=Data[v][s];
    truoc[v]=s;
}
else{
d[v]=10000;// nhung dinh ko lien thuoc => cho so max
}
}
d[s]=0;
T[s]=true;
    countT--;
//sua lai nhan

    while(countT>0)
    {
    //b1 tim dinh u sao cho d[u]= min trong cac d[i]
    int min=20000,u;
for(int i=0;i<n;i++)
{
if(min>d[i] && !T[i]){
min=d[i];
u=i;
}
}
//u la dinh co d[u] nho nhat cut no khoi danh sach T
T[u]=true;
countT--;
// gan lai nhan
for(int v=0;v<n;v++)
{
if(Data[u][v]!=0 && !T[v] && d[v]>d[u]+Data[u][v])
{
d[v]=d[u]+Data[u][v];
truoc[v]=u;
}
}
}
 
//xuat bang nhan
for(int i=0;i<n;i++)
{
cout<<endl<<"kc tu "<<s<<"=>"<<i<<" : "<<d[i];
cout<<endl<<"duong di ngan nhat la: ";
cout<<i;
int j=truoc[i];
while(j!=s)
{
cout<<"=>"<<j;
j=truoc[j];
}
cout<<"=>"<<s;
}
}


int main()
{
int solt=0;
int soDinh,Data[10][10];
bool ChuaXet[10];
int ChuaXet_Lt[10],Truoc[10];
Queue Q;

Nhap(soDinh,Data);

// for(int i=0;i<soDinh;i++)
// {
// ChuaXet[i]=true;
// ChuaXet_Lt[i]=0;
// Truoc[i]=-1;
// }

// for(int i=0;i<soDinh;i++)
// {
// if(ChuaXet[i]){
// DFS(Data,soDinh,i,ChuaXet);// DFS
// BFS(Data,soDinh,i,ChuaXet);// BFS
// BFS_DD(Data,soDinh,i,ChuaXet,Truoc);
// }
// if(ChuaXet_Lt[i]==0){ ////duyet cac thanh phan lien thong
// solt=solt+1;
// BFS_LT(Data,soDinh,i,ChuaXet_Lt,solt);
// }
// cout<<endl;
// }
//    if(Kiem_Tra_CC_Euler(Data,soDinh))    Euler_Cycle(Data,soDinh);
//    else    cout<<" Khong co Chu Trinh Euler";
Dijkstra(Data,soDinh,1);
return 0;
}

////Phần cây khung bé nhất( Kruskal và Prim)

+ file: Text:
12
7
1 4 1
6 7 1
4 6 2
1 2 3
1 6 3
3 4 3
2 3 4
3 7 5
5 6 5
2 6 6
4 5 6

3 5 7
+ Code:(chu yeu dua vao phan link huong dan)
////TOAN ROI RAC PHAN CAY/////
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<math.h>
using namespace std;
//v so dinh, nEgle so canh,Mst: cay bao trum,parent[i] luu cha cua dinh i nao do
int V,nEgle,MST[20][20],Mat[20][20],parent[20];
int Cost[20],soDinh;// Mat :ma tran trong so ,Cost: gia tri,
bool ChuaXet[20];
//cau truc 1 canh su dung Kruskal
struct Egle
{
int u,v,weight;
};
Egle egle[20];
////////Nhap tu File//////////
// nhap bang danh sach ke///
void Nhap_Ds()
{
fstream f;
f.open("dothi1.txt");
f>>nEgle;
f>>V;
for(int i=1;i<=V;i++) 
for(int j=1;j<=V;j++)
Mat[i][j]=0;
for(int i=0;i<nEgle;i++)
{
f>>egle[i].u;
f>>egle[i].v;
f>>egle[i].weight;
Mat[egle[i].u][egle[i].v]=Mat[egle[i].v][egle[i].u]=egle[i].weight;
}
}

//sap xep cac canh theo chieu tang dan trong so// sap xep chon
void Sort()// file da sap xep tu truoc nen ko can dung cung dk
{
for(int i=0;i<nEgle-1;i++)
{
for(int j=i;j<nEgle;j++)
{
if(egle[i].weight>egle[j].weight)
{
//doi cho 2 egle
Egle hold=egle[i];
egle[i]=egle[j];
egle[j]=hold;
}
}
}
}
//tim nut cha cua 1 dinh...=> neu 2 dinh khong cung nut cha có the noi vs nhau
//tranh viec tao ra 1 chu trinh
int Find_Set(int x)
{
while(parent[x]>0)//vi -1 la ve trang thai ban dau=> cai dat the
{
x=parent[x];
}
return x;
}
//ket noi 2 nut voi nhau// de chon no vao cay khung Min
void Union(int u,int v)//=> ham nay tu nghi=> chac la co loi
{//ban dau tat ca cac parent bang -1
if(parent[u]==-1 && parent[v]!=-1)// neu 1 nut co cha= 1 nut khac
{ // va 1 nut chua co(=-1)=> nut nay phai noi vao nut kia
parent[u]=v;
}
else if(parent[u]!=-1 && parent[v]==-1){// nguoc lai
parent[v]=u;
}
else if(parent[v]==-1 && parent[u]==-1)// 2 nut cung co cha
{
if(u>v) parent[v]=u;// thang co so hieu lon hon se lam cha
else parent[u]=v;
}
else{//2 nut cung la con
if(u>v) {
int dad=Find_Set(v);//tim to tien cu cua con be
parent[v]=u;//gan cha cua con be = thang lon
parent[dad]=v; //gan (to tien cu) = con be (he he)
}//=> vay la tat ca cung 1 to tien hihi
else {
int dad=Find_Set(u);
parent[u]=v;
parent[dad]=u;
}
}
}

void Union2(int u,int v)//u va v la 2 dinh goc cua 2 phe
{
int x=parent[u]+parent[v];
if(parent[u]>parent[v])// noi goc co cha lon hon vao goc co cha nho hon
{// cha cua 2 goc nay thi luon am,,, nen thang cha con lai cang am tiep
parent[v]=x;
parent[u]=v;
}
else{
parent[u]=x;
parent[v]=u;
}
}

void Kruskal()
{
//khai bao nut cha
for(int i=1;i<=V;i++)
{
parent[i]=-1;
}
Sort();// sap xep

for(int i=0;i<nEgle;i++)
{
int u=Find_Set(egle[i].u);//tim cha cua nut u cua tung canh
int v=Find_Set(egle[i].v);//tim cha cua nut v cua tung canh
//neu u=v chung to 2 nut cua canh egle[i] cung goc=> 1 chu trinh
//=> loai canh Egle[i] ko cho no vao Cay khung min
if(u!=v){
int x=egle[i].u;
int y=egle[i].v;
//luu lai cay bao trum
MST[x][y]=MST[y][x]=egle[i].weight;
//ket noi 2 goc voi nhau => canh egle[i] duoc chon cho cay khung min
Union2(u,v);
}
}
}

int Extract_Min()//tim dinh co Cost min trong so cac dinh chua dk chon=> Thu
{    // b1: dinh dau tien voi Cost=0=> dinh tiep theo...
int min=20000,u;
for(int i=1;i<=V;i++)
{
if(ChuaXet[i] && Cost[i]<min)
{
min=Cost[i];
u=i;
}
}
return u;
}

void Prim(int start)
{
for(int i=1;i<=V;i++)
{
parent[i]=-1;
ChuaXet[i]=true;
Cost[i]=20000;//1 con so intMax nao do( rat lon)
}

Cost[start]=0;

for(int i=1;i<=V;i++)
{
int u=Extract_Min();// dinh co Cost nho nhat=> xem no co dk lam cha cua dinh khac ko
ChuaXet[u]=false;

for(int v=1;v<=V;v++)// duyet cac dinh ke voi no,chua dk chon
{
if(v==u) continue;
if(ChuaXet[v] && Mat[u][v]!=0 && Mat[u][v]<Cost[v])
{//tat ca cac dinh ban dau deu duoc danh so Cost
// vi Cost ban dau =20000,danh dau cha cua no
Cost[v]=Mat[u][v];
parent[v]=u;
}
// neu xet lan tiep theo voi cha khac, cost nho hon=> chon cha moi(hehe)
// tu do ta co duoc Cay khung nho nhat tu danh sach CHa(ngon)
}
}

// dua parent tim ra cay bao trum nho nhat
for(int i=1;i<=V;i++)
{
if(i==start) continue;
MST[parent[i]][i]=MST[i][parent[i]]=Mat[parent[i]][i];
}
}

int main()
{
Nhap_Ds();
Sort();

    Kruskal();
    //Prim(1);
    //cay khung nho nhat co dang ma tran
    for(int i=1;i<=V;i++)
    {
    for(int j=1;j<=V;j++)
    {
    cout<<MST[i][j]<<"  ";
}
cout<<endl;
}

system("pause");
return 0;
}