9.1 (Graphs)

Question 1

What is a collection of dots and lines?

Answer 1

graph

Question 2

What are the dots in a graph called?

Answer 2

vertices (nodes)

Question 3

What are the lines in a graph called?

Answer 3

edges

Question 4

Each edge connects a pair of ________.

Answer 4

vertices

Question 5

There is at most ____ edge between any two vertices

Answer 5

1

Question 6

What is an edge that only goes in one direction?

Answer 6

directed edge

Question 7

What is an edge that can go in both directions?

Answer 7

undirected edge

Question 8

What is a path that begins and ends at the same node?

Answer 8

cycle

Question 9

What is a graph that doesn’t contain any cycles?

Answer 9

acyclic graph

Question 10

What is a graph that’s connected if every node is reachable from every other node?

Answer 10

connected graph

Question 11

What is a graph that’s complete if every node has an edge to every other edge? (grows as O(n^2)

Answer 11

complete graph

Question 12

A node is reachable only if?

Answer 12

a path exists between the two nodes

Question 13

Vertices that are all connected to a vertex with an edge are called?

Answer 13

neighbors

Question 14

A graph is considered _______ if it has numbers associated with edges

Answer 14

weighted

Question 15

What are weighted graphs useful for?

Answer 15

mapping between locations, traffic, distance, time, etc.

Question 16

Mathematically, a graph G is a pair (___, ___)

Answer 16

(V, E)

Question 17

V is the set of _______.

Answer 17

vertices

Question 18

E is the set of _______.

Answer 18

edges

Question 19

A graph is _____ if it has relatively few edges

Answer 19

sparse

Question 20

A graph is ______ if it has a lot of edges

Answer 20

dense

Question 21

Which graph algorithm explores a graph level-by-level using a queue?

Answer 21

Breadth-First-Search

Question 22

Which graph algorithm explores as deeply as possible using a stack (or recursion)?

Answer 22

Depth-First-Search

Question 23

Which graph algorithm is useful for finding the shortest path between points in weighted graphs?

Answer 23

Dijkstra

Question 24

What is Breadth-First-Search useful for?

Answer 24

finding the shortest path in unweighted graphs

Question 25

What is Depth-First-Search useful for?

Answer 25

cycle detection and topological sorting

Question 26

What is Dijkstra useful for?

Answer 26

applications like Google Maps

Question 27

Which graph algorithm finds a minimum spanning tree and makes the least possible weight between any two nodes?

Answer 27

kruskal