Untitled

 avatar
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