Data Structures Graphs & Heaps Unit Test Prep

What is a graph in data structures?

A collection of nodes (vertices) connected by edges that represent relationships between elements

What is a vertex (node)?

A fundamental unit in a graph that represents an entity or value

What is an edge?

A connection between two vertices in a graph

What is the difference between a directed and undirected graph?

Directed graphs have edges with direction (u → v), while undirected graphs have bidirectional edges (u — v)

What is a cycle in a graph?

A path that starts and ends at the same vertex without repeating edges

What is an acyclic graph?

A graph with no cycles

What is a DAG?

A Directed Acyclic Graph (a directed graph with no cycles)

What is topological ordering?

A linear ordering of vertices in a DAG such that for every directed edge u → v, u comes before v

When is topological ordering possible?

Only when the graph is a DAG (no cycles)

What is an adjacency matrix?

A 2D array used to represent a graph where rows and columns represent nodes

How do you define a graph using an adjacency matrix?

Create an n x n matrix where n is the number of nodes, and fill entries based on edges

What does each row in an adjacency matrix represent?

A source node

What does each column in an adjacency matrix represent?

A destination node

What does a 1 (or non-zero value) mean in an adjacency matrix?

An edge exists between two nodes

What does a 0 mean in an adjacency matrix?

No edge exists between two nodes

How many entries represent an edge in an undirected graph adjacency matrix?

Two entries (symmetric positions)

How many entries represent an edge in a directed graph adjacency matrix?

One entry

What is the time complexity to check if an edge exists using an adjacency matrix?

O(1)

What is a common bug when working with adjacency matrices?

Forgetting symmetry in undirected graphs or mixing up row/column meaning

What should you check when debugging graph code?

Correct edge insertion, proper traversal logic, handling visited nodes, and edge direction

What is a common mistake in graph traversal code?

Not marking nodes as visited, leading to infinite loops

What is DFS (Depth-First Search)?

A traversal that explores as far as possible down one path before backtracking

What is BFS (Breadth-First Search)?

A traversal that explores all neighbors before moving to the next level

What is a heap?

A complete binary tree that satisfies the heap property

What is the heap property?

In a max heap, parent ≥ children; in a min heap, parent ≤ children

What is a complete binary tree?

A tree where all levels are full except possibly the last, filled left to right

What is a max heap?

A heap where the largest element is always at the root

What is a min heap?

A heap where the smallest element is always at the root

How is a heap typically stored?

As an array

What is the index relationship in a heap array?

For node at index i: left child = 2i+1, right child = 2i+2, parent = (i-1)/2

How does adding (inserting) to a heap work?

Add to the end, then bubble up to restore heap property

What is bubbling up?

Swapping a node with its parent until the heap property is satisfied

How does removing from a heap work?

Remove root, replace with last element, then bubble down

What is bubbling down?

Swapping a node with its larger (max heap) or smaller (min heap) child until heap property is restored

What is the time complexity of insert in a heap?

O(log n)

What is the time complexity of remove in a heap?

O(log n)

What is a common bug in heap code?

Incorrect parent/child index calculations

What is another common heap mistake?

Not handling edge cases like empty heap or single element

What does it mean to trace a path between two nodes?

Follow edges step-by-step to determine if a path exists between nodes

What algorithm is often used to trace paths?

DFS or BFS

What should you include in a path-tracing method?

A visited set and a base case when the target is found

What is a base case in recursive graph traversal?

When the current node is the target node

Why is a visited set important?

To prevent infinite loops in cyclic graphs

What might an FRQ ask you to implement with graphs?

Methods like addEdge, hasPath, or traversal functions

What might an FRQ ask you to explain?

How a traversal works or why a bug occurs

What might an FRQ ask you to debug?

Fix incorrect edge handling, traversal logic, or missing visited checks

What is a graph class responsible for?

Managing nodes and edges

What is a node class responsible for?

Storing value and references to neighbors

How do you represent neighbors in a node class?

Using a list or set of adjacent nodes

What is a typical method for checking connectivity?

hasPath(start, end)

What is the general approach for hasPath?

Use DFS or BFS to see if end node is reachable from start