Posted By

ldominov on 01/09/13

Tagged

c++

Versions (?)

alo

/ Published in: C++

hamilton cycles

Highlighted TextExpand

#include<iostream>
#include<cstdlib>
#define N 6

using namespace std;

void ispis_rj(int put[]);

bool valja (int v, bool graf[N][N], int put[], int pos)
{
    if (graf[ put[pos-1] ][ v ] == 0) return false;
    for (int i = 0; i < pos; i++) if (put[i] == v) return false;

return true;
}

void hamo(bool graf[N][N], int put[N], int pos){
     if (pos == N){
        if ( graf[ put[pos-1] ][ put[0] ] == 1 ) ispis_rj(put);
        return;
    }
    for (int v = 1; v < N; v++) {
        if (valja(v, graf, put, pos)) {
            put[pos] = v;
            hamo (graf, put, pos+1);
            put[pos] = -1;
        }
    }
}

void ispis_rj(int put[]) {
    for (int i = 0; i < N; i++) 
		cout << put[i]+1 << "\t" ;
    cout << put[0]+1 << endl;
}

int main() {
   bool graf[N][N] = {{1, 0, 1, 1, 1, 1},
                      {0, 1, 0, 1, 1, 0},
                      {1, 0, 1, 0, 0, 1},
                      {1, 1, 0, 1, 1, 1},
                      {1, 1, 0, 1, 1, 0},
                      {1, 0, 1, 1, 0, 1},
                     };
    int *put = new int[N];
    for (int i = 0; i < N; i++) put[i] = -1;
    put[0] = 0;
	cout << "\nRjesenje (ako ga ima):" << endl;
    hamo (graf, put, 1);

system("pause");
    return 0;
}

Report this snippet Tweet

Comments

Subscribe to comments

Posted By: ldominov on January 9, 2013: abu

Comment:

You need to login to post a comment.

Posted By

Tagged

Versions (?)

alo

Related snippets

Comments

Choose a language for easy browsing: