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