graphs and MSTs Flashcards
(24 cards)
What is a path in a graph?
A sequence of nodes which are connected by consecutive edges.
What defines a connected graph?
A graph is connected if there is a path between ANY two nodes.
What is a cycle in a graph?
A path that starts and ends at the same node, has at least 3 edges, and no other node appears more than once.
What is an acyclic graph?
A graph that has no cycles.
What is a tree in graph theory?
A graph with no cycles (acyclic).
What is a spanning tree?
A set of edges which connects all nodes of a graph and is acyclic.
Does every connected graph have a spanning tree?
Yes.
What are weighted edges in a graph?
Edges that have a cost/weight associated with them.
What is a minimum spanning tree (MST)?
A spanning tree whose cost (sum of edge costs) is no greater than other spanning trees.
Name two algorithms to find the MST of graphs.
- Prim’s algorithm
- Kruskal’s algorithm
What is a safe edge in Prim’s algorithm?
The least cost edge out of a tree that has grown so far.
What is the initial set of nodes in Prim’s algorithm?
R = {A, B, C, D, E, F} with S = {} and T = {}.
What is the time complexity of Prim’s algorithm using a priority queue?
O(E log E), where E is the number of edges.
What does Kruskal’s algorithm do?
Builds up a set of edges that don’t need to be connected.
What is a safe edge in Kruskal’s algorithm?
A minimal cost edge remaining that can be added without creating a cycle.
How do you track partitions in Kruskal’s algorithm?
By mapping elements to representatives of what set they are in.
Fill in the blank: A tree is a graph with no _______.
cycles.
True or False: Kruskal’s algorithm can yield more than one outcome depending on the starting edge.
True.
What is the purpose of using a priority queue in graph algorithms?
To find and remove the minimal remaining edge each time through the loop.
What happens if a chosen edge in Kruskal’s algorithm forms a cycle?
It is discarded.
What is the initial partition of nodes in Kruskal’s algorithm?
{A} {F} {B} {C} {D} {E}.
What does the variable T represent in Kruskal’s algorithm?
The set of edges which are a subset of a minimal spanning tree of G.
What is required to check if an edge forms a cycle in Kruskal’s algorithm?
Check if the two nodes of the edge are already connected.
What data structure is used to track connections in Kruskal’s algorithm?
A hashmap mapping elements to their representatives.
