Fundamentals of data structures (graphs)

Question 1

What are graphs

Answer 1

• Abstract data structures used to represent complex relationships beween items
• can be used to represent networks
• consists of nodes (or vertices) joined by edges (or arcs)
• weighted graphs are those which edges are assigned a value
• Can be represented by adjacency matrices and adjacency lists

Question 2

Adjacency matrices

Answer 2

Each node in the graph is assigned both a row and a column

for unweighted graphs:
* a 1 shows than an edge joins two nodes
* a 0 shows there is no connection

• they have a characteristic diagonal line of 0s, which show the diagonal symmetry

Question 3

Adjacency lists

Answer 3

• Represent a graph using a list
• For each node, a list of adjacent nodes is created

Question 4

Comparing adjaceny lists vs adjacency matrices

Answer 4

Memory efficiency: lists, only stores edges that exist in the graph

Time efficiency: matrices, specific edges can be queried quickly, looked up by its row and column
|

Lists are suited to sparse graphs, matrices are suited to dense graphs