Hamiltonian path


1. Introduction

The idea of the algorithm: technical use depth-first search by marking the peak went through during the search.
Description of inputs and outputs of the problem:
Input Data for file File4.inp
- The first line contains the number n is the number of vertices in a graph (0 <n <100)
- Field 2 record peak comes.
- Line i + 2 (1 <= i <= n) contains n number of A [i, 1], A [i, 2], ..., A [i, n] each number separated by a space.

hamilton_exam

2. Source code:

#include <stdio.h>
#include <conio.h>
#include <iostream>
#define FileIn "File4.inp"
using namespace std;
int Count = 0;
int *L;
char *Mark;
int **A,n,D;
//Read data from File4.inp
void Read_File() {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d",&n,&D);
cout<<"Matrix.\n"<<D<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--;
}
//Initial data
void Initial() {
Mark = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
Mark[i] =0;
L[i] = 0;
}
Mark[D] = 1;
L[0] = D;
}
//Show path
void ShowPath(int Dinh) {
Count++;
cout<<endl<<D+1;
for (int i = 1; i<Dinh; i++)
cout<<" -> "<<L[i]+1;
}
//Search path
void Try(int Dinh){
if(Dinh == n)
ShowPath(Dinh);
else {
for(int i = 0; i<n; i++)
if( A[L[Dinh-1]][i]>0 && Mark[i] == 0){
L[Dinh] = i;
Mark[i] = 1;
Try(Dinh+1);
L[Dinh] = 0;
Mark[i] = 0;
}
}
}
int main() {
Read_File();
Initial();
cout<<"Hamiltonian path: ";
Try(1);
if(Count==0)
cout<<" khong co.";
delete *A,Mark,L;
return 0;
}

3. Result:

hamilton_result


Advertisements