A connector problem is defined as: given a graph G and a positive cost c_e for each e in E, find a minimum-cost spanning connected subgraph of G.
When the edge costs are all positive, this problem-type can be solved using Minimum Spanning Tree (MST) algorithms. I'm not really sure what would change if the edge costs weren't strictly positive. My understanding of the two MST algorithms I know (Prim's and Kruskal's) is that both of these algorithms are greedy, in that they choose the most optimal (cheapest) edge connecting any two nodes to eventually span the graph. If the costs are negative, I assumed that the greediness of these algorithms would always favor the least costly (or most negative) edge cost if there existed an edge that was negative. Could someone explain to me why negative edge costs would inhibit these algorithms from solving the connector problem as an MST problem?