4.2.4 Graphs

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/9

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

10 Terms

1
New cards

What is a graph?

A complex abstract data structure used to represent complex relationships between items

<p>A complex abstract data structure used to <mark data-color="purple">represent complex relationships between items</mark> </p>
2
New cards

How can graphs be represented?

  • Adjacency matrices

  • Adjacency lists

3
New cards

What is an adjacency matrix?

Tabular representation

—> Each node is assigned a row and a column

<p><mark data-color="purple">Tabular representation</mark></p><p>—&gt; Each node is assigned a row and a column</p>
4
New cards

What is an adjacency list?

A list of adjacent nodes is created for each node in the graph

—> Only record existing connections

<p>A <mark data-color="purple">list of adjacent nodes is created for each node</mark> in the graph</p><p>—&gt; Only record <mark data-color="purple">existing </mark>connections </p>
5
New cards

What are the positives of using an adjacency matrix?

+ Convenient

+ Simple to add new edges

6
New cards

What are the negatives of using an adjacency matrix?

- Memory inefficient, as it stores all possible edges

7
New cards

Where are adjacency matrices best suited?

Dense graphs where there are a large number of edges

8
New cards

What are the positives of using an adjacency list?

+ More memory efficient, only stores existing connections

9
New cards

What are the negatives of using an adjacency list?

- Slow to query, as every item in a list must be searched linearly

10
New cards

Where are adjacency lists best suited?

(Large) Sparse graphs with little edges