So I have an un-directed un-weighted graph. It contains cycles. I would like to find the path which visits the most nodes with no repeat visits to any node. Since this is a graph traversal, you can start and end at any node you like.
Background Research: I have looked at Travelling Salesman Problem (TSP); this problem is different and does NOT allow you to finish where you started from and there are no weights. I have looked at several other algorithms, but have found none suitable for this problem.
Graph Size: There are 100 nodes in the graph; with 10 disconnected nodes.
Best Answer
This problem is still difficult, it is known as Hamiltonian path, and NP-complete. It doesn't really make a difference if the path is closed (a circuit) or not. Just ask the HAM-PATH problem for every pair of endpoints of all edges and you could solve HAM-CIRCUIT.