Bài thực hành giải thuật.

Xin lỗi vì diễn đàn này nhưng post bài môn giải thuật.

Bạn nào có đầy đủ các bài thực hành môn giải thuật thì chia sẻ cho mình với, mình đang rất cần. Cảm ơn nhiều.

Sắp xếp bậc tăng
#include<iostream.h>
#include<conio.h>

#define MAX 30
#define indef 32655

// dinh nghia 1 ds cac dinh

struct GRAPH {
int numv;//so dinh
int g[MAX][MAX]; // ma tran ke cua do thi
};


GRAPH G;
struct DINH
{
int dinh;
int bac;
};

DINH d[MAX];
//int d[MAX];//khoang cach giua 2 dinh

void init(GRAPH &a)
{
int i,j;
cout<<"given number of vertices of graph:"; cin>>a.numv;
cout<<"input adjacent matrix of graph:\n";
for(i=1;i<=a.numv;i++)
{
for(j=i+1;j<=a.numv;j++)
{
cout<<"a["<<i<<","<<j<<"]=";
cin>>a.g[i][j];
a.g[j][i]=a.g[i][j];
}
a.g[i][i]=0; cout<<"\n";
}

}
void print_data(GRAPH a)
{
int i,j;
cout<<"adjacent matrix:\n";
for(i=1;i<=a.numv;i++)
{
for(j=1;j<=a.numv;j++)
cout<<a.g[i][j]<<" ";
cout<<"\n";
}
}

int baccuadinh(GRAPH a, int s)
{
int d =0;
for(int i=1;i<=a.numv;i++)
d+=a.g[s][i];
return d;
}
void mangbacG(GRAPH a)
{
for(int i=1;i<=a.numv;i++)
{
d[i].dinh=i;
d[i].bac=baccuadinh(G,i);
}

}
void xuatmangbac(DINH d[], GRAPH a)
{
for(int i=1;i<=a.numv;i++)
{
cout<<d[i].bac<<" - "<<d[i].dinh<<endl;
//cout<<d[i].dinh;

}

}
void sapbactang(DINH d[],GRAPH a)
{
int temp;
for(int i=1;i<a.numv;i++)
for(int j=i+1;j<=a.numv;j++)
{
if(d[i].bac>d[j].bac)
{
temp=d[i].bac;
d[i].bac=d[j].bac;
d[j].bac=temp;
}
}
}
void main()
{

init(G);
print_data(G);
mangbacG(G);
//xuatmangbac(d,G);
sapbactang(d,G);
xuatmangbac(d,G);

}

Thuat toan Prim
// Input must be a connected undirect graph
#include<iostream.h>
#include<conio.h>
#define MAX 30
#define false 0
#define true 1
#define MAXINT 32560

typedef int GRAPH[MAX][MAX];

struct Tree_Edge{
int x,y;
};
typedef struct NODE *link;
struct NODE{
int v;
link next;
};
typedef link SET;
GRAPH G;
SET V;
struct Tree_Edge T[MAX];
int key[MAX], before[MAX];
int n;
void Set_init(SET &S)
{
S=NULL;
}
void Insert_Set(int x, SET & S)
{
SET q;
q=new(NODE);
q->v=x;
q->next=S;
S=q;
}

void init(GRAPH &c)
{
int i,j;
cout<<"Given number of vertices of graph:"; cin>>n;
cout<<"Input weight matrix for graph:\n";
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
cout<<"c["<<i<<","<<j<<"]="; cin>>c[i][j]; c[j][i]=c[i][j];
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if(c[i][j]==0) c[i][j]=MAXINT;
Set_init(V);
for(i=1;i<=n;i++) Insert_Set(i,V);
}
void print_data(GRAPH c)
{
int i,j;
cout<<"weight matrix\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) if (c[i][j]==MAXINT) cout<<char(236)<<" "; else cout<<c[i][j]<<" ";
cout<<"\n";
}
}

void Delete(int x,SET &l)
{
SET p;
if(l!=NULL)
if(x==(l->v)){ p=l;l=l->next; delete p;}
else Delete(x,l->next);
}
void result()
{
int k;
cout<<"Minimal spanning tree:\n";
cout<<"{";
for(k=1;k<=n-2; k++)
{
cout<<"("<<T[k].x<<","<<T[k].y<<"), ";
}
cout<<"("<<T[n-1].x<<","<<T[n-1].y<<")}";
cout<<endl;
}
void Prim(GRAPH G, int s)
{
int k,u,i,min;
SET Q;
key[s]=0; before[s]=s;
Delete(s,V);
Q=V;
while(V!=NULL)
{
key[V->v]=G[s][V->v]; before[V->v]=s;
V=V->next;
}
i=0;

while(Q!=NULL)
{
V=Q; min=MAXINT;
while(V!=NULL)
{
k=V->v;
if(key[k]<min){min=key[k]; u=k;}
V=V->next;
}
i=i+1;
T[i].x=u; T[i].y=before[u]; Delete(u,Q);
V=Q;
while(V!=NULL)
{
if(key[V->v]>G[u][V->v])
{
key[V->v]=G[u][V->v];
before[V->v]=u;
}
V=V->next;
}
}
result();
}
void main()
{
int s;
init(G);
print_data(G);
cout<<"Select root vertex of MST:"; cin>>s;
Prim(G,s);
getch();
}

Thuat toán BFS
#include<iostream.h>
#include<conio.h>

#define MAX 30
#define indef 32655
#define white 0
#define black -1
#define gray 1
#define NIL -1

// dinh nghia 1 ds cac dinh
typedef struct node *LIST;
struct node{
int v;
LIST next;
};
// dinh nghia 1 ds hang doi:
typedef struct NODE_LIST{
LIST f,r;
}QUEUE;
// DINH NGHIA DO THI:
struct GRAPH {
int numv;//so dinh
int g[MAX][MAX]; // ma tran ke cua do thi
};

struct DEGREE {
int v;
int degree;
};

GRAPH G;
DEGREE dv[MAX];
int d[MAX];//khoang cach giua 2 dinh
int color[MAX];
int befor[MAX];
int value=0;

void queueinit(QUEUE &Q)
{
Q.f=Q.r=NULL;
}
int queueempty(QUEUE Q)
{
if(Q.r==NULL) return 1;
else return 0;
}
void push_queue(int x, QUEUE &Q)
{
LIST q;
q=new(node);
q->v=x;
q->next=NULL;
if(Q.r==NULL) Q.f=q;
else Q.r->next=q;
Q.r=q;
}
int pop_queue(QUEUE &Q)
{
int s;
LIST q;
if(!queueempty(Q))
{
q=Q.f;
s=q->v;
Q.f=q->next;
if(Q.f==NULL) Q.r=NULL;
delete q;
}
return s;

}
void init(GRAPH &a)
{
int i,j;
cout<<"given number of vertices of graph:"; cin>>a.numv;
cout<<"input adjacent matrix of graph:\n";
for(i=1;i<=a.numv;i++)
{
for(j=i+1;j<=a.numv;j++)
{
cout<<"a["<<i<<","<<j<<"]=";
cin>>a.g[i][j];
a.g[j][i]=a.g[i][j];
}
a.g[i][i]=0; cout<<"\n";
}

}
void print_data(GRAPH a)
{
int i,j;
cout<<"adjacent matrix:\n";
for(i=1;i<=a.numv;i++)
{
for(j=1;j<=a.numv;j++)
cout<<a.g[i][j]<<" ";
cout<<"\n";
}
}

void BFS(GRAPH a, int s)
{
int u,v;
QUEUE Q;
for(u=1;u<=G.numv;u++)
{
color[u]=white;

d[u]=indef;//khoang cach =vo cuc
befor[u]=NIL;
}
color[s]=gray;
d[s]=0;
befor[s]=NIL;
queueinit(Q);
push_queue(s,Q);
while(!queueempty(Q))
{
u=pop_queue(Q);
//cout<<"("<<u<<", "<<d[u]<<")\n";
//begin
//if (u == t)
// return d[u];
// end
for(v=1;v<=a.numv;v++)
if((a.g[u][v]==1)&&(color[v]==white))
{
color[v]=gray;
d[v]=d[u]+1;
befor[v]=u;
push_queue(v,Q);
}
color[u]=black;
}
}
//==============Quic Sort===============
void SWAP(int &a, int &b)
{
int c = a;
a = b;
b = c;
}
int PARTION(DEGREE A[], int p,int r)
{
int x = A[r].degree;//degree of vertix
int i = p - 1;
for (int j = p; j<r; j++)
{
if (A[j].degree <= x)
{
i++;
SWAP(A[i].degree, A[j].degree);
SWAP(A[i].v, A[j].v);
}
}
SWAP(A[i+1].degree, A[r].degree);
SWAP(A[i+1].v, A[r].v);
return i+1;
}
void Increase(int &count)
{
count++;
}
void QuickSort(DEGREE A[], int p, int r)
{
int q;
Increase(value);
if (p<r)
{
q = PARTION(A, p, r);
cout<<"q="<<q<<"\n";
QuickSort(A, p, q-1);
QuickSort(A, q+1, r);
}

}
//==============End=====================
int baccuadinh(GRAPH a, int s)
{
int d =0;
for(int i=1;i<=a.numv;i++)
d+=a.g[s][i];
return d;
}

int Min_Path(GRAPH G, int s, int t)
{
BFS(G, s);
return d[t];
}

void Make_Vertix_Degree(GRAPH G, DEGREE dv[])
{
for(int i = 1; i<G.numv; i++)
{
dv[i].degree = baccuadinh(G, i);
dv[i].v = i;
}
}

void PRINT_OUT_ARRAY(DEGREE dv[MAX])
{
for (int i=1; i<=5; i++)
{
cout<<"Dinh theo bac tang dan \n";
cout<<"Dinh="<<dv[i].v<<" bac="<<dv[i].v<<"\n";
}
}

void main()
{
int u;
int test;
int s;
int t;
DEGREE de[MAX];
init(G);
print_data(G);
//cout<<"nhap dinh can tinh bac:";
//cin>>u;
//cout <<"\n";
//cout<<baccuadinh(G,u);
//BFS(G,4);
//===Begin Bai 2=================
cout<<"Nhap dinh bat dau:";cin>>s;
cout<<"Nhap dinh ket thuc:";cin>>t;
cout<<"Min_Path="<<Min_Path(G, s, t);
//===Begin Bai 2=================

//===Begin Bai 1====
//Make_Vertix_Degree(G, de);
//QuickSort(de, 0, MAX);
//===End Bai 2======
cin>>test;
}