무방향 그래프에서 Hamiltonian 경로는 각 정점을 정확히 한 번 방문하는 경로이고 Hamiltonian 순환 또는 회로는 마지막 정점에서 간선이 있는 Hamiltonian 경로입니다. 첫 번째 정점으로.
이 문제에서는 그래프에 해밀턴 주기가 포함되어 있는지 여부를 확인하려고 합니다. 그리고 Hamiltonian 주기가 있는 경우 주기도 인쇄하십시오.
입력 및 출력
Input: The adjacency matrix of a graph G(V, E). Output: The algorithm finds the Hamiltonian path of the given graph. For this case it is (0, 1, 2, 4, 3, 0). This graph has some other Hamiltonian paths. If one graph has no Hamiltonian path, the algorithm should return false.
알고리즘
isValid(v, k)
입력 - 정점 v 및 위치 k.
출력 - k 위치에 v를 배치하는 것이 유효한지 여부를 확인합니다.
Begin if there is no edge between node(k-1) to v, then return false if v is already taken, then return false return true; //otherwise it is valid End
cycleFound(노드 k)
입력 - 그래프의 노드입니다.
출력 - Hamiltonian Cycle이 있으면 참, 그렇지 않으면 거짓입니다.
Begin if all nodes are included, then if there is an edge between nodes k and 0, then return true else return false; for all vertex v except starting point, do if isValid(v, k), then //when v is a valid edge add v into the path if cycleFound(k+1) is true, then return true otherwise remove v from the path done return false End
예
#include<iostream> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {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}, }; /* int graph[NODE][NODE] = { {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}, }; */ int path[NODE]; void displayCycle() { cout<<"Cycle: "; for (int i = 0; i < NODE; i++) cout << path[i] << " "; cout << path[0] << endl; //print the first vertex again } bool isValid(int v, int k) { if (graph [path[k-1]][v] == 0) //if there is no edge return false; for (int i = 0; i < k; i++) //if vertex is already taken, skip that if (path[i] == v) return false; return true; } bool cycleFound(int k) { if (k == NODE) { //when all vertices are in the path if (graph[path[k-1]][ path[0] ] == 1 ) return true; else return false; } for (int v = 1; v < NODE; v++) { //for all vertices except starting point if (isValid(v,k)) { //if possible to add v in the path path[k] = v; if (cycleFound (k+1) == true) return true; path[k] = -1; //when k vertex will not in the solution } } return false; } bool hamiltonianCycle() { for (int i = 0; i < NODE; i++) path[i] = -1; path[0] = 0; //first vertex as 0 if ( cycleFound(1) == false ) { cout << "Solution does not exist"<<endl; return false; } displayCycle(); return true; } int main() { hamiltonianCycle(); }
출력
Cycle: 0 1 2 4 3 0