0

I'm trying to solve this work problem, but I'm having some difficuly, since I suck at recursion.

My question is: is there a way where I can pick a node in a graph and traverse the graph all the way through back to the same node where I started, but the nodes can only be visited once? And of course to save the resulting edges traversed.

The graph is unweighted, but it is coordinates in a 2D x and y coordinate system, so each coordinate has an x and y value, meaning the edges can weighted by calculating the distance between the coordinates. If that helps...

Dominique Fortin
  • 2,212
  • 15
  • 20
Johan -
  • 1
  • Loop through the children of the source node and BFS starting from each one, check if last node is source and all nodes visited – Mohd Apr 16 '18 at 10:55
  • I'm not sure I understand that. Could you expand a bit on the details? But it sounds like you're onto something! Thanks! – Johan - Apr 16 '18 at 11:02
  • is the graph directed? – Mohd Apr 16 '18 at 11:13
  • Check [this answer](https://stackoverflow.com/a/44037665/7688996) should be helpful – Mohd Apr 16 '18 at 11:37
  • Moe: no, it's not. And thanks – Johan - Apr 16 '18 at 15:47
  • It seems like CPT only works if the graph is weighted. My graph is unweighted and undirected. Is there a way to solve this? – Johan - Apr 16 '18 at 21:52
  • What you describe looks like very basic BFS search which typically include marking "visited" nodes. For more detailed help and example, post [mcve] – c0der Apr 17 '18 at 09:42

1 Answers1

0

I'm not completely sure I understand, but here is a suggestion: pick a node n0, then an edge e=(n0,n1). Then remove that edge from the graph, and use a breadth-first search to find the shortest path from n1 back to n0 if it exists.

Another suggestion, which might help you to control the length of the resulting path better: Pick a starting node n0 and find a spanning tree T emanating from n0. Remove n0, and T will (hopefully) break into components. Find an edge e=(n1,n2) from one component to another. Then that edge, plus the edges in T connecting the n1 to n0, plus the edges in T connecting n2 to n0, is a cycle with the properties you desire.

Edward Doolittle
  • 4,002
  • 2
  • 14
  • 27