Basics of Graphs
A structure consisting of vertices and edges
What is a graph?
A tree that connects all vertices without forming cycles
What is a spanning tree?
A spanning tree contains no ______
What are cycles?
Algorithm used to find Minimum Spanning Tree by growing a tree
What is Prim’s Algorithm?
Algorithm that builds MST by selecting smallest edges first
What is Kruskal’s Algorithm?
A graph with no direction on edges
What is an undirected graph?
A spanning tree of a graph with n vertices contains this many edges
What is n − 1 edges?
All spanning trees of a graph have the same number of this
What are edges?
Prim’s algorithm starts from this
What is any arbitrary vertex?
First step in Kruskal’s algorithm
What is sorting edges by weight?
A graph where every pair of vertices is connected
What is a complete graph?
A graph must have this property to contain a spanning tree
What is being connected?
A spanning tree is minimally ______
What is connected?
At each step, Prim’s algorithm selects this type of edge
What is the minimum weight edge?
Edges are added only if they do not form this
What is a cycle?
A graph with no cycles
What is an acyclic graph?
Removing one edge from a spanning tree results in this
What is a disconnected graph?
A spanning tree is maximally ______
What is acyclic?
Prim’s algorithm always adds edges that connect to this
What is a new vertex?
Technique used to detect cycles efficiently
What is Union-Find (Disjoint Set)?
A graph that has at least one path between every pair of vertices
What is a connected graph?
Adding one edge to a spanning tree creates this
What is a cycle?
Maximum number of spanning trees in a complete graph with n vertices
What is n^(n−2)?
Prim’s algorithm stops when this condition is met
What is all vertices are included in the tree?
Kruskal’s algorithm stops when this condition is satisfied
What is n − 1 edges are selected?