Smallest sum of graph weight, where each node are connceted (like a network)

Question

Hello,

What algorithm I can use for problem like this:

Have a graph positive weighted, i want to know a smallest possible sum of weights where each node are connected (connected like a network, where each node is a eg. network device).

In this network each node can be connected with other node by some other other nodes in way. But all nodes from input graph must be in a network.

Any one can help me with this?

Answer 1

You're looking for a minimum spanning tree (MST).

Answer 2

I believe the resulting network you want is a minimum spanning tree, which has two well-known algorithms: Kruskal's and Prim's.