Ch 10: Graphs II

Question 1

what is a directed graph (digraph)?

Answer 1

consists of vertices connected by directed edges

Question 2

what is a directed edge?

Answer 2

a connection between a starting vertex and a terminating vertex

Question 3

what is a path?

Answer 3

a sequence of directed edges leading from a source(starting) vertex to a destination(terminating) vertex

Question 4

what is a cycle?

Answer 4

a path that starts and ends at the same vertex

Question 5

what is the difference between cyclic and acyclic?

Answer 5

cyclic contains a cycle, acyclic does not

Question 6

what is a weighted graph?

Answer 6

associates a weight with an edge

Question 7

what is weight (cost)?

Answer 7

represents some numerical value between vertices

Question 8

are weighted graphs directed or undirected?

Answer 8

can be either

Question 9

what is path length?

Answer 9

sum of edge weights in a path

Question 10

what is cycle length?

Answer 10

sum of the edge weights in a cycle

Question 11

what is negative edge weight cycle?

Answer 11

has a cycle length < 0

Question 12

what are the 2 shortest path algorithms?

Answer 12

Dijkstra’s and Bellman-Ford’s

Question 13

what is distance?

Answer 13

the shortest path distance from the start vertex

Question 14

what is a predecessor point?

Answer 14

points to the previous vertex along the shortest path from the start vertex

Question 15

what is the runtime of Dijkstra’s if the unvisited vertex queue is implemented using a list?

Answer 15

O(V^2)

Question 16

what is the runtime of Dijkstra’s if the unvisited vertex queue is implemented using a heap?

Answer 16

O(VlogV)

Question 17

who is Dijkstra’s algorithm created by?

Answer 17

Edsger Dijkstra

Question 18

who is the Bellman-Ford algorithm created by?

Answer 18

Richard Bellman and Lester Forman Jr

Question 19

does Dijkstra’s handle negative weights?

Answer 19

no

Question 20

does Bellman-Ford’s handle negative weights?

Answer 20

yes

Question 21

what is topological search?

Answer 21

(of a directed, acyclic graph) produces a list of the graph’s vertices such that for every edge from a vertex x to a vertex y, x comes before y in the list

Question 22

what is the space complexity of topological search?

Answer 22

O(|V| + |E|)

Question 23

what is a minimum spanning tree?

Answer 23

a subset of the graph’s edges that connect all vertices in the graph together with the minimum sum of edge weights

Question 24

what type of graph does a minimum spanning tree work for?

Answer 24

a weighted & connected graph

Question 25

what does it mean for a graph o be connected?

Answer 25

a graph contains a path between every pair of vertices

Question 26

what is Kruskal’s minimum spanning tree algorithm?

Answer 26

an algorithm that determines the subset of the graph’s edges that connect all vertices in an undirected graph with the minimum sum of edge weights

Question 27

what is the space complexity of Kruskal’s?

Answer 27

O(|E| + |V|)

Question 28

what is the runtime complexity of Kruskal’s?

Answer 28

O(|E| + |V|)

Question 29

what is the all-pairs shortest path algorithm?

Answer 29

an algorithm that determines the shortest path between all possible pairs of vertices in a graph

Question 30

what is the Floyd-Warshall all-pairs shortest path algorithm?

Answer 30

generates a |V|*|V| matrix of values representing the shortest path lengths between all vertex pairs in the graph

Question 31

does Floyd-Warshall support cyclic graphs and negative weights?

Answer 31

yes but graph cannot have a negative cycle

Question 32

what is a negative cycle?

Answer 32

a cycle with edge weights that sum to a negative value

Question 33

what is the space complexity of Floyd-Warshall?

Answer 33

O(|V|^2)

Question 34

what is the runtime complexity of Floyd-Warshall?

Answer 34

O(|V|^3)