インターフェイスメソッドの実装を求める割り当ての質問がありますisHamiltonian
。再帰を使用して問題を解決しようとしました。
条件を満たすパスがある場合は、ノードからのすべてのパスを試すだけです。
- すべてのノードを1回だけ移動します
- 最後のノードは最初のノードに直接接続されています
ハミルトニアンだと思います。
これらのコードを試しましたが、機能しません
public static boolean isHamiltonian(Graph g) throws InvalidGraphException {
if (g == null || !(g instanceof GraphI) || ((GraphI) g).getDirected()) {
throw new InvalidGraphException();
}
NodeI[] nodes = (NodeI[]) g.nodes();
if (nodes.length < 3)
return false;
return isHamiltonian(nodes[0], nodes[0], new HashSet<NodeI>());
}
private static boolean isHamiltonian(NodeI start, NodeI n, HashSet<NodeI> hs) {
hs.add(n);
NodeI[] nodes = n.getReachableNeighbours();
boolean connectedWithStart = false;
for (int i = 0; i < nodes.length; i++) {
if (nodes[i].compareTo(start) == 0) {
connectedWithStart = true;
break;
}
}
if (hs.size() == n.getGraph().nodes().length && connectedWithStart) {
return true;
}
for (int i = 0; i < nodes.length; i++) {
if (!hs.contains(nodes[i]))
isHamiltonian(start, nodes[i], hs);
}
return false;
}