Graphs

Question 1

What is a graph

Answer 1

Set of nodes connected by edges

Question 2

What is a unweighted graph

Answer 2

All edges cost 0 to travel

Question 3

What is a weighted graph

Answer 3

Each edge has a cost to travel

Question 4

What is a undirected graph

Answer 4

Each edge is bi-directional

Question 5

What is a directed graph

Answer 5

Each edge is one-way

Question 6

How does an adjacency matrix represent a graph

Answer 6

Each row and column represent a node.
Item at [row, column] represents a connection.
In an unweighted graph this number is 1.
In a weighted graph the number is the weight

Question 7

How does an adjacency list represent a graph

Answer 7

A list of nodes is created, and each node contains a list of connected nodes.

Question 8

Advantage and disadvantage of using a adjacency matrix

Answer 8

Advantage: Easy to work with, adding an edge is easy

Disadvantage: Can have lots of wasted space if used with a sparse graph

Question 9

Advantage and disadvantage of using a adjacency list

Answer 9

Advantage: Easy way to store large graphs as only stores information about connections that exist.

Disadvantage: It is slow to search through