4.2.4 Graphs
Studied by 0 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/9
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
10 Terms
What is a graph?
A complex abstract data structure used to represent complex relationships between items
How can graphs be represented?
Adjacency matrices
Adjacency lists
What is an adjacency matrix?
Tabular representation
—> Each node is assigned a row and a column
What is an adjacency list?
A list of adjacent nodes is created for each node in the graph
—> Only record existing connections
What are the positives of using an adjacency matrix?
+ Convenient
+ Simple to add new edges
What are the negatives of using an adjacency matrix?
- Memory inefficient, as it stores all possible edges
Where are adjacency matrices best suited?
Dense graphs where there are a large number of edges
What are the positives of using an adjacency list?
+ More memory efficient, only stores existing connections
What are the negatives of using an adjacency list?
- Slow to query, as every item in a list must be searched linearly
Where are adjacency lists best suited?
(Large) Sparse graphs with little edges
Note 
Flashcards (33)