Pro.ID10150 TitleMinimum Spanning Tree Title链接http://10.20.2.8/oj/exercise/problem?problem_id=10150 AC0 Submit0 Ratio- 时间&空间限制描述Sample Problem: Agri-Net [Russ Cox, Winter 1999 USACO Open]Farmer John is bringing internet connectivity to all farms in the area. He has ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to minimize the length of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a path exists from any farm to any other farm. Some farms might have 1, 2, 3, or more connections to them. The AbstractionGiven: an undirected, connected graph with weighted edges A spanning tree of a graph is any sub-graph which is a connected tree (i.e., there exists a path between any nodes of the original graph which lies entirely in the sub-graph). A minimal spanning tree is a spanning tree which has minimal `cost' (where cost is the sum of the weights of the edges in the tree). Prim's algorithm to construct a Minimal Spanning TreeGiven: lists of nodes, edges, and edge costs The algorithm (greedily) builds the minimal spanning tree by iteratively adding nodes into a working tree.
For analysis of why this works, consult Chapter 24 of [Cormen, Leiserson, Rivest]. Here is pseudocode for the algorithm: Running time of this formulation is O(N2). You can obtain O(N log N) for sparse graphs, but it normally isn't worth the extra programming time. Execution ExampleConsider the following graph with weighted edges:
All nodes not shown have infinite distance, intree=False, and source=nil. The smallest distance for a node not in the tree is 20, so the listed edge to node 3 is added to the tree:
Note that node 3 is now `in the tree'. Node 2's distance changed to 9 while the source changed to 3. The smallest distance is 7, so the edge from node 3 to node 7 (coincidental name!) is connected:
Node 2's distance is 9, the smallest of any node not in the tree. Adding the edge from node 3 to node 2 results in a graph that looks like this:
Add the edge from node 2 to node 5:
Adding the edge from node 5 to node 4 is the next step:
![]()
Finally, add the edge from node 6 to node 8:
And the minimal spanning tree is easily seen here. Dangerous CurveUnderstand that changing any element in a tree requires complete recalculation - incremental recalculation of a spanning tree when changing isolated nodes, for example, is not generally possible. Problem CuesIf the problem mentions wanting an optimal, connected sub-graph, a minimum cost way to connect a system together, or a path between any two parts of the system, it is very likely to be a minimum spanning tree problem. ExtensionsIf you subject the tree to any other constraints (no two nodes may be very far away or the average distance must be low), this algorithm breaks down and altering the program to handle such constraints is very difficult. There is obviously no problem with multiple edges between two nodes (you ignore all but the smallest weight). Prim's algorithm does not extend to directed graphs (where you want strong connectedness), either. Sample ProblemsPackage RoutingGiven: a set of locations of cities and the cost of connecting each pair of cities for a shipping company. Find the cheapest set of pairs of cities such that a package can be routed from any city to any other city. Highway BuildingLower Slobbovia has made the plunge and has decided to connect all their cities with roads. Of course, being cheap, they want to spend as little money as possible. The cost of a highway is linearly proportional to its length. Given the x,y coordinates of the cities in L.S., find the cheapest way to interconnect the cities. Bovile Phones (abridged) [USACO Training Camp 1998, Contest 2]Given: a collection of stationary cows and haystacks in the field along with a cost function for connecting two (arbitrary) locations. Using only the haystacks and cows, calculate which haystacks one should include in a network to minimize the total cost. Analysis: For each possible set of haystacks (i.e., about 2 n sets), calculate the cost of the minimal spanning tree of the haystacks in that set along with all the cows. Find the combination of haystacks that minimizes the cost. 输入This is NOT a problem , but a course. Read it , but not Submit 输出Description Sample Problem: Agri-Net [Russ Cox, Winter 1999 USACO Open]Farmer John is bringing internet connectivity to all farms in the area. He has ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to minimize the length of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a path exists from any farm to any other farm. Some farms might have 1, 2, 3, or more connections to them. The AbstractionGiven: an undirected, connected graph with weighted edges A spanning tree of a graph is any sub-graph which is a connected tree (i.e., there exists a path between any nodes of the original graph which lies entirely in the sub-graph). A minimal spanning tree is a spanning tree which has minimal `cost' (where cost is the sum of the weights of the edges in the tree). Prim's algorithm to construct a Minimal Spanning TreeGiven: lists of nodes, edges, and edge costs The algorithm (greedily) builds the minimal spanning tree by iteratively adding nodes into a working tree.
For analysis of why this works, consult Chapter 24 of [Cormen, Leiserson, Rivest]. Here is pseudocode for the algorithm: Running time of this formulation is O(N2). You can obtain O(N log N) for sparse graphs, but it normally isn't worth the extra programming time. Execution ExampleConsider the following graph with weighted edges:
All nodes not shown have infinite distance, intree=False, and source=nil. The smallest distance for a node not in the tree is 20, so the listed edge to node 3 is added to the tree:
Note that node 3 is now `in the tree'. Node 2's distance changed to 9 while the source changed to 3. The smallest distance is 7, so the edge from node 3 to node 7 (coincidental name!) is connected:
Node 2's distance is 9, the smallest of any node not in the tree. Adding the edge from node 3 to node 2 results in a graph that looks like this:
Add the edge from node 2 to node 5:
Adding the edge from node 5 to node 4 is the next step:
![]()
Finally, add the edge from node 6 to node 8:
And the minimal spanning tree is easily seen here. Dangerous CurveUnderstand that changing any element in a tree requires complete recalculation - incremental recalculation of a spanning tree when changing isolated nodes, for example, is not generally possible. Problem CuesIf the problem mentions wanting an optimal, connected sub-graph, a minimum cost way to connect a system together, or a path between any two parts of the system, it is very likely to be a minimum spanning tree problem. ExtensionsIf you subject the tree to any other constraints (no two nodes may be very far away or the average distance must be low), this algorithm breaks down and altering the program to handle such constraints is very difficult. There is obviously no problem with multiple edges between two nodes (you ignore all but the smallest weight). Prim's algorithm does not extend to directed graphs (where you want strong connectedness), either. Sample ProblemsPackage RoutingGiven: a set of locations of cities and the cost of connecting each pair of cities for a shipping company. Find the cheapest set of pairs of cities such that a package can be routed from any city to any other city. Highway BuildingLower Slobbovia has made the plunge and has decided to connect all their cities with roads. Of course, being cheap, they want to spend as little money as possible. The cost of a highway is linearly proportional to its length. Given the x,y coordinates of the cities in L.S., find the cheapest way to interconnect the cities. Bovile Phones (abridged) [USACO Training Camp 1998, Contest 2]Given: a collection of stationary cows and haystacks in the field along with a cost function for connecting two (arbitrary) locations. Using only the haystacks and cows, calculate which haystacks one should include in a network to minimize the total cost. Analysis: For each possible set of haystacks (i.e., about 2 n sets), calculate the cost of the minimal spanning tree of the haystacks in that set along with all the cows. Find the combination of haystacks that minimizes the cost. Input This is NOT a problem , but a course. Read it , but not Submit Output This is NOT a problem , but a course. Read it , but not Submit Sample Input This is NOT a problem , but a course. Read it , but not Submit Sample Output This is NOT a problem , but a course. Read it , but not Submit Source 样例输入This is NOT a problem , but a course. Read it , but not Submit 样例输出This is NOT a problem , but a course. Read it , but not Submit 作者 |