CONTOH 1 : DFS
#include <iostream>
#include <conio>
class vertex
{
public:
char lab;
bool condition;
vertex *parent;
vertex(char l)
{
lab=l;
}
};
class graph
{
public:
vertex** addvertex;
int **add_jacent;
void Addvertex(char a);
void addedge(int st, int end);
void ALL_DFS();
graph()
{
addvertex=new vertex*[20];
add_jacent=new int*[20];
for(int i=0;i<20;i++)
{
add_jacent[i]=new int[20];
for(int j=0;j<20;j++)
{
add_jacent[i][j]=0;
}
}
nvert=0;
}
private:
void display(int v);
int nvert;
void DFS_search(vertex *v, int j);
};
void graph::Addvertex(char a)
{
addvertex[nvert++]=new vertex(a);
}
void graph::addedge(int st, int end)
{
add_jacent[st][end]=1;
add_jacent[end][st]=1;
}
void graph::display(int v)
{
cout<<addvertex[v]->lab<<" ";
}
void graph::ALL_DFS()
{
cout<<"Pencarian jalur dengan metode DFS :"<<endl;
for(int i=0;i<nvert;i++)
{
addvertex[i]->condition=false; /// kondisi
addvertex[i]->parent=NULL; /// keadaan awal
}
for(int j=0;j<nvert;j++)
{
if(addvertex[j]->condition == false)
{
DFS_search(addvertex[j],j);
}
}
}
void graph::DFS_search(vertex *vert,int index)
{
vert->condition=true;
display(index);
for(int i=0;i<nvert;i++)
{
if((add_jacent[index][i]==1) && (addvertex[i]->condition == false))
{
addvertex[i]->parent=vert;
DFS_search(addvertex[i],i);
}
}
}
void main()
{
graph *a=new graph();
a->Addvertex('A'); ///0
a->Addvertex('B'); ///1
a->Addvertex('C'); ///2
a->Addvertex('D'); ///3
a->Addvertex('E'); ///4
a->Addvertex('F'); ///5
a->Addvertex('G'); ///6
a->Addvertex('H'); ///7
a->Addvertex('I'); ///8
a->Addvertex('J'); ///9
a->Addvertex('K'); ///10
a->addedge(0, 1); ///AB
a->addedge(0, 2); ///AC
a->addedge(1, 3); ///BD
a->addedge(1, 4); ///BE
a->addedge(2, 5); ///CF
a->addedge(2, 6); ///CG
a->addedge(3, 7); ///DH
a->addedge(3, 8); ///DI
a->addedge(4, 9); ///EJ
a->addedge(5, 10); ///FK
a->ALL_DFS();
cout<<endl;
cout<<endl;
cout<<"Hasil Pencarian DFS, sesuai dengan Graph pada Gambar 11.3"<<endl;
getch();
}
===================================
CONTOH 2 : DFS KOTA
#include <iostream>
#include <conio>
//#include <cstring>
#include <string>
class vertex
{
public:
char lab;
string kota;
bool condition;
vertex *parent;
vertex(char l, string k)
{
lab=l;
kota=k;
}
};
class graph
{
public:
vertex** addvertex;
int **add_jacent;
void Addvertex(char a, string kota);
void addedge(int st, int end);
void ALL_DFS();
graph()
{
addvertex=new vertex*[20];
add_jacent=new int*[20];
for(int i=0;i<20;i++)
{
add_jacent[i]=new int[20];
for(int j=0;j<20;j++)
{
add_jacent[i][j]=0;
}
}
nvert=0;
}
private:
void display(int v);
int nvert;
void DFS_search(vertex *v, int j);
};
void graph::Addvertex(char a, string k)
{
addvertex[nvert++]=new vertex(a,k);
}
void graph::addedge(int st, int end)
{
add_jacent[st][end]=1;
add_jacent[end][st]=1;
}
void graph::display(int v)
{
cout<<addvertex[v]->lab<<" "<<addvertex[v]->kota<<" -->";
}
void graph::ALL_DFS()
{
cout<<"Pencarian jalur dengan metode DFS :"<<endl;
for(int i=0;i<nvert;i++)
{
addvertex[i]->condition=false; /// kondisi
addvertex[i]->parent=NULL; /// keadaan awal
}
for(int j=0;j<nvert;j++)
{
if(addvertex[j]->condition == false)
{
DFS_search(addvertex[j],j);
}
}
}
void graph::DFS_search(vertex *vert,int index)
{
vert->condition=true;
display(index);
for(int i=0;i<nvert;i++)
{
if((add_jacent[index][i]==1) && (addvertex[i]->condition == false))
{
addvertex[i]->parent=vert;
DFS_search(addvertex[i],i);
}
}
}
void main()
{
graph *a=new graph();
a->Addvertex('A',"Mataram"); ///0
a->Addvertex('B',"Jalan Lingkar"); ///1
a->Addvertex('C',"Patung Giri menang"); ///2
a->Addvertex('D',"Perbatasan Lombar-Loteng"); ///3
a->Addvertex('E',"BIL"); ///4
a->Addvertex('F',"Tanah Awu"); ///5
a->Addvertex('G',"Rembitan"); ///6
a->Addvertex('H',"Sade"); ///7
a->Addvertex('I',"Tanjung Aan"); ///8
a->Addvertex('J',"Kute"); ///9
a->addedge(0, 1); ///AB
a->addedge(0, 6); ///AD
a->addedge(1, 2); ///BC
a->addedge(1, 3); ///BD
a->addedge(6, 7); ///CG
a->addedge(2, 4); ///CF
a->addedge(2, 3); ///CD
a->addedge(3, 4); ///DE
a->addedge(3, 5); ///EF
a->addedge(4, 5); ///EH
a->addedge(7, 8); ///FH
a->addedge(7, 9); ///GH
a->addedge(8, 9); ///GI
a->ALL_DFS();
getch();
}
==============================================
CONTOH 3 : DIJSKTRA
#include <iostream>
#include <conio>
#include <string>
class vertex
{
public:
char lab;
vertex *parent;
int distance;
bool value;
vertex(char a)
{
lab=a;
}
};
class edge
{
public:
int vert;
int weight;
edge(int v,int w)
{
vert=v;
weight=w;
}
};
class PQ
{
public:
int size;
edge **add_edge;
int top;
PQ(int i, int x)
{
size=i;
add_edge=new edge*[size];
top=x;
}
int isempty()
{
if(top<=0)
return 1;
else
return 0;
}
void insert(edge *item)
{
if(isempty()==1)
{
add_edge[top++]=item;
}else
{
int step=0;
int i;
for(i=0;i<top;i++)
{
if((add_edge[i]->vert) == (item->vert) )
{
step=1;
int ganti=item->weight;
if((add_edge[i]->weight) >= ganti)
{
add_edge[i]->weight=ganti;
break;
}
}else if((add_edge[i]->weight) >= (item->weight))
{
break;
}
}
if(step==0)
{
for(int j=top;j>i;j--)
{
add_edge[j]=add_edge[j-1];
}
add_edge[i]=item;
top++;
}
}
}
edge* pop()
{
edge *temp;
if(isempty()==1)
{
cout<<"kosong";
}else
{
temp=add_edge[0];
for(int i=1;i<top;i++)
{
add_edge[i-1]=add_edge[i];
}
top--;
}
return temp;
}
};
class graph
{
public:
void Addvertex(char v);
void addedge(int s,int e,int w);
void Djikstra();
graph()
{
addvertex=new vertex*[20];
add_adjacent=new int*[20];
for(int i=0;i<20;i++)
{
add_adjacent[i]=new int[20];
for(int j=0;j<20;j++)
{
add_adjacent[i][j]=0;
}
}
Q=new PQ(200,0);
addjacent=0;
nvert=0;
}
private:
void displayvert(vertex *v);
void relaxation(int st,int end,int dist);
vertex **addvertex;
int **add_adjacent;
PQ *Q;
int addjacent;
int nvert;
};
void graph::Addvertex(char lab)
{
addvertex[nvert++]=new vertex(lab);
}
void graph::addedge(int st, int end, int w)
{
this->add_adjacent[st][end]=w;
addjacent++;
}
void graph::displayvert(vertex *disp)
{
if(disp->parent != NULL)
{
displayvert(disp->parent);
cout<<disp->lab<<" ";
}
}
void graph::relaxation(int st,int end,int dist)
{
int destination=addvertex[end]->distance;
int start=addvertex[st]->distance;
if(destination > (start+dist))
{
addvertex[end]->distance=start+dist;
addvertex[end]->parent=addvertex[st];
}
}
void graph::Djikstra()
{
for(int i=0;i<nvert;i++)
{
addvertex[i]->distance=99;
addvertex[i]->parent=NULL;
addvertex[i]->value=false;
}
int current=0;
addvertex[0]->distance=0;
edge *start=new edge(current,0);
Q->insert(start);
while(Q->isempty() !=1 )
{
addvertex[current]->value=true;
for(int j=0;j<nvert;j++)
{
if(j==current)
continue;
if(addvertex[j]->value==true)
continue;
int dist=add_adjacent[current][j];
if(dist==0)
continue;
relaxation(current,j,dist);
int weight=addvertex[j]->distance;
edge *path=new edge(j,weight);
Q->insert(path);
}
edge *pop=Q->pop();
current=pop->vert;
int w=pop->weight;
}
for(int i=0;i<nvert;i++)
{
cout<<"Biaya untuk ke vertex "<<addvertex[i]->lab<<" :"
<<addvertex[i]->distance<<endl;
cout<<"Jalur :";
displayvert(addvertex[i]);
cout<<" "<<endl;
}
}
void main()
{
graph *a=new graph();
/*
a->Addvertex('A'); ///0
a->Addvertex('B'); ///1
a->Addvertex('C'); ///2
a->Addvertex('D'); ///3
a->Addvertex('E'); ///4
a->Addvertex('F'); ///5
a->Addvertex('G'); ///6
a->Addvertex('H'); ///7
a->Addvertex('I'); ///8
a->Addvertex('J'); ///9
a->addedge(0,1,2); ///AB
a->addedge(0,2,12); ///AC
a->addedge(0,4,6); ///AE
a->addedge(1,3,1); ///BD
a->addedge(1,4,3); ///BE
a->addedge(2,8,3); ///CI
a->addedge(3,4,1); ///DE
a->addedge(3,5,7); ///DF
a->addedge(3,7,5); ///DH
a->addedge(4,2,2); ///EC
a->addedge(4,8,6); ///EI
a->addedge(4,6,9); ///EG
a->addedge(6,7,5); ///GH
a->addedge(6,9,2); ///GJ
a->addedge(7,5,1); ///HF
a->addedge(7,9,2); ///HJ
a->addedge(8,6,1); ///IG
a->addedge(8,9,6); ///IJ
*/
a->Addvertex('A'); ///1
a->Addvertex('B'); ///2
a->Addvertex('C'); ///3
a->Addvertex('D'); ///4
a->Addvertex('E'); ///5
a->Addvertex('F'); ///6
a->addedge(0,1,10); ///AB
a->addedge(0,2,5); ///AC
a->addedge(1,2,2); ///BC
a->addedge(1,3,1); ///BD
a->addedge(2,1,3); ///CB
a->addedge(2,3,9); ///CD
a->addedge(2,4,2); ///CE
a->addedge(3,4,2); ///DE
a->addedge(3,5,12); ///DF
a->addedge(4,0,7); ///EA
a->addedge(4,3,6); ///ED
a->addedge(4,5,15); ///EF
cout<<"Implementasi Algoritma Djikstra :"<<endl;
cout<<endl;
a->Djikstra();
getch();
}
=================================================
CONTOH 4 : KRUSKAL
#include <iostream>
#include <conio>
#include <string>
class vertex
{
public:
char lab;
string kota;
vertex *parent;
int rank;
vertex(char l,string k)
{
lab=l;
kota=k;
}
};
class edge
{
public:
int start;
int weight;
int end;
edge(int s,int e,int w)
{
start=s;
end=e;
weight=w;
}
};
class PQ
{
public:
int size;
edge **add_edge;
int top;
PQ(int i, int x)
{
size=i;
add_edge=new edge*[size];
top=x;
}
int isempty()
{
if(top<=0)
return 1;
else
return 0;
}
void insert(edge *item)
{
if(isempty()==1)
{
add_edge[top++]=item;
}else
{
int i;
for(i=0;i<top;i++)
{
if(add_edge[i]->weight>=item->weight)
break;
}
for(int j=top;j>i;j--)
{
add_edge[j]=add_edge[j-1];
}
add_edge[i]=item;
top++;
}
}
};
class graph
{
public:
vertex **addvertex;
int **add_adjacent;
int nvert,addjacent;
void Addvertex(char v,string kota);
void addedge(int s,int e,int w);
void kruskal();
graph()
{
addvertex=new vertex*[20];
add_adjacent=new int*[20];
for(int i=0;i<20;i++)
{
add_adjacent[i]=new int[20];
for(int j=0;j<20;j++)
{
add_adjacent[i][j]=1000000;
}
}
x=new PQ(200,0);
nvert=0;
addjacent=0;
}
private:
void makeset(vertex *v);
void displayvert(int v);
void displayvertex(int v);
vertex *findset(vertex *v);
void uni(vertex *x,vertex *y);
void link(vertex *x,vertex *y);
PQ *x;
};
void graph::Addvertex(char lab, string k)
{
addvertex[nvert++]=new vertex(lab,k);
}
void graph::addedge(int st, int end, int w)
{
this->add_adjacent[st][end]=w;
this->add_adjacent[end][st]=w;
addjacent++;
edge *path=new edge(st,end,w);
x->insert(path);
}
void graph::displayvert(int v)
{
cout<<addvertex[v]->kota;
}
void graph::displayvertex(int v)
{
cout<<addvertex[v]->lab<<"";
}
void graph::makeset(vertex *v)
{
v->parent=v;
v->rank=0;
}
vertex* graph::findset(vertex *v)
{
if(v != v->parent)
{
v->parent=findset(v->parent);
}
return v->parent;
}
void graph::link(vertex *x, vertex *y)
{
if(x->rank > y->rank)
{
y->parent=x;
}else
{
x->parent=y;
if(x->rank == y->rank)
y->rank=y->rank+1;
}
}
void graph::uni(vertex *x, vertex *y)
{
link(findset(x),findset(y));
}
void graph::kruskal()
{
int total=0;
for(int i=0;i<nvert;i++)
{
makeset(addvertex[i]);
}
for(int i=0;i<addjacent;i++)
{
int start=x->add_edge[i]->start;
int end=x->add_edge[i]->end;
vertex *a;
a=findset(addvertex[start]);
vertex *b;
b=findset(addvertex[end]);
if(a->lab != b->lab)
{
uni(addvertex[start], addvertex[end]);
displayvert(start);
cout<<"-";
displayvert(end);
cout<<"(";
displayvertex(start);
displayvertex(end);
cout<<")";
// cout<<add_adjacent[start][end]<<" ";
total=total+this->add_adjacent[start][end];
}
}
cout<<endl;
cout<<"Nilai Total keseluruhan MST :"<<total;
}
void main()
{
cout<<"Implementation of Graph using Kruskal Algorithm "<<endl;
graph *a=new graph();
a->Addvertex('A',"dompu"); ///0
a->Addvertex('B',"Mataram"); ///1
a->Addvertex('C',"denpasar"); ///2
a->Addvertex('D',"banyuwangi"); ///3
a->Addvertex('E',"surabaya"); ///4
a->Addvertex('F',"Yogyakarta"); ///5
a->Addvertex('G',"semarang"); ///6
a->Addvertex('H',"Jakarta"); ///7
a->Addvertex('I',"Bandung"); ///8
a->addedge(0, 1, 6); ///AB
a->addedge(0, 3, 8); ///AD
a->addedge(1, 2, 1); ///BC
a->addedge(1, 3, 10); ///BD
a->addedge(2, 6, 20); ///CG
a->addedge(2, 5, 15); ///CF
a->addedge(2, 3, 21); ///CD
a->addedge(3, 4, 14); ///DE
a->addedge(4, 5, 3); ///EF
a->addedge(4, 7, 5); ///EH
a->addedge(5, 7, 11); ///FH
a->addedge(6, 7, 13); ///GH
a->addedge(6, 8, 18); ///GI
a->addedge(7, 8, 17); ///HI
a->kruskal();
getch();
}
Tidak ada komentar:
Posting Komentar