What does a Matrix representation of a graph look like, and mean?
Ex: 0’s represent Vertices, and two adjacent 0’s are connected by an Edge
What is a cycle in the context of a Graph?
A set of Edges that can be traversed to loop from a Vertex to itself.
(e.g. V₁ -> E₁ -> V₂ -> E₂ -> V₃ -> E₃ -> V₁)
What is the difference between a Directed Graph and an Undirected Graph?
The edges only go in one direction. (e.g. Linked List, Tree)
The edges are bidirectional. Often depicted using an Adjacency List (or rarely with an Adjacency Matrix).
When using a Matrix, what’s the best variable names to use for the rows and columns?
Some form of “row” and “column” (e.g. “r” & “c”, “row” & “col”, etc.)
Avoid using x,y or something similarly ambiguous.
What does the code for a Graph Node look like?
# GraphNode used for adjacency list
class GraphNode:
def __init__(self, val):
self.val = val
self.neighbors = []
aka an Adjacency List
What are the two main component types in a Graph?
What is the most common use for DFS when used with a Graph?
Finding any valid path, or finding the total number of valid paths between two vertices.
What is the most common use for BFS when used with a Graph?
Finding the shortest path between two vertices.
Last changeda month ago
