10 Trees and Graph Algorithms Free Online FlashCards

What is a tree?

A tree is a connected, acyclic undirected graph.

How many edges does a tree with $n$ vertices have?

A tree with $n$ vertices has exactly $n-1$ edges.

What is a leaf in a tree?

A leaf is a vertex of degree 1. Every tree with at least two vertices has at least two leaves.

What is a spanning tree?

A spanning tree contains every vertex of the graph and is itself a tree.

How does Kruskal's algorithm build an MST?

Kruskal's algorithm sorts edges by increasing weight and adds an edge when it joins two previously disconnected components.

How does Prim's algorithm build an MST?

Prim's algorithm starts with one vertex and repeatedly adds the minimum-weight edge connecting the current tree to a vertex outside it.

In a rooted tree, what is a vertex's parent?

The parent of a vertex is the next vertex on its path toward the root.

What is the height of a rooted tree?

The height of a rooted tree is the maximum depth of any vertex.

What data structure does BFS use, and how does it explore?

BFS uses a queue and visits vertices level by level.

How does DFS explore a graph?

DFS follows one branch as far as possible before backtracking; it can use recursion or an explicit stack.

What is inorder traversal for a binary tree?

Inorder traversal processes the left subtree, then the vertex, then the right subtree.

What is the adjacency-list runtime of BFS and DFS?

For adjacency lists, BFS and DFS run in $O(|V|+|E|)$ time.