Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit569c6ae

Browse files
committed
Add Hamiltonian cycle.
1 parent0fc7b9d commit569c6ae

File tree

4 files changed

+274
-1
lines changed

4 files changed

+274
-1
lines changed

‎README.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,8 @@
7474
*[Topological Sorting](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/topological-sorting) - DFS method
7575
*[Articulation Points](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/articulation-points) - Tarjan's algorithm (DFS based)
7676
*[Bridges](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bridges) - DFS based algorithm
77-
*[Eulerian Path and Eulerian Circuit](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path) - Fleury's algorithm - Visit every edge once
77+
*[Eulerian Path and Eulerian Circuit](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path) - Fleury's algorithm - Visit every edge exactly once
78+
*[Hamiltonian Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
7879
*[Strongly Connected Components](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm
7980
***Uncategorized**
8081
*[Tower of Hanoi](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower)
@@ -111,6 +112,7 @@
111112
*[Maximum Subarray](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray)
112113
*[Bellman-Ford Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - finding shortest path to all graph vertices
113114
***Backtracking**
115+
*[Hamiltonian Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
114116
*[N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
115117
***Branch & Bound**
116118

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
#Hamiltonian Path
2+
3+
**Hamiltonian path** (or**traceable path**) is a path in an
4+
undirected or directed graph that visits each vertex exactly once.
5+
A**Hamiltonian cycle** (or**Hamiltonian circuit**) is a
6+
Hamiltonian path that is a cycle. Determining whether such paths
7+
and cycles exist in graphs is the**Hamiltonian path problem**.
8+
9+
![Hamiltonian cycle](https://upload.wikimedia.org/wikipedia/commons/6/6c/Hamiltonian_path_3d.svg)
10+
11+
One possible Hamiltonian cycle through every vertex of a
12+
dodecahedron is shown in red – like all platonic solids, the
13+
dodecahedron is Hamiltonian.
14+
15+
##Naive Algorithm
16+
17+
Generate all possible configurations of vertices and print a
18+
configuration that satisfies the given constraints. There
19+
will be`n!` (n factorial) configurations.
20+
21+
```
22+
while there are untried configurations
23+
{
24+
generate the next configuration
25+
if ( there are edges between two consecutive vertices of this
26+
configuration and there is an edge from the last vertex to
27+
the first ).
28+
{
29+
print this configuration;
30+
break;
31+
}
32+
}
33+
```
34+
35+
##Backtracking Algorithm
36+
37+
Create an empty path array and add vertex`0` to it. Add other
38+
vertices, starting from the vertex`1`. Before adding a vertex,
39+
check for whether it is adjacent to the previously added vertex
40+
and not already added. If we find such a vertex, we add the
41+
vertex as part of the solution. If we do not find a vertex
42+
then we return false.
43+
44+
##References
45+
46+
-[Hamiltonian path on Wikipedia](https://en.wikipedia.org/wiki/Hamiltonian_path)
47+
-[Hamiltonian path on YouTube](https://www.youtube.com/watch?v=dQr4wZCiJJ4)
48+
-[Hamiltonian cycle on GeeksForGeeks](https://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/)
Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
importGraphVertexfrom'../../../../data-structures/graph/GraphVertex';
2+
importGraphEdgefrom'../../../../data-structures/graph/GraphEdge';
3+
importGraphfrom'../../../../data-structures/graph/Graph';
4+
importhamiltonianCyclefrom'../hamiltonianCycle';
5+
6+
describe('hamiltonianCycle',()=>{
7+
it('should find hamiltonian paths in graph',()=>{
8+
constvertexA=newGraphVertex('A');
9+
constvertexB=newGraphVertex('B');
10+
constvertexC=newGraphVertex('C');
11+
constvertexD=newGraphVertex('D');
12+
constvertexE=newGraphVertex('E');
13+
14+
constedgeAB=newGraphEdge(vertexA,vertexB);
15+
constedgeAE=newGraphEdge(vertexA,vertexE);
16+
constedgeAC=newGraphEdge(vertexA,vertexC);
17+
constedgeBE=newGraphEdge(vertexB,vertexE);
18+
constedgeBC=newGraphEdge(vertexB,vertexC);
19+
constedgeBD=newGraphEdge(vertexB,vertexD);
20+
constedgeCD=newGraphEdge(vertexC,vertexD);
21+
constedgeDE=newGraphEdge(vertexD,vertexE);
22+
23+
constgraph=newGraph();
24+
graph
25+
.addEdge(edgeAB)
26+
.addEdge(edgeAE)
27+
.addEdge(edgeAC)
28+
.addEdge(edgeBE)
29+
.addEdge(edgeBC)
30+
.addEdge(edgeBD)
31+
.addEdge(edgeCD)
32+
.addEdge(edgeDE);
33+
34+
consthamiltonianCycleSet=hamiltonianCycle(graph);
35+
36+
expect(hamiltonianCycleSet.length).toBe(8);
37+
38+
expect(hamiltonianCycleSet[0][0].getKey()).toBe(vertexA.getKey());
39+
expect(hamiltonianCycleSet[0][1].getKey()).toBe(vertexB.getKey());
40+
expect(hamiltonianCycleSet[0][2].getKey()).toBe(vertexE.getKey());
41+
expect(hamiltonianCycleSet[0][3].getKey()).toBe(vertexD.getKey());
42+
expect(hamiltonianCycleSet[0][4].getKey()).toBe(vertexC.getKey());
43+
44+
expect(hamiltonianCycleSet[1][0].getKey()).toBe(vertexA.getKey());
45+
expect(hamiltonianCycleSet[1][1].getKey()).toBe(vertexB.getKey());
46+
expect(hamiltonianCycleSet[1][2].getKey()).toBe(vertexC.getKey());
47+
expect(hamiltonianCycleSet[1][3].getKey()).toBe(vertexD.getKey());
48+
expect(hamiltonianCycleSet[1][4].getKey()).toBe(vertexE.getKey());
49+
50+
expect(hamiltonianCycleSet[2][0].getKey()).toBe(vertexA.getKey());
51+
expect(hamiltonianCycleSet[2][1].getKey()).toBe(vertexE.getKey());
52+
expect(hamiltonianCycleSet[2][2].getKey()).toBe(vertexB.getKey());
53+
expect(hamiltonianCycleSet[2][3].getKey()).toBe(vertexD.getKey());
54+
expect(hamiltonianCycleSet[2][4].getKey()).toBe(vertexC.getKey());
55+
56+
expect(hamiltonianCycleSet[3][0].getKey()).toBe(vertexA.getKey());
57+
expect(hamiltonianCycleSet[3][1].getKey()).toBe(vertexE.getKey());
58+
expect(hamiltonianCycleSet[3][2].getKey()).toBe(vertexD.getKey());
59+
expect(hamiltonianCycleSet[3][3].getKey()).toBe(vertexB.getKey());
60+
expect(hamiltonianCycleSet[3][4].getKey()).toBe(vertexC.getKey());
61+
});
62+
63+
it('should return false for graph without Hamiltonian path',()=>{
64+
constvertexA=newGraphVertex('A');
65+
constvertexB=newGraphVertex('B');
66+
constvertexC=newGraphVertex('C');
67+
constvertexD=newGraphVertex('D');
68+
constvertexE=newGraphVertex('E');
69+
70+
constedgeAB=newGraphEdge(vertexA,vertexB);
71+
constedgeAE=newGraphEdge(vertexA,vertexE);
72+
constedgeBE=newGraphEdge(vertexB,vertexE);
73+
constedgeBC=newGraphEdge(vertexB,vertexC);
74+
constedgeBD=newGraphEdge(vertexB,vertexD);
75+
constedgeCD=newGraphEdge(vertexC,vertexD);
76+
77+
constgraph=newGraph();
78+
graph
79+
.addEdge(edgeAB)
80+
.addEdge(edgeAE)
81+
.addEdge(edgeBE)
82+
.addEdge(edgeBC)
83+
.addEdge(edgeBD)
84+
.addEdge(edgeCD);
85+
86+
consthamiltonianCycleSet=hamiltonianCycle(graph);
87+
88+
expect(hamiltonianCycleSet.length).toBe(0);
89+
});
90+
});
Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
importGraphVertexfrom'../../../data-structures/graph/GraphVertex';
2+
3+
/**
4+
*@param {number[][]} adjacencyMatrix
5+
*@param {object} verticesIndices
6+
*@param {GraphVertex[]} cycle
7+
*@param {GraphVertex} vertexCandidate
8+
*@return {boolean}
9+
*/
10+
functionisSafe(adjacencyMatrix,verticesIndices,cycle,vertexCandidate){
11+
constendVertex=cycle[cycle.length-1];
12+
13+
// Get end and candidate vertices indices in adjacency matrix.
14+
constcandidateVertexAdjacencyIndex=verticesIndices[vertexCandidate.getKey()];
15+
constendVertexAdjacencyIndex=verticesIndices[endVertex.getKey()];
16+
17+
// Check if last vertex in the path and candidate vertex are adjacent.
18+
if(!adjacencyMatrix[endVertexAdjacencyIndex][candidateVertexAdjacencyIndex]){
19+
returnfalse;
20+
}
21+
22+
// Check if vertexCandidate is being added to the path for the first time.
23+
constcandidateDuplicate=cycle.find(vertex=>vertex.getKey()===vertexCandidate.getKey());
24+
25+
return!candidateDuplicate;
26+
}
27+
28+
/**
29+
*@param {number[][]} adjacencyMatrix
30+
*@param {object} verticesIndices
31+
*@param {GraphVertex[]} cycle
32+
*@return {boolean}
33+
*/
34+
functionisCycle(adjacencyMatrix,verticesIndices,cycle){
35+
// Check if first and last vertices in hamiltonian path are adjacent.
36+
37+
// Get start and end vertices from the path.
38+
conststartVertex=cycle[0];
39+
constendVertex=cycle[cycle.length-1];
40+
41+
// Get start/end vertices indices in adjacency matrix.
42+
conststartVertexAdjacencyIndex=verticesIndices[startVertex.getKey()];
43+
constendVertexAdjacencyIndex=verticesIndices[endVertex.getKey()];
44+
45+
// Check if we can go from end vertex to the start one.
46+
return!!adjacencyMatrix[endVertexAdjacencyIndex][startVertexAdjacencyIndex];
47+
}
48+
49+
/**
50+
*@param {number[][]} adjacencyMatrix
51+
*@param {GraphVertex[]} vertices
52+
*@param {object} verticesIndices
53+
*@param {GraphVertex[][]} cycles
54+
*@param {GraphVertex[]} cycle
55+
*/
56+
functionhamiltonianCycleRecursive({
57+
adjacencyMatrix,
58+
vertices,
59+
verticesIndices,
60+
cycles,
61+
cycle,
62+
}){
63+
// Clone cycle in order to prevent it from modification by other DFS branches.
64+
constcurrentCycle=[...cycle].map(vertex=>newGraphVertex(vertex.value));
65+
66+
if(vertices.length===currentCycle.length){
67+
// Hamiltonian path is found.
68+
// Now we need to check if it is cycle or not.
69+
if(isCycle(adjacencyMatrix,verticesIndices,currentCycle)){
70+
// Another solution has been found. Save it.
71+
cycles.push(currentCycle);
72+
}
73+
return;
74+
}
75+
76+
for(letvertexIndex=0;vertexIndex<vertices.length;vertexIndex+=1){
77+
// Get vertex candidate that we will try to put into next path step and see if it fits.
78+
constvertexCandidate=vertices[vertexIndex];
79+
80+
// Check if it is safe to put vertex candidate to cycle.
81+
if(isSafe(adjacencyMatrix,verticesIndices,currentCycle,vertexCandidate)){
82+
// Add candidate vertex to cycle path.
83+
currentCycle.push(vertexCandidate);
84+
85+
// Try to find other vertices in cycle.
86+
hamiltonianCycleRecursive({
87+
adjacencyMatrix,
88+
vertices,
89+
verticesIndices,
90+
cycles,
91+
cycle:currentCycle,
92+
});
93+
94+
// Remove candidate vertex from cycle path in order to try another one.
95+
currentCycle.pop();
96+
}
97+
}
98+
}
99+
100+
/**
101+
*@param {Graph} graph
102+
*@return {GraphVertex[][]}
103+
*/
104+
exportdefaultfunctionhamiltonianCycle(graph){
105+
// Gather some information about the graph that we will need to during
106+
// the problem solving.
107+
constverticesIndices=graph.getVerticesIndices();
108+
constadjacencyMatrix=graph.getAdjacencyMatrix();
109+
constvertices=graph.getAllVertices();
110+
111+
// Define start vertex. We will always pick the first one
112+
// this it doesn't matter which vertex to pick in a cycle.
113+
// Every vertex is in a cycle so we can start from any of them.
114+
conststartVertex=vertices[0];
115+
116+
// Init cycles array that will hold all solutions.
117+
constcycles=[];
118+
119+
// Init cycle array that will hold current cycle path.
120+
constcycle=[startVertex];
121+
122+
// Try to find cycles recursively in Depth First Search order.
123+
hamiltonianCycleRecursive({
124+
adjacencyMatrix,
125+
vertices,
126+
verticesIndices,
127+
cycles,
128+
cycle,
129+
});
130+
131+
// Return found cycles.
132+
returncycles;
133+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp