Untitled
unknown
plain_text
a year ago
1.5 kB
5
Indexable
#include <iostream> #include <vector> using namespace std; namespace HamiltonianCycle { void printSolution(int path[], int V) { cout << "Hamiltonian Cycle: "; for (int i = 0; i < V; i++) { cout << path[i] << " "; } cout << path[0] << endl; } void printAllHamiltonianCycles(const vector<vector<int>>& graph, int path[], int pos, int V) { if (pos == V) { printSolution(path, V); return; } for (int v = 1; v < V; v++) { if (graph[path[pos - 1]][v] == 1 && path[v] == -1) { path[pos] = v; printAllHamiltonianCycles(graph, path, pos + 1, V); path[pos] = -1; } } } bool hamCycle(const vector<vector<int>>& graph, int V) { int* path = new int[V]; for (int i = 0; i < V; i++) path[i] = -1; path[0] = 0; printAllHamiltonianCycles(graph, path, 1, V); delete[] path; return true; } } // namespace HamiltonianCycle int main() { int V; cout << "Enter the number of vertices (V): "; cin >> V; vector<vector<int>> graph(V, vector<int>(V, 0)); cout << "Enter the adjacency matrix for the graph (0 or 1):\n"; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { cin >> graph[i][j]; } } HamiltonianCycle::hamCycle(graph, V); return 0; }
Editor is loading...
Leave a Comment