Chapter 38: Graphs and Chapter 63: Graph Traversal Algorithms

Question 1

What is a graph

Answer 1

A graph is a set of vertices/nodes connected by edges/arcs.

Question 2

Undirected graph

Answer 2

All edges are bidirectional

Question 3

Directed graph

Answer 3

The edges are unidirectional

Question 4

Advantages compared to Linked List/Binary Tree

Answer 4

Each vertex can have more than 2 edges therefore able to point to any vertex in the data structure

Question 5

Weighted graph

Answer 5

Where each edge is given an value to show the cost of going from one vertex to another.

Question 6

Adjacency list (define)

Answer 6

Adjacency lists: storing graphs as objects or using a dictionary.

Question 7

Adjacency list (python syntax with/without weights)

Answer 7

Python syntax (no weights): graph = {“A”:[“B”,”D”,”E”,”F”]…}
Python syntac (with weights): graph = {“A”:[“B”:57,”D”:56,”E”:45,”F”:25]…}

Question 8

Adjacency Matrix

Answer 8

Adjacency matrix: a 2d array which stores the value of the weight of the edge between 2 vertices.
Symmetrical with an undirected graph (with 0 top left to bottom right).
Pros: very convenient (adding an edge is simple).
Cons: A sparse graph with many nodes but not many edges will lead to lots of 0s/empty cells therefore inefficient

Question 9

Uses of graphs in computer science

Answer 9

1. Mapping road networks for navigation systems
2. Storing social network data
3. Resource allocation in operating systems
4. Representing molecular structures and geometry.

Question 10

Types of graph traversals

Answer 10

There are 2 ways of traversing a graph:
- A depth-first traversal
- A breadth-first traversal

Question 11

Depth-first traversal

Answer 11

In this traversal, we go as far down one route as we can before backtracking and taking the next route.
- Uses an edge-based technique
- Makes use of the stack data structure

Question 12

Depth-first traversal algorithm

Answer 12

1. Set the root node as the current node
2. Add the current node to the list of visited nodes (if it isn’t already in the list)
3. Go through all the connected nodes to the current node
   - (i) If the current node isn’t in visited nodes, push it onto the stack. Usually traverse on the left side of the graph
4. Pop the node from the stack and set it to current node
5. Start again through step 2.

Once we get to the end of one route, there will be no further nodes to push onto the stack therefore it will pop the next node which is the start of the next route.