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
what does it mean for a graph o be connected?
a graph contains a path between every pair of vertices
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
what is the space complexity of Kruskal’s?
O(|E| + |V|)
what is the runtime complexity of Kruskal’s?
O(|E| + |V|)
what is the all-pairs shortest path algorithm?
an algorithm that determines the shortest path between all possible pairs of vertices in a graph
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
does Floyd-Warshall support cyclic graphs and negative weights?
yes but graph cannot have a negative cycle
what is a negative cycle?
a cycle with edge weights that sum to a negative value
what is the space complexity of Floyd-Warshall?
O(|V|^2)
what is the runtime complexity of Floyd-Warshall?
O(|V|^3)
