I am given a connected, weighted undirected graph.

I must obtain minimum possible weight sum of "marked" vertexes in the graph.
Vertexes must be marked so that each simple cycle contains at least one "marked" vertex.

I will approach this problem by:

  1. using DFS on each node to obtain list of all possible cycles. I must guarantee that each simple cycle contains a marked vertex so first I must find all simple cycles, right?
  2. Iterate through cycles and find which vertexes to mark.

My questions are:

  1. Is there a better(more optimal) way to approach this problem (do some calculation while doing DFS? some way to avoid using DFS on each node?)
  2. I will use Java to complete this assignment, are there any useful libraries for this type of task? currently I plan on using arrays and lists.

Originally asked on https://stackoverflow.com/questions/48367470/how-to-approach-homework-about-graph-traversal , but a user suggested to post here.

  • $\begingroup$ [Also posted on ](stackoverflow.com/questions/48367470). Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration. $\endgroup$ – Discrete lizard Jan 21 '18 at 14:51
  • $\begingroup$ Question 1 is on-topic here, but 2 is off-topic here, although on-topic on Stackoverflow (but likely a duplicate). Perhaps you should keep the algorithm question here, remove the part about Java, and take a quick look at SO if there is a question about DFS or graph libraries in Java. $\endgroup$ – Discrete lizard Jan 21 '18 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.