Data Structures, unit: Graphs and Graph Traversal. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
28 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a graph?
- A collection of nodes (vertices) connected by edges
- What is a vertex in a graph?
- A node representing an entity
- What is an edge in a graph?
- A connection between two vertices
- What is a directed graph?
- A graph where edges have a direction, going from one vertex to another
- What is an undirected graph?
- A graph where edges have no direction, representing a two-way connection
- What is a weighted graph?
- A graph where each edge has an associated numeric cost or weight
- What is an adjacency list?
- A graph representation storing each vertex's neighbors in a list
- What is an adjacency matrix?
- A graph representation using a 2D array to indicate which vertices are connected
- What is the space complexity of an adjacency matrix for a graph with V vertices?
- O(V^2)
- What is the space complexity of an adjacency list for a graph with V vertices and E edges?
- O(V + E)
- What is breadth-first search (BFS)?
- A graph traversal algorithm that explores all neighbors at the current depth before moving deeper
- What data structure does BFS use to track which nodes to visit next?
- A queue
- What is depth-first search (DFS)?
- A graph traversal algorithm that explores as far as possible along a branch before backtracking
- What data structure does DFS typically use, explicitly or via recursion?
- A stack (or the call stack, if implemented recursively)
- What is a connected graph?
- A graph where a path exists between every pair of vertices
FlashKeepers