Hi,I am implementing graph ,all function works except the Hamiltonian part(1 function and 2 private method).Every time i compile,it shows two error message,,i don't know how to use adjacency list or is there any way to implement it using the class declaration as given above...I have main problem on my pathok function (those two returning statements..)
Your help is highly appreciated.
my code is:
#include <iostream>
#include <vector>
#include <queue>
template <typename ItemType>
class Graph //CLASS DECLARATION
{
public:
bool Hamilton(vector<int>& x);
private:
class VertexNode;
typedef VertexNode * NodePointer;
class VertexNode
{
public:
VertexNode(int n) { vert = n; next = 0; }
int vert;
NodePointer next;
};
vector<ItemType> vertex;
vector<NodePointer> adj;
vector<bool> visit;
bool RecursHamilton(int k, vector<int>& x);
bool PathOK(int k, const vector<int>& x);
};
template <typename ItemType>
bool Graph<ItemType>::RecursHamilton(int k, vector<int>& x)
{
int j;
int n = int(adj.size());
vector<bool> used;
for( x[k] = 2;x[k] < x[n];x[k]++)
if(PathOK(j,x))
{
used[x[k]] = true;
if(k == n || RecursHamilton(j,x))
return true;
used[x[k]] = false;
}
return false;
}
template <typename ItemType>
bool Graph<ItemType>::PathOK(int k, const vector<int>& x)
{
vector<bool> used;
int n = int(adj.size());
if(used[x[k]])
return false;
if(k<n)
return adj [x[k-1]] [x[k]];
else
return adj[x[n-1]][x[n]] && adj[x[1]][x[n]];
}
template <typename ItemType>
bool Graph<ItemType>::Hamilton(vector<int>& x)
{
vector<bool> used;
int j;
int n = int(adj.size()-1);
x[0] = 1;
used[0] = true;
for(int i = 2;i<=n;i++)
used[i] = false;
RecursHamilton(j, x);
return false;
}