Graphs

Question 1

What is a graph?

Answer 1

A data structure designed to represent the relationship between items

Question 2

What is a node/vertex of a graph?

Answer 2

A representation of an item of data, often drawn as a circle.

Question 3

What is an edge/arc of graph?

Answer 3

A line used to represent the relationship between two nodes

Question 4

Describe a weighted graph

Answer 4

Each edge has a value/cost attributed to it

Question 5

Describe a directed graph

Answer 5

A graph in which some edges can only be traversed in one direction

Question 6

Describe a disconnected graph

Answer 6

A graph which two or more nodes are not connected to the graph

Question 7

What are the uses of a graph data structure?

Answer 7

Route finding
Representing networks in human relationships
Computer networks
Project management
Game theory (mathematical modelling of strategic decisions)

Question 8

What is an adjacency list?

Answer 8

A method of representing a graph by listing, for each node just the nodes that are directly connected to it directly

Question 9

What is an adjacency matrix?

Answer 9

A method of representing a grid with values in each cell to show which nodes are connected to each other?

Question 10

What are the advantages and disadvantages of an adjacency list?

Answer 10

+ Good for sparse graphs (few edges) or situations where edges don’t need to be tested often as it takes up less space
- Poor for dense graphs as it takes too long to process each value

Question 11

What are the advantages and disadvantages of an adjacency matrix?

Answer 11

+ Good for dense graphs (many edges) or situations where edges need to be tested often as it’s easier to process each value
- Poor for sparse graphs as it wastes storage space