competitive-programming/Backtracking/Hamiltonian_Cycle.cpp at master · kothariji/competitive-programming · GitHub

History

152 lines (132 loc) · 3.95 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

/* C++ program for solution of Hamiltonian

Cycle problem using backtracking */

#include <bits/stdc++.h>

using namespace std;

// Number of vertices in the graph

#define V 5

void printSolution(int path[]);

/* A utility function to check if

the vertex v can be added at index 'pos'

in the Hamiltonian Cycle constructed

so far (stored in 'path[]') */

bool isSafe(int v, bool graph[V][V],

int path[], int pos)

{

/* Check if this vertex is an adjacent

vertex of the previously added vertex. */

if (graph [path[pos - 1]][ v ] == 0)

return false;

/* Check if the vertex has already been included.

This step can be optimized by creating

an array of size V */

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

if (path[i] == v)

return false;

return true;

}

/* A recursive utility function

to solve hamiltonian cycle problem */

bool hamCycleUtil(bool graph[V][V],

int path[], int pos)

{

/* base case: If all vertices are

included in Hamiltonian Cycle */

if (pos == V)

{

// And if there is an edge from the

// last included vertex to the first vertex

if (graph[path[pos - 1]][path[0]] == 1)

return true;

else

return false;

}

// Try different vertices as a next candidate

// in Hamiltonian Cycle. We don't try for 0 as

// we included 0 as starting point in hamCycle()

for (int v = 1; v < V; v++)

{

/* Check if this vertex can be added

// to Hamiltonian Cycle */

if (isSafe(v, graph, path, pos))

{

path[pos] = v;

/* recur to construct rest of the path */

if (hamCycleUtil (graph, path, pos + 1) == true)

return true;

/* If adding vertex v doesn't lead to a solution,

then remove it */

path[pos] = -1;

}

/* If no vertex can be added to

Hamiltonian Cycle constructed so far,

then return false */

return false;

}

/* This function solves the Hamiltonian Cycle problem

using Backtracking. It mainly uses hamCycleUtil() to

solve the problem. It returns false if there is no

Hamiltonian Cycle possible, otherwise return true

and prints the path. Please note that there may be

more than one solutions, this function prints one

of the feasible solutions. */

bool hamCycle(bool graph[V][V])

{

int *path = new int[V];

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

path[i] = -1;

/* Let us put vertex 0 as the first vertex in the path.

If there is a Hamiltonian Cycle, then the path can be

started from any point of the cycle as the graph is undirected */

path[0] = 0;

if (hamCycleUtil(graph, path, 1) == false )

{

cout << "\nSolution does not exist";

return false;

}

printSolution(path);

return true;

}

/* A utility function to print solution */

void printSolution(int path[])

{

cout << "Solution Exists:"

" Following is one Hamiltonian Cycle \n";

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

cout << path[i] << " ";

// Let us print the first vertex again

// to show the complete cycle

cout << path[0] << " ";

cout << endl;

}

// Driver Code

int main()

{

/* Let us create the following graph

(0)--(1)--(2)

| / \ |

(3)-------(4) */

bool graph1[V][V] = {{0, 1, 0, 1, 0},

{1, 0, 1, 1, 1},

{0, 1, 0, 0, 1},

{1, 1, 0, 0, 1},

{0, 1, 1, 1, 0}};

// Print the solution

hamCycle(graph1);

/* Let us create the following graph

(0)--(1)--(2)

| / \ |

(3) (4) */

bool graph2[V][V] = {{0, 1, 0, 1, 0},

{1, 0, 1, 1, 1},

{0, 1, 0, 0, 1},

{1, 1, 0, 0, 0},

{0, 1, 1, 0, 0}};

// Print the solution

hamCycle(graph2);

return 0;

}

competitive-programming/Backtracking/Hamiltonian_Cycle.cpp at master · kothariji/competitive-programming · GitHub

Expand file tree

Breadcrumbs

Hamiltonian_Cycle.cpp

Latest commit

History

Breadcrumbs

Hamiltonian_Cycle.cpp

File metadata and controls