Description
- create a forest F (a set of trees), where each vertex in the graph is a separate tree
- create a set S containing all the edges in the graph
- while S is nonempty and F is not yet spanning
- remove an edge with minimum weight from S
- if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
- otherwise discard that edge.
At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.
Read more about this topic: Kruskal's Algorithm
Famous quotes containing the word description:
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)
“Do not require a description of the countries towards which you sail. The description does not describe them to you, and to- morrow you arrive there, and know them by inhabiting them.”
—Ralph Waldo Emerson (1803–1882)
“An intentional object is given by a word or a phrase which gives a description under which.”
—Gertrude Elizabeth Margaret Anscombe (b. 1919)