Graphs Flashcards
What is a Breadth-First Search?
Starts at the root and explores all nodes at the present depth, then moving on to the next depth level
What is a Depth-First Search
Starts at the root node and explores as far as possible along each branch before backtracking.
What is the advantage of an adjacency matrix?
They are time efficient, since each edge can be specifically queried very quickly using rows and columns.
What is the disadvantage of an adjacency matrix?
They are memory inefficient, as each edge between nodes are stored, even if they don’t exist.
When would you use an adjacency matrix?
For a dense graph with a large number of edges.
What is the advantage of an adjacency list?
They are memory efficient, as they only store edges that exist in the graph.
What is the disadvantage of an adjacency list?
They are time inefficient, as each item in a list must be searched sequentially until the desired edge is found.
When would you use an adjacency list?
For a sparse graph with few edges.
What are the 3 characteristics of a Tree?
- Connected
- No cycles
- Undirected
What does it mean when a graph is weighted?
It’s edges are assigned a value that can represent values such as time, distance or cost.
