Ch 10: Graphs II Flashcards
what is a directed graph (digraph)?
consists of vertices connected by directed edges
what is a directed edge?
a connection between a starting vertex and a terminating vertex
what is a path?
a sequence of directed edges leading from a source(starting) vertex to a destination(terminating) vertex
what is a cycle?
a path that starts and ends at the same vertex
what is the difference between cyclic and acyclic?
cyclic contains a cycle, acyclic does not
what is a weighted graph?
associates a weight with an edge
what is weight (cost)?
represents some numerical value between vertices
are weighted graphs directed or undirected?
can be either
what is path length?
sum of edge weights in a path
what is cycle length?
sum of the edge weights in a cycle
what is negative edge weight cycle?
has a cycle length < 0
what are the 2 shortest path algorithms?
Dijkstra’s and Bellman-Ford’s
what is distance?
the shortest path distance from the start vertex
what is a predecessor point?
points to the previous vertex along the shortest path from the start vertex
what is the runtime of Dijkstra’s if the unvisited vertex queue is implemented using a list?
O(V^2)
what is the runtime of Dijkstra’s if the unvisited vertex queue is implemented using a heap?
O(VlogV)
who is Dijkstra’s algorithm created by?
Edsger Dijkstra
who is the Bellman-Ford algorithm created by?
Richard Bellman and Lester Forman Jr
does Dijkstra’s handle negative weights?
no
does Bellman-Ford’s handle negative weights?
yes
what is topological search?
(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
what is the space complexity of topological search?
O(|V| + |E|)
what is a minimum spanning tree?
a subset of the graph’s edges that connect all vertices in the graph together with the minimum sum of edge weights
what type of graph does a minimum spanning tree work for?
a weighted & connected graph