Ch 10: Graphs II Flashcards

1
Q

what is a directed graph (digraph)?

A

consists of vertices connected by directed edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what is a directed edge?

A

a connection between a starting vertex and a terminating vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is a path?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what is a cycle?

A

a path that starts and ends at the same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what is the difference between cyclic and acyclic?

A

cyclic contains a cycle, acyclic does not

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what is a weighted graph?

A

associates a weight with an edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is weight (cost)?

A

represents some numerical value between vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

are weighted graphs directed or undirected?

A

can be either

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what is path length?

A

sum of edge weights in a path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

what is cycle length?

A

sum of the edge weights in a cycle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

what is negative edge weight cycle?

A

has a cycle length < 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what are the 2 shortest path algorithms?

A

Dijkstra’s and Bellman-Ford’s

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what is distance?

A

the shortest path distance from the start vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what is a predecessor point?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

O(V^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

17
Q

who is Dijkstra’s algorithm created by?

A

Edsger Dijkstra

18
Q

who is the Bellman-Ford algorithm created by?

A

Richard Bellman and Lester Forman Jr

19
Q

does Dijkstra’s handle negative weights?

20
Q

does Bellman-Ford’s handle negative weights?

21
Q

what is topological search?

A

(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

22
Q

what is the space complexity of topological search?

A

O(|V| + |E|)

23
Q

what is a minimum spanning tree?

A

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

24
Q

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

A

a weighted & connected graph

25
what does it mean for a graph o be connected?
a graph contains a path between every pair of vertices
26
what is Kruskal's minimum spanning tree algorithm?
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
27
what is the space complexity of Kruskal's?
O(|E| + |V|)
28
what is the runtime complexity of Kruskal's?
O(|E| + |V|)
29
what is the all-pairs shortest path algorithm?
an algorithm that determines the shortest path between all possible pairs of vertices in a graph
30
what is the Floyd-Warshall all-pairs shortest path algorithm?
generates a |V|*|V| matrix of values representing the shortest path lengths between all vertex pairs in the graph
31
does Floyd-Warshall support cyclic graphs and negative weights?
yes but graph cannot have a negative cycle
32
what is a negative cycle?
a cycle with edge weights that sum to a negative value
33
what is the space complexity of Floyd-Warshall?
O(|V|^2)
34
what is the runtime complexity of Floyd-Warshall?
O(|V|^3)