Chapter 38 - Graphs

Question 1

What is a graph?

Answer 1

» An abstract data structure which are representing a complex relationship
» A set of vertices or nodes connected by adges or arcs

Question 2

What is traversal?

Answer 2

» It is essentially the ‘cost’ of movement around the graph

Question 3

What are the features of an undirected graph?

Answer 3

» Consists of nodes
» All edges are bidirectional - meaning they can go any direction

Question 4

What is an edge?

Answer 4

» Represents a path/link between 2 nodes

Question 5

What is an arc?

Answer 5

» Another name for an edge

Question 6

What is a vertex?

Answer 6

» Each data item within a graph

Question 7

What is a node?

Answer 7

» Another name for a vertex

Question 8

What is a weighted edge?

Answer 8

» Edges that have some value, attached to them
» Shows the cost of traversing

Question 9

What are the features of a directed graph?

Answer 9

» Shows direction - can be bidirectional
» Consists of nodes

Question 10

What are the 2 possible implementations of a graph?

Answer 10

» Adjacency matrix
» Adjacency list

Question 11

What does each row and column represent in a adjacency matrix?

Answer 11

» A node

Question 12

What is the order of a matrix?

Answer 12

» Row then column

Question 13

What is an adjacency matrix?

Answer 13

» A table showing which nodes in a graph are connected and if the edges are weighted
» Elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph

Question 14

What will the adjacency matrix be in an undirect graph?

Answer 14

» Symmetric

Question 15

How can an unweighted graph be represented in a matrix?

Answer 15

» May be represented with 1s instead of weights

Question 16

How can a weighted graph be represented in a matrix?

Answer 16

» Instead of 1s, there can be the value of the weight

Question 17

What are the advantages of an adjacency matrix?

Answer 17

» Very convenient to work with
» Adding edges is very simple

Question 18

What are the disadvantages of an adjacency matrix?

Answer 18

» A sparse graph with not many connections will leave most of the cells empty, therefore wasting space
» Using a static 2D array for it, it is harder to add or delete nodes

Question 19

What is an adjacency list?

Answer 19

» A collection of unordered lists used to represent a finite graph
» Each list describes the set of neighbours of a vertex in a graph

Question 20

How does an adjacency list look like?

Answer 20

» A list of all the nodes are created
» Each node points to a list where all the adjacent nodes to which is directly linked

Question 21

When should an adjacency list be implemented as a dictionary?

Answer 21

» When it is weighted, with each key in the dictionary being the node and the value, the edge weight

Question 22

What are the advantages of an adjacency list?

Answer 22

» Good way of representing a sparsely connected graph
» More memory efficient

Question 23

What are the disadvantages of an adjacency list?

Answer 23

» In the adjacency list, you need to list all the nodes that the node is connected to, in order to find the other node of the edge required.
» Not time efficient

Question 24

What is the page rank algorithm?

Answer 24

» An algorithm used by Google search to rank website in their search engine results

Question 25

What are the 2 ways to traverse a graph so that every node is visited?

Answer 25

» A depth - first traversal » A breadth - first traversal

Question 26

What is a Depth-first traversal?

Answer 26

» We go as far down one route as we can before backtracking and taking the next route » Visit the first node atatched to starting node » Visited all the nodes connected directly or indirectly to this first node » Visit the second node directly atteched to the starting node

Question 27

What is the data structure used for depth-first traversal?

Answer 27

» A stack

Question 28

What are the applications for depth-first searches?

Answer 28

» Finding a path between 2 vertices » Solving a puzzles such as navigating a maze

Question 29

Is there a unique way to visit all the nodes in a depth-first search?

Answer 29

» No as the sequence involves some choices

Question 30

What is a breadth-first search?

Answer 30

» We visit all the neighbours of a node, then all the neighbours of the first node visited, and so on before moving further away from the start node

Question 31

What is the data structure used for breadth-first searches?

Answer 31

» A queue

Question 32

What are the applications for a breadth-first search?

Answer 32

» Finding the shortest path between 2 points » Facebook used a breadth-first search to find all the friends of a given individual

Question 33

What are some applications for graphs?

Answer 33

» Computer networks » Roads between towns » Web pages and links

Question 34

How does a graph differ from a linked list?

Answer 34

» Each vertex can have more than 2 edges

Question 35

What does a 1 represent in an adjacency matrix?

Answer 35

» Represents an edge between 2 vertices

Question 36

What is abstraction?

Answer 36

» Using only the necessary detail and discarding unecessary detail

Question 37

In an undirected graph, what are the edges?

Answer 37

» Bidirectional