CSC 3102 Chapter : Csc3102MST
Document Summary
Prim"s & kruskal"s algorithms: introduction, kruskal"s algorithm, prim"s algorithm. A spanning tree is an acyclic subgraph of a graph that contains all the graph"s vertices. A minimum spanning tree is a minimum-weight acyclic subgraph of a weighted graph which contains all of the graph"s vertices. The problem of nding a minimum spanning tree in a weighted graph has many applications. The design of a physical network with feasibility con- straint between nodes. Such networks may include telecommunications net- works, transportation networks, energy pipelines, vlsi chips, etc. The min- imum spanning tree gives a lower-bound on the cost of building the network. {input: g - a weighted undirected graph with n vertices. W - a weight function on e the edge set with m edges. Output: t - a minimum spanning tree with n vertices. } T
