Program C++ Graph Coloring : Pewarnaan Graf

Program C++ Graph Coloring : Pewarnaan Graf - Pewarnaan graf adalah kasus khusus dari pelabelan graf , yaitu menggunakan warna untuk menandai pada batasan tertentu. Dalam bentuk yang paling sederhana, itu adalah cara untuk mewarnai simpul dari graf sehingga tidak ada dua simpul yang berdekatan mempunyai warna yang sama.

Tentunya tidak mudah untuk menggambarkan graf pada program console. Sehingga perlu teknik khusus. Kita misalkan 1 adalah tanda graf yang terhubung dan 0 adalah tanda graf tidak terhubung. Sebagai contoh, kita mempunyai 7 vertex dan terhubung seperti gambar dibawah ini :

Program C++ Graph Coloring : Pewarnaan Graf - Kemudian penulisan hubungan graf adalah sebagai berikut :

0 1 1 0 1 1 0

1 0 0 1 0 1 1

1 0 0 1 1 1 0

0 1 1 0 0 1 1

1 0 1 0 0 0 1

1 1 1 1 0 0 0

0 1 0 1 1 0 0

Implementasi program c++ pewarnaan graf atau Graph Coloring sebagai berikut :

#include <cstdlib>

#include <iostream>

using namespace std;

// inisialisai

const int MAX = 100;

int n;

int a[MAX][MAX];

int color[MAX];

int degree[MAX];

int NN[MAX];

int NNCount;

int unprocessed;

void Coloring();

void GetInput();

void Init();

int MaxDegreeVertex();

void scannedInit(int scanned[MAX]);

void UpdateNN(int ColorNumber);

int FindSuitableY(int ColorNumber, int& VerticesInCommon);

int MaxDegreeInNN();

void PrintOutput();

void Coloring()

{

    int x,y;

    int ColorNumber = 0;

    int VerticesInCommon = 0;

    while (unprocessed>0)

    {

        x = MaxDegreeVertex(); 

        ColorNumber ++;

        color[x] = ColorNumber;

        unprocessed --;

        UpdateNN(ColorNumber);

        while (NNCount>0)

        {

            y = FindSuitableY(ColorNumber, VerticesInCommon);

            if (VerticesInCommon == 0)

                y = MaxDegreeInNN();

            color[y] = ColorNumber;

            unprocessed --;

            UpdateNN(ColorNumber);

        }

    }

}

void GetInput()

{

    cout<<"Masukkan banyak data : ";

    cin >> n;

    cout<<"Masukkan hubungan graph : \n";

    for (int i=0; i < n; i++){

        for (int j=0; j < n; j++){

            cout<<"Simpul "<<i+1<<" - "<<j+1<<" : ";

            cin >> a[i][j]; 

            }

        }

}

void Init()

{

    for (int i=0; i < n; i++)

    {

        color[i] = 0;

        degree[i] = 0;

        for (int j = 0; j < n; j++)

            if (a[i][j] == 1)

                degree[i] ++;

    }

    NNCount = 0;

    unprocessed = n;

}

int MaxDegreeVertex()

{

    int max = -1;

    int max_i;

    for (int i =0; i < n; i++)

        if (color[i] == 0)

            if (degree[i]>max)

            {

                max = degree[i];

                max_i = i;

            }

    return max_i;

}

void scannedInit(int scanned[MAX])

{

    for (int i=0; i < n; i++)

        scanned[i] = 0;

}

void UpdateNN(int ColorNumber)

{

    NNCount = 0;

    for (int i=0; i < n; i++)

        if (color[i] == 0)

        {

            NN[NNCount] = i;

            NNCount ++; 

        }

    

    for (int i=0; i < n; i++)

        if (color[i] == ColorNumber)

            for (int j=0; j < NNCount; j++)

                while (a[i][NN[j]] == 1)

                {

                    NN[j] = NN[NNCount - 1];

                    NNCount --;

                }

}

int FindSuitableY(int ColorNumber, int& VerticesInCommon)

{

    int temp,tmp_y,y;

    int scanned[MAX];

    VerticesInCommon = 0;

    for (int i=0; i < NNCount; i++)

    {

        tmp_y = NN[i];

        temp = 0;

        scannedInit(scanned);

        for (int x=0; x < n; x++)

            if (color[x] == ColorNumber)

                for (int k=0; k < n; k++)

                    if (color[k] == 0 && scanned[k] == 0)

                        if (a[x][k] == 1 && a[tmp_y][k] == 1)

                        {

                            temp ++;

                            scanned[k] = 1;

                        }

        if (temp > VerticesInCommon)

        {

            VerticesInCommon = temp;

            y = tmp_y;

        }

    }

    return y;

}

int MaxDegreeInNN()

{

    int tmp_y;

    int temp, max = 0;

    for (int i=0; i < NNCount; i++)

    {

        temp = 0;

        for (int j=0; j < n; j++)

            if (color[j] == 0 && a[NN[i]][j] == 1)

                temp ++;

        if (temp>max)

        {

            max = temp;

            tmp_y = NN[i];

        }

    }

    if (max == 0)

        return NN[0];

    else

        return tmp_y;

}

void PrintOutput()

{

     cout<<"\n\n";

    for (int i=0; i < n; i++)

        cout << "Vertex " << i+1 

             << " warna " << color[i] << endl;

}

int main(int argc, char *argv[])

{

    

    system("color f2");

    system("title Program Graph Coloring - 1 Juni 2012 - dyasprogramming.blogspot.com");

    

    awal:

    GetInput();

    Init();

    Coloring();

    PrintOutput();

    

    cout<<"\nIngin mengulang ? (y/n) : ";

    char p;

    cin>>p;

    if(p=='y') {

               system("cls");

               goto awal;

               }

    else return EXIT_SUCCESS;

}

Program C++ N Queen Secara Rekursif

Program C++ N Queen Secara Rekursif - Program n queen atau n ratu adalah masalah menempatkan n catur ratu pada papan catur n × n sehingga tidak ada dua ratu atau lebih menyerang satu sama lain atau saling memakan. Dengan demikian, solusi mensyaratkan bahwa tidak ada dua ratu atau lebih berbagi baris yang sama, kolom, atau diagonal.

Implementasi program n queen menggunakan bahasa c++ bisa menggunakan dua jenis perulangan. Yang pertama secara iteratif dan secara rekursif. Berikut ini adalah program c++ penempatan n ratu secara rekursif : (lihat juga program c++ nqueen secara iteratif)

#include <cstdlib>

#include <iostream>

#include <math.h>

using namespace std;

void cetakSolusi(int x[],int n){

    int i,j;

    char c[100][100];

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            c[i][j]='X';

        }

    }

    for(i=1;i<=n;i++)

    {

        c[i][x[i]] ='Q';

    }

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            cout<<"\t"<<c[i][j];

        }

    cout<<endl;

    }

    cout<<endl;

}

bool tempat (int x[], int k ){

int i;

bool stop, kedudukan;

kedudukan = true;

i = 1;

stop = false;

while((i<k) && (!stop)){

if((x[i]==x[k]) || (abs(x[i]-x[k])==abs(i-k))){

kedudukan = false;

stop = true;

}else{

i++;

}

}

return kedudukan;

}

void nRatuR(int n, int k, int x[]){

bool stop;

stop = false;

while(!stop){

x[k] +=1;

        while((x[k] <= n) && ( !tempat(x,k))){

            x[k] +=1;

        }

        

        if(x[k] <= n){

            if(k == n){

                cetakSolusi(x,n);

            }else{

                nRatuR(n,k+1,x);

            }

        }

        else{

            stop = true;

            x[k]=0;

        }

}

}

int main(int argc, char *argv[])

{

    system("color f2");

    system("title Program N_Ratu - 1 Juni 2012 - dyasprogramming.blogspot.com");

    

    awal:

    int n;

    int x [100];

    cout<<"Masukkan banyak ratu : ";

    cin>>n;

    cout<<"\n\nKemungkinan yang didapatkan :\n\n";

nRatuR(n,1,x);

    cout<<"\nIngin mengulang ? (y/n) : ";

    char p;

    cin>>p;

    if(p=='y') {

               system("cls");

               goto awal;

               }

    else return EXIT_SUCCESS;

}

Program C++ N Queen Secara Iteratif

Program C++ N Queen Secara Iteratif - Program n queen atau n ratu adalah masalah menempatkan n catur ratu pada papan catur n × n sehingga tidak ada dua ratu atau lebih menyerang satu sama lain atau saling memakan. Dengan demikian, solusi mensyaratkan bahwa tidak ada dua ratu atau lebih berbagi baris yang sama, kolom, atau diagonal.

Implementasi program n queen menggunakan bahasa c++ bisa menggunakan dua jenis perulangan. Yang pertama secara iteratif dan secara rekursif. Berikut ini adalah program c++ penempatan n ratu secara iteratif : (lihat juga program c++ nqueen secara rekursif)

#include <cstdlib>

#include <iostream>

#include <math.h>

using namespace std;

void cetakSolusi(int x[],int n){

    int i,j;

    char c[100][100];

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            c[i][j]='X';

        }

    }

    for(i=1;i<=n;i++)

    {

        c[i][x[i]] ='Q';

    }

    for(i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

        {

            cout<<"\t"<<c[i][j];

        }

    cout<<endl;

    }

    cout<<endl;

}

bool tempat (int x[], int k ){

int i;

bool stop, kedudukan;

kedudukan = true;

i = 1;

stop = false;

while((i<k) && (!stop)){

if((x[i]==x[k]) || (abs(x[i]-x[k])==abs(i-k))){

kedudukan = false;

stop = true;

}else{

i++;

}

}

return kedudukan;

}

void nRatuI(int n){

int x[100],k;

k=1; 

    x[k] = 0;

     

    while(k > 0){

x[k] +=1;

        while((x[k] <= n) && ( !tempat(x,k))){        

            x[k] +=1;

        }

        

        if(x[k] <= n){

            if(k == n){

                cetakSolusi(x,n);

            }else{

                k++;

                x[k]=0;

            }

        }

        else{

            k--;

        }

         

    }

}

int main(int argc, char *argv[])

{

    system("color f2");

    system("title Program N_Ratu - 1 Juni 2012 - dyasprogramming.blogspot.com");

    

    awal:

    int n;

    cout<<"Masukkan banyak ratu : ";

    cin>>n;

    cout<<"\n\nKemungkinan yang didapatkan :\n\n";

nRatuI(n);

    cout<<"\nIngin mengulang ? (y/n) : ";

    char p;

    cin>>p;

    if(p=='y') {

               system("cls");

               goto awal;

               }

    else return EXIT_SUCCESS;

}