Section 7 Chapter 41 - Graphs

Question 1

Graph

Answer 1

A set of nodes that are connect by edges. Can be used to represent complex relationships

Question 2

Weighted Graph

Answer 2

A graph where each edge has a number associated with it. This is often the ‘cost’ to move along that edge

Question 3

Node

Answer 3

A point on a graph. Nodes are connected to each other by edges and can often represent locations or states.

Question 4

Edge

Answer 4

An edge connects to nodes. Edges often represent a movement or a change

Question 5

Undirected graph

Answer 5

Edges are all bidirectional. This means that all edges can be travelled across in both directions

Question 6

Directed graph

Answer 6

All the edges are one way

Question 7

Common uses for graphs (4)

Answer 7

• Showing road connections between cities
• FSM
• Representing a computer network
• Showing links between web pages

Question 8

Adjacency matrix

Answer 8

A table that can be represented with a two dimensional array. It represents the nodes of a graph and the connections between these nodes.

Question 9

What an undirected graph adjacency matrix will look like

Answer 9

symmetrical

Question 10

How to represent an unweighted graph with an adjacency matrix

Answer 10

0s and 1s

Question 11

Adjacency list

Answer 11

A list of all nodes. Each node in the list points to a list of its adjacent nodes and the weights. Can be represented as a list of dictionaries

Question 12

Adjacency matrix vs adjacency list

Answer 12

Adjacency matrix
+ Adding an edge is easy
+ Testing for the presence of an edge is easy
- In a graph with lots of nodes but few edges, a adjacency matrix would have a lot of empty wasted space
Adjacency list
- More space efficient