Skip to content

Colouring graph dengan C++

September 2, 2009

#include

#include

//library untuk file

#include

void main()

{

char pilih;

do

{

clrscr();

char filename[100];

cout<<"==================="<<endl;

cout<<"| Program |"<<endl;

cout<<"| Colouring Graph |"<<endl;

cout<<"==================="<<endl;

cout<<endl;

ifstream infile;

//membuka file

do

{

cout<<"Masukkan nama file sebagai inputan program : ";

cin>>filename;

infile.open(filename);

//validasi file

if (!infile)

{

cout<<"File tidak ada coba perikasa kembali!"<<endl;

}

}while (!infile);

typedef struct{

int stat,color;

int check;

char name[20];

}idver;

int l[20];

int temp2,n1[20];

int i,j,k,bar,kol,temp;

idver vertex[20][20],vert[20];

//membaca isi file (baris dan kolom

infile>>bar;

infile>>kol;

cout<<kol<<" vertex ditemukan"<<endl;

cout<<"Silahkan beri nama masing – masing vertex"<<endl;

for (i=0; i<kol; i++)

{

cout<<"Vertex ke-"<<(i+1)<<" : ";

cin>>vert[i].name;

}

//membaca isi file (status vertex, 0 atau 1)

for (i=0; i<bar; i++)

{

n1[i]=0;

for (j=0; j<kol; j++)

{

infile>>temp;

vertex[i][j].stat = temp;

//menghitung nilai satu

if (temp==1)

n1[i]++;

}

}

//mencari baris yang paling banyak memiliki satu

int max = -1;

for (i=0;i<bar;i++)

{ if (n1[i] > max)

{

max=n1[i];

}

}

int res=max;

int incolor =1;

for (i=0; i<kol; i++)

{

for (j=i+1; j<kol; j++)

{

vertex[i][j].check =0;

}

vert[i].color=0;

}

max=-1;

for (i=0; i<kol; i++)

{

/*for (j=0; j<kol; j++)

{

for (k=j+1; k<kol; k++)

{

if (vertex[j][k].connect ==0)

if ((vertex[i][j].stat==1) && (vertex[i][k].stat==1))

vertex[i][j].connect =1;

}

}

*/

vert[i].color=0;

}

//pewarnaan

for (i=0; i<bar; i++)

{

for (j=0; j<kol; j++)

{

for (k=j+1; k<kol; k++)

{

if ((n1[i]>=max))

{

if (vertex[j][k].check == 0)

{

if((vertex[i][j].stat ==1) && (vertex[i][k].stat ==1))

{

vertex[j][k].check =1;

if (vert[j].color == 0)

{

vert[j].color = incolor;

vert[k].color = incolor + 1;

}

else

{

vert[k].color = vert[j].color + 1;

}

}

else

{

if ((vertex[i][j].stat==1) && (vertex[i][k].stat==0))

{

if (vert[j].color == 0)

{

vert[j].color = incolor;

vert[k].color = incolor;

}

else

{

vert[k].color = vert[j].color;

}

}

else

{

if (j==0)

vert[k].color = vert[j].color=incolor;

}

}

}

}

}

}

max=n1[i];

}

cout<<"—————————"<<endl;

cout<<res<<" warna ditemukan"<<endl;

cout<<"Lanjut untuk detail"<<endl;

getch();

typedef struct {

char nama[10];

}warna;

//list warna

warna color[10];

strcpy(color[1].nama,”Merah”);

strcpy(color[2].nama,”Jingga”);

strcpy(color[3].nama,”Kuning”);

strcpy(color[4].nama,”Hijau”);

strcpy(color[5].nama,”Biru”);

strcpy(color[6].nama,”Nila”);

strcpy(color[7].nama,”Ungu”);

cout<<endl;

for (i=0; i<kol; i++)

{

if (res==kol)

cout<<vert[i].name<<" dengan warna "<<color[i+1].nama<<endl;

else

cout<<vert[i].name<<" dengan warna "<<(color[vert[i].color].nama)<<endl;

}

cout<<"————————————"<<endl;

cout<<"Keterangan"<<endl;

for (i=0; i<kol; i++)

{

if ((vert[i].color == vert[i+1].color) && (kol!=res))

{

cout<<vert[i].name<<" warnanya boleh sama dengan "<<vert[i+1].name<<" karena tidak adjecent(bertetanggaan)"<<endl;

}

else if (kol==res)

{

cout<<"Semua vertex harus memiliki warna berbeda"<<endl;

i=kol;

}

}

infile.close();

cout<<"====================================================================="<<endl;

cout<<"Ulang program ? (y/n) : ";

cin>>pilih;

}while ((pilih==’y’) || (pilih==’Y’));

}

Untuk adk2 smster 3 maap karena program yg di atas gak jalan..Makanya jangan maen copy aj..

Karena ak baek hati ini klik aja di sini untuk donlod program nya, tp pake C++..

Jangan lupa komen yaw…

10 Comments
  1. orang imut permalink

    muach…

  2. maha permalink

    kak kalo menentukan graf terhubung pa ga dengan c++ gmn carana??

  3. @ maha :
    bisa diperjelas sedikit gak, mengenai gmn inputny, trus outputny mw sperti ap ?
    Menurut ak, algoritma colouring graph itu merupkan lanjutan dari pngecekan graf terhubung ny itu…
    maap y sebelumny..

  4. Anonymous permalink

    kak program yang vb ada gak???

  5. waduh, ak lum dapet bwt…
    terjemahin aja k VB algoritma nya..Pasti bisa…

  6. mas cara mengiputkan ya bagai mana?

  7. ijin copas ya..

    makasih..

  8. @Hobby : lewat file mas.. ntar kalo mas uda download, ada sebuah file txt. “Latihan.txt”. Isinya
    0 0 1 1 0
    1 1 0 0 1
    0 1 0 0 1
    1 0 0 0 1
    ….
    Kurang lebih seperti di atas.
    Tiap kolom dari angka tersebut berarti Vertex. Kolom 1 bearti vertex ke 1, kolom 2 vertex ke 2. Dan baris nya itu menunjukan hubungan dari masing – masing vertex. Misalnya pada baris ke 1 yang di beri angka “1” adalah Vertex ke 3 dan 4 jadinya Vertex ke 3 dan ke 4 berhubungan. Dan warnyanya gak boleh sama.
    jadi mas bisa edit file itu, terserah mau vertex nya berapa.

    @ muslim_IT, silahkan mas…

  9. mas.. kok program aku gag bisa jlan sih , program nya udah di download tapi tetep gag bisa .terus input filenya apa?
    terima kasih

  10. Anonymous permalink

    pas kita insert vertex.. masa kita harus insert vertex sebanyak itu mas??.. sekitar 30rb vertex???

    tlg balas ke email remixone@rocketmail.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: