9.4 (Spanning Trees) Flashcards
What is a subgraph that has the same connectivity as the graph and is a tree?
spanning tree
A graph has a spanning tree only if?
it has a single connected component
What are the two classic algorithms to compute spanning trees?
edge-centric and vertex-centric
Which algorithm sorts the edges by weight and processes each edge in order?
edge-centric algorithm
Which algorithm has each vertex pick an edge connecting it to another vertex until they belong to a single connected component?
vertex-centric algorithm
What is a graph with measures associated with the edges?
weighted graphs
What is a spanning tree that has the least total weight?
minimum spanning tree (MST)
True or false; if all the weights are the same, every spanning tree is a minimum spanning tree.
true
What is the edge-centric algorithm for minimum spanning trees?
Kruskal’s algorithm
What is the vertex-centric algorithm for minimum spanning trees?
Prim’s algorithm
