Graphs

Question 1

Define Graph

Answer 1

• abstract data type that can be used to represent complex, non-linear relationships between objects
• contains nodes and edges

Question 2

Define neighbour

Answer 2

two nodes connected by an edge

Question 3

Define degree

Answer 3

number of other nodes that a node is connected to

Question 4

Define loop

Answer 4

edge that connects node to itself

Question 5

Define cycle

Answer 5

closed path

Question 6

Uses of graphs

Answer 6

• social networking
• transport networks
• the internet
• World wide web

Question 7

Define undirected graph

Answer 7

allows you to traverse in either direction between nodes

Question 8

Define directed graph

Answer 8

edges have direction, you move between nodes in specified direction

Question 9

Define weighted graph

Answer 9

values associated with the edges

Question 10

Define adjacency matrix

Answer 10

• table
• 0s if unweighted
• infinity if weighted

Question 11

Define adjacency list

Answer 11

• dictionary
• unweighted: B - D; H
• weighted: B - D,15; H,40

Question 12

Advantages of adjacency lists

Answer 12

-space efficient for graphs with few edges (sparse graphs)

Question 13

Disadvantages of adjacency lists

Answer 13

-requires linear search when determining presence of an edge

Question 14

Advantages of adjacency matrix

Answer 14

• space efficient for graphs with a lot of edges (denser graphs)
• good when frequently testing for prescence of edges