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:
- 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?
- Iterate through cycles and find which vertexes to mark.
My questions are:
- 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?)
- 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.