# First approximation to the TSP in a non-complete Graph

I'm trying to solve the Travelling Salesman Problem in a non-complete graph $(G,E)$ using genetic algorithms.

My problem is that I can't find a good first approximation by the usual greedy algorithms, as long as I can't assure an arbitrary edge $(u,v)$ to be in $E$. I tried to add to $E$ new edges (with almost infinity weight) in order to make it complete, bit then it turns to be way more inefficient.

I can't find a good solution on internet. So can anyone help me?

• Which greedy algorithm are you trying? – Raziman T V Feb 11 '17 at 9:38
• I'm looking for a kruskal-similar algorithm. If the graph was complete I would add edges starting with the ones with less cost and always that this edge does not cause a vertex to have grade two or more and does not form a cycle until the full graph is covered. Then I will connect the formed paths in a single one. I'm trying to find something similar for non-complete graphs. – Alpp Feb 11 '17 at 16:34