Graphs

Question 1

What is a graph?

Answer 1

An abstract data type, which is a set of vertices/nodes connected to each other by edges/arcs.

Question 2

What is an abstract data type?

Answer 2

A data structure created by the programmer rather than being implemented into the programming language.

Question 3

What are the abstract data types i have to know about?

Answer 3

Queues
Stacks
Trees
Graphs

Question 4

What are edges/arcs?

Answer 4

connections to nodes essentially

Question 5

What are vertices/nodes.

Answer 5

loads of ‘locations’ essentially

Question 6

What type can the edges be of?

Answer 6

one way or two way(bidirectional)

Question 7

A graph with all arcs being one way is called?

Answer 7

directed or digraph

Question 8

What is this data type often used for?

Answer 8

To represent complex relationships

Question 9

What does it mean when an edge/arc is weighted?

Answer 9

When they have a label of a certain value to represent something e.g distance between nodes

Question 10

How is direction represented on an edge on a graph?

Answer 10

use of arrows

Question 11

What are the two possible types of implementation of a graph?

Answer 11

adjacency matrix

adjacency list

Question 12

What is an adjacency list?

Answer 12

when we represent a graph by listing each node in graph and nodes connected to it

Question 13

What is an adjacency matrix?

Answer 13

Using a e.g. 2d array to store data about a graph. Rows and columns represent nodes and their intersection is the value.

Question 14

Why can the adjacency list implementation often very efficient compared to the matrix?

Answer 14

it is more effective to implement a sparsely connected graph, as using a matrix would leave a lot of elements with 0s in them

Question 15

What is an advantage of an adjacency matrix?

Answer 15

simple to add an edge

Question 16

What is a disadvantage of a adjacency matrix?

Answer 16

a sparsely connected graph will have a lot of 0 values

Question 17

What does traversing a graph mean?

Answer 17

vising every node or vertex on a graph

Question 18

What are the two methods of traversing a graph

Answer 18

• depth first traversal

- breadth first traversal

Question 19

What is the depth- first traversal method?

Answer 19

• uses a problem solving component of backtracking

- we go as far as we can using one route and backtrack when we hit a dead end to take another route

Question 20

What is the breadth - first traversal method?

Answer 20

When we visit all neighbours of a node that was first visited, we do this for all neighbours.

Question 21

What can graphs be used to represent?

Answer 21

• computer networks with nodes representing computers and weighted edges representing the bandwidth between them
• roads between towns with weighted edges representing distance/fairs or times
• tasks in a project, where ones have to be completed before others
• web pages and links (pagerank)

Question 22

What are graph used for?

Answer 22

• gps

- friend suggestions on social media

Question 23

What is a cyclic graph?

Answer 23

a directed graph which contains a path from at least one node back to itself. It contains a cycle

Question 24

What is a acyclic graph?

Answer 24

a directed graph which contains absolutely no cycles, no node can be traversed back to itself