Graphs - Chapter 9

Question 1

A blank is a data structure for representing connections among items, and consists of vertices connected by edges

Answer 1

graph

Question 2

A blank (or node) represents an item in a graph.

Answer 2

vertex

Question 3

An blank represents a connection between two vertices in a graph.

Answer 3

edge

Question 4

For a given graph, the number of vertices is commonly represented as blank, and the number of edges as blank

Answer 4

V
E

Question 5

Two vertices are blank if connected by an edge.

Answer 5

adjacent

Question 6

A blank is a sequence of edges leading from a source (starting) vertex to a destination (ending) vertex.

Answer 6

path

Question 7

The blank is the number of edges in the path.

Answer 7

path length

Question 8

The blank between two vertices is the number of edges on the shortest path between those vertices

Answer 8

distance

Question 9

Blank are often used to represent a geographic map, which can contain information about places and travel routes. Ex: Vertices in a graph can represent airports, with edges representing available flights. Edge weights in such graphs often represent the length of a travel route, either in total distance or expected time taken to navigate the route. Ex: A map service with access to real-time traffic information can assign travel times to road segments.

Answer 9

Graphs

Question 10

A graph can be used to represent relationships between products. Blank in the graph corresponding to a customer’s purchased products have adjacent vertices representing products that can be recommended to the customer.

Answer 10

Vertices

Question 11

A graph may use a vertex to represent a person. An blank in such a graph represents a relationship between 2 people. In a graph representing a social network, an edge commonly represents friendship. In a graph representing a professional network, an edge commonly represents business conducted between 2 people.

Answer 11

edge

Question 12

Various approaches exist for representing a graph data structure. A common approach is an blank.

Answer 12

adjacency list

Question 13

two vertices are adjacent if connected by an edge. In an blank graph representation, each vertex has a list of adjacent vertices, each list item representing an edge.

Answer 13

adjacency list

Question 14

A key advantage of an adjacency list graph representation is a size of blank, because each vertex appears once, and each edge appears twice. V refers to the number of vertices, E the number of edges.

Answer 14

O(V + E)

Question 15

A key disadvantage of an adjacency list graph is that determining whether two vertices are adjacent is blank, because one vertex’s adjacency list must be traversed looking for the other vertex, and that list could have V items.

Answer 15

O(V)

Question 16

in most applications, a vertex is only adjacent to a small fraction of the other vertices, yielding a blank. A balnk has far fewer edges than the maximum possible.

Answer 16

sparse graph

Question 17

In an blank graph representation, each vertex is assigned to a matrix row and column, and a matrix element is 1 if the corresponding two vertices have an edge or is 0 otherwise.

Answer 17

adjacency matrix

Question 18

Assuming the common implementation as a two-dimensional array whose elements are accessible in blank, then an adjacency matrix’s key benefit is O(1) determination of whether two vertices are adjacent: The corresponding element is just checked for 0 or 1.

Answer 18

O(1)

Question 19

A key drawback is blank size. Ex: A graph with 1000 vertices would require a 1000 x 1000 matrix, meaning 1,000,000 elements. An adjacency matrix’s large size is inefficient for a sparse graph, in which most elements would be 0’s.

Answer 19

O(V^2)

Question 20

An adjacency matrix only represents blank among vertices; if each vertex has data, like a person’s name and address, then a separate list of vertices is needed.

Answer 20

edges

Question 21

An algorithm commonly must visit every vertex in a graph in some order, known as a blank.

Answer 21

graph traversal

Question 22

A blank is a traversal that visits a starting vertex, then all vertices of distance 1 from that vertex, then of distance 2, and so on, without revisiting a vertex.

Answer 22

breadth-first search (BFS)

Question 23

An algorithm for blank enqueues the starting vertex in a queue. While the queue is not empty, the algorithm dequeues a vertex from the queue, visits the dequeued vertex, enqueues that vertex’s adjacent vertices (if not already discovered), and repeats.

Answer 23

breadth-first search

Question 24

When the BFS algorithm first encounters a vertex, that vertex is said to have been blank.

Answer 24

discovered

Question 25

In the BFS algorithm, the vertices in the queue are called the blank, being vertices thus far discovered but not yet visited. Because each vertex is visited at most once, an already-discovered vertex is not enqueued again.

Answer 25

frontier

Question 26

A blank is a traversal that visits a starting vertex, then visits every vertex along each path starting from that vertex to the path’s end before backtracking.

Answer 26

depth-first search (DFS)

Question 27

An algorithm for blank pushes the starting vertex to a stack. While the stack is not empty, the algorithm pops the vertex from the top of the stack. If the vertex has not already been visited, the algorithm visits the vertex and pushes the adjacent vertices to the stack.

Answer 27

depth-first search

Question 28

A blank can be implemented using the program stack instead of an explicit stack. The blank algorithm is first called with the starting vertex. If the vertex has not already been visited, the recursive algorithm visits the vertex and performs a recursive DFS call for each adjacent vertex.

Answer 28

recursive DFS

Question 29

A blank consists of vertices connected by directed edges.

Answer 29

directed graph, or digraph,

Question 30

A blank is a connection between a starting vertex and a terminating vertex.

Answer 30

directed edge

Question 31

In a directed graph, a vertex Y is blank to a vertex X, if there is an edge from X to Y.

Answer 31

adjacent

Question 32

Many graphs are blank, like those representing links between web pages, maps for navigation, or college course prerequisites.

Answer 32

directed

Question 33

In a directed graph: A blank is a sequence of directed edges leading from a source (starting) vertex to a destination (ending) vertex.

Answer 33

path

Question 34

In a directed graph: A blank is a path that starts and ends at the same vertex. A directed graph is cyclic if the graph contains a cycle, and acyclic if the graph does not contain a cycle.

Answer 34

cycle

Question 35

A directed graph is blank if the graph contains a cycle, and blank if the graph does not contain a cycle.

Answer 35

cyclic
acyclic

Question 36

A blank associates a weight with each edge

Answer 36

weighted graph

Question 37

A graph edge’s blank, or blank, represents some numerical value between vertex items, such as flight cost between airports, connection speed between computers, or travel time between cities. A weighted graph may be directed or undirected.

Answer 37

weight, or cost,

Question 38

In a weighted graph, the path blank is the sum of the edge weights in the path.

Answer 38

length

Question 39

The blank is the sum of the edge weights in a cycle.

Answer 39

cycle length

Question 40

A blank has a cycle length less than 0

Answer 40

negative edge weight cycle

Question 41

A blank does not exist in a graph with a negative edge weight cycle, because each loop around the negative edge weight cycle further decreases the cycle length, so no minimum exists.

Answer 41

shortest path

Question 42

The Graph class holds a vertex adjacency list using a blank that maps a Vertex object to a list of adjacent Vertex objects. The Vertex class contains a label, but can be augmented by graph algorithms to contain additional data if required.

Answer 42

dictionary

Question 43

A Graph object is initialized with an empty adjacency list. Vertex objects are created and added to the Graph using the blank.

Answer 43

add_vertex() method

Question 44

Edges are represented as vertex pairs, using a blank.

Answer 44

2-item tuple

Question 45

Edges also have blank. By default, an edge is assigned with weight 1.0. Edge weights are stored in the dictionary edge_weights where the vertex pair is the key and the edge weight is the value. Ex: The edge (vertex_a, vertex_b) is assigned with weight 3.7 by self.edge_weights[(vertex_a, vertex_b)] = 3.7.

Answer 45

numeric weights

Question 46

blank traverses a graph by starting at a specific vertex and visiting the vertex’s adjacent vertices before visiting the next closest vertices. No vertex is re-visited.

Answer 46

Breadth-first search

Question 47

The breadth-first search function has three parameters:

Answer 47

graph is the graph to search.
start_vertex is the starting vertex of the breadth-first search.
distances is an optional dictionary to store the distance of each visited vertex from the start vertex.

Question 48

The breadth-first search function defines three container variables:

Answer 48

discovered_set is a set of all discovered vertices.
frontier_queue is a Queue variable (Queue class defined in a previous section) that stores vertices that have been discovered, but not yet visited.
visited_list is an ordered list of visited vertices.

Question 49

Initially, the start vertex is added to both blank and blank. start_vertex is dequeued from the queue and added to the visited list. Then, undiscovered vertices adjacent to the current dequeued vertex are added to discovered_set and frontier_queue. The distances from the adjacent vertices are set to the current dequeued vertex’s distance + 1.

Answer 49

frontier_queue and discovered_set.

Question 50

The process of dequeuing a vertex from frontier_queue and adding the vertex’s adjacent vertices to discovered_set continues until frontier_queue is empty. In the end, blank contains the order of the breadth-first search’s traversal.

Answer 50

visited_list

Question 51

Blank search traverses a graph by first visiting a specific starting vertex, and then visiting every vertex along each path originating from the starting vertex. Each path is traversed to the path’s end before backtracking.

Answer 51

Depth-first

Question 52

To perform depth-first search, the Graph and Vertex classes are used as well as a depth-first search function. depth_first_search() takes three arguments (the current graph, the starting vertex, and a function to mark visited vertices) and defines two container variables:

Answer 52

vertex_stack is a list used as the stack of yet-to-be-visited vertices.
visited_set is a set used to keep track of which vertices have been visited.

Question 53

Initially, visited_set is empty and the starting vertex is pushed onto blank. So long as vertex_stack is not empty, the loop pops a vertex from vertex_stack and assigns current_vertex with the popped vertex. If current_vertex is not in visited_set, then current_vertex is visited, added to visited_set, and each adjacent vertex is pushed onto vertex_stack.

Answer 53

vertex_stack

Question 54

depth_first_search()’s blank parameter is a function that takes a single vertex as an argument. The function is called once for each vertex traversed during the depth-first search

Answer 54

visit_function

Question 55

Blank computes the shortest path from a given starting vertex to all other vertices in the graph.

Answer 55

Dijkstra’s algorithm

Question 56

To perform Dijjkstra’s algorithm, the Graph and Vertex classes are used. The Vertex class is extended to include two additional data members:

Answer 56

distance
pred_vertex - A reference to the vertex that occurs immediately before the vertex, on a path from some start vertex to the vertex.

Question 57

Blank - The total sum of the edge weights on a path from some start vertex to the vertex.

Answer 57

distance

Question 58

Blank - A reference to the vertex that occurs immediately before the vertex, on a path from some start vertex to the vertex.

Answer 58

pred_vertex

Question 59

Put all vertices in an unvisited queue.
unvisited_queue = []
for current_vertex in g.adjacency_list:
unvisited_queue.append(current_vertex)

# start_vertex has a distance of 0 from itself
start_vertex.distance = 0

# One vertex is removed with each iteration; repeat until the list is
# empty.
while len(unvisited_queue) > 0:
    
    # Visit vertex with minimum distance from start_vertex
    smallest_index = 0
    for i in range(1, len(unvisited_queue)):
        if unvisited_queue[i].distance < unvisited_queue[smallest_index].distance:
            smallest_index = i
    current_vertex = unvisited_queue.pop(smallest_index)

    # Check potential path lengths from the current vertex to all neighbors.
    for adj_vertex in g.adjacency_list[current_vertex]:
        edge_weight = g.edge_weights[(current_vertex, adj_vertex)]
        alternative_path_distance = current_vertex.distance + edge_weight
              
        # If shorter path from start_vertex to adj_vertex is found,
        # update adj_vertex's distance and predecessor
        if alternative_path_distance < adj_vertex.distance:
            adj_vertex.distance = alternative_path_distance
            adj_vertex.pred_vertex = current_vertex

Answer 59

Dijkstra’s shortest path algorithm.

Question 60

After calling the dijkstra_shortest_path() function, the shortest path from the starting vertex to any other given vertex can be built by following the pred_vertex blank from the destination vertex to the starting vertex.

Answer 60

backwards

Question 61

Blank, created by Edsger Dijkstra, determines the shortest path from a start vertex to each vertex in a graph.

Answer 61

Dijkstra’s shortest path algorithm

Question 62

For each vertex, Dijkstra’s algorithm determines the vertex’s blank and blank

Answer 62

distance and predecessor pointer

Question 63

A vertex’s blank is the shortest path distance from the start vertex.

Answer 63

distance

Question 64

A vertex’s blank points to the previous vertex along the shortest path from the start vertex.

Answer 64

predecessor pointer

Question 65

Dijkstra’s algorithm initializes all vertices’ distances to blank initializes all vertices’ predecessors to null, and enqueues all vertices into a queue of unvisited vertices.

Answer 65

infinity (∞),

Question 66

For each adjacent vertex, the algorithm computes the distance of the path from the start vertex to the current vertex and continuing on to the blank. If that path’s distance is shorter than the adjacent vertex’s current distance, a shorter path has been found. The adjacent vertex’s current distance is updated to the distance of the newly found shorter path’s distance, and vertex’s predecessor pointer is pointed to the current vertex.

Answer 66

adjacent vertex

Question 67

After running Dijkstra’s algorithm, the shortest path from the start vertex to a destination vertex can be determined using the vertices’ blank

Answer 67

predecessor pointers.

Question 68

If the destination vertex’s predecessor pointer is blank, the shortest path is traversed in reverse by following the predecessor pointers until the start vertex is reached.

Answer 68

not 0

Question 69

If the destination vertex’s predecessor pointer is null, then a path from the start vertex to the destination vertex blank.

Answer 69

does not exist

Question 70

If the unvisited vertex queue is implemented using a list, the runtime for Dijkstra’s shortest path algorithm is blank

Answer 70

O(V^2)

Question 71

Implementing the unvisited vertex queue using a standard binary heap reduces the runtime to BLANK, and using a Fibonacci heap data structure (not discussed in this material) reduces the runtime to blank

Answer 71

O((E + V) log V)
O(E + V log V).

Question 72

Blank can be used for unweighted graphs (using a uniform edge weight of 1) and weighted graphs with non-negative edges weights

Answer 72

Dijkstra’s shortest path algorithm

Question 73

For a directed graph with negative edge weights, Dijkstra’s algorithm may not find the shortest path for some vertices, so the algorithm should not be used if a blank exists.

Answer 73

negative edge weight

Question 74

The blank, created by Richard Bellman and Lester Ford, Jr., determines the shortest path from a start vertex to each vertex in a graph.

Answer 74

Bellman-Ford shortest path algorithm

Question 75

For each vertex, the Bellman-Ford algorithm determines the vertex’s distance and predecessor pointer. A vertex’s blank is the shortest path distance from the start vertex.

Answer 75

distance

Question 76

A vertex’s blank points to the previous vertex along the shortest path from the start vertex.

Answer 76

predecessor pointer

Question 77

The blank initializes all vertices’ current distances to infinity (∞) and predecessors to null, and assigns the start vertex with a distance of 0. The algorithm performs V-1 main iterations, visiting all vertices in the graph during each iteration. Each time a vertex is visited, the algorithm follows all edges to adjacent vertices. For each adjacent vertex, the algorithm computes the distance of the path from the start vertex to the current vertex and continuing on to the adjacent vertex. If that path’s distance is shorter than the adjacent vertex’s current distance, a shorter path has been found. The adjacent vertex’s current distance is updated to the newly found shorter path’s distance, and the vertex’s predecessor pointer is pointed to the current vertex.

Answer 77

Bellman-Ford algorithm

Question 78

The Bellman-Ford algorithm does not require a blank for visiting vertices during each main iteration. So after each iteration, a vertex’s current distance and predecessor may not yet be the shortest path from the start vertex. The shortest path may propagate to only one vertex each iteration, requiring V-1 iterations to propagate from the start vertex to all other vertices.

Answer 78

specific order

Question 79

The runtime for the Bellman-Ford shortest path algorithm is blank. The outer loop (the main iterations) executes V-1 times. In each outer loop execution, the algorithm visits each vertex and follows the subset of edges to adjacent vertices, following a total of E edges across all loop executions.

Answer 79

O(VE)

Question 80

The Bellman-Ford algorithm supports graphs with negative edge weights. However, if a blank exists, a shortest path does not exist. After visiting all vertices V-1 times, the algorithm checks for negative edge weight cycles. If a negative edge weight cycle does not exist, the algorithm returns true (shortest path exists), otherwise returns false.

Answer 80

negative edge weight cycle

Question 81

The Bellman-Ford algorithm computes the shortest path from a given starting vertex to all other vertices in the graph. The algorithm works by first finding the minimum distances for all vertices that are reachable from the start vertex in one step, then in two steps, then in three steps, etc. until minimum distances for all reachable vertices have been calculated. Note that if the graph has |V| vertices, then all minimum distances must be found after at most blank of the main loop.

Answer 81

|V|-1 iterations

Question 82

In the main loop, each edge is examined to see if a blank to the start vertex than was previously known is found. After |V|-1 iterations are complete, a final iteration is performed to see if any distance decreases further; if a distance decreases again, then a negative edge weight cycle must exist in the graph and the algorithm fails.

Answer 82

shorter distance

Question 83

Each Vertex object is assigned two extra data members to help with the Bellman-Ford algorithm:

Answer 83

distance
.
pred_vertex

Question 84

blank- The minimum distance found so far from the start vertex. The data member is assigned with an initial value of float(‘inf’), which is the Python representation of infinty
.

Answer 84

distance

Question 85

blank - The previous vertex in the shortest path from the start vertex. The data member is assigned with an initial value of None, indicating that at the start of the algorithm, no known path exists from the start vertex.

Answer 85

pred_vertex

Question 86

def bellman_ford(graph, start_vertex):
# Initialize all vertex distances to infinity and
# and predecessor vertices to None.
for current_vertex in graph.adjacency_list:
current_vertex.distance = float(‘inf’) # Infinity
current_vertex.pred_vertex = None

# start_vertex has a distance of 0 from itself
start_vertex.distance = 0                

# Main loop is executed |V|-1 times to guarantee minimum distances.
for i in range(len(graph.adjacency_list)-1):
    # The main loop.
    for current_vertex in graph.adjacency_list:
        for adj_vertex in graph.adjacency_list[current_vertex]:
            edge_weight = graph.edge_weights[(current_vertex, adj_vertex)]
            alternative_path_distance = current_vertex.distance + edge_weight
                  
            # If shorter path from start_vertex to adj_vertex is found,
            # update adj_vertex's distance and predecessor
            if alternative_path_distance < adj_vertex.distance:
               adj_vertex.distance = alternative_path_distance
               adj_vertex.pred_vertex = current_vertex

# Check for a negative edge weight cycle
for current_vertex in graph.adjacency_list:
    for adj_vertex in graph.adjacency_list[current_vertex]:
         edge_weight = graph.edge_weights[(current_vertex, adj_vertex)]
         alternative_path_distance = current_vertex.distance + edge_weight

         # If shorter path from start_vertex to adj_vertex is still found,
         # a negative edge weight cycle exists
         if alternative_path_distance < adj_vertex.distance:
            return False

return True

Answer 86

The bellman_ford() function.

Question 87

A blank 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.

Answer 87

topological sort

Question 88

Graphs can be used to indicate a sequence of steps, where an edge from X to Y indicates that X must be done before Y. A blank of such a graph provides one possible ordering for performing the steps. Ex: Given a graph representing course prerequisites, a topological sort of the graph provides an ordering in which the courses can be taken.

Answer 88

topological sort

Question 89

The topological sort algorithm uses three lists:

Answer 89

a results list that will contain a topological sort of vertices, a no-incoming-edges list of vertices with no incoming edges, and a remaining-edges list.

Question 90

The blank starts as an empty list of vertices

Answer 90

result list

Question 91

The blank starts as a list of all vertices in the graph with no incoming edges.

Answer 91

no-incoming-edges vertex list

Question 92

The blank starts as a list of all edges in the graph.

Answer 92

remaining-edges list

Question 93

The algorithm executes while the no-incoming-edges vertex list is not empty. For each iteration, a vertex is removed from the no-incoming-edges list and added to the result list. Next, a temporary list is built by removing all edges in the remaining-edges list that are outgoing from the removed vertex. For each edge currentE in the temporary list, the number of edges in the remaining-edges list that are incoming to currentE’s terminating vertex are counted. If the incoming edge count is 0, then currentE’s terminating vertex is added to the no-incoming-edges vertex list.

Answer 93

Topological sort algorithm

Question 94

The two vertex lists used in the topological sort algorithm will at most contain all the vertices in the graph. The remaining-edge list will at most contain all edges in the graph. Therefore, for a graph with a set of vertices V and a set of edges E, the space complexity of topological sorting is blank
. If a graph implementation allows for retrieval of a vertex’s incoming and outgoing edges in constant time, then the time complexity of topological sorting is also blank

Answer 94

O(|V| + |E|)

Question 95

The blank finds an ordered list of vertices from a directed graph where no vertex has an outgoing edge to a preceding vertex in the list.

Answer 95

topological sort algorithm

Question 96

Blank is useful in many real-world situations such as manufacturing (where some components must be built before other components) or course scheduling (where some courses must be completed as prerequisites to other courses). When the graph is drawn with the vertices lined up left to right in the order of a topological sort, then all edges will point in the direction from left to right.

Answer 96

Topological sorting

Question 97

The topological sorting algorithm iterates through lists of edges. In Python, the Graph class represents edges using a blank in the form: (from_vertex, to_vertex), and a for loop can be used to iterate through a list or set of edges. Ex. Edges are stored in a data member dictionary called edge_weights, so all of the edges in a graph can be iterated through using a loop like:

for (from_vertex, to_vertex) in g.edge_weights.keys():

Answer 97

2-tuple

Question 98

The above code defines two variables that can be used inside the loop body: BLANK AND blank

Answer 98

from_vertex (the start of the edge) and to_vertex (the end of the edge).

Question 99

A set object called edges_remaining is initialized before the main loop with all edges from the graph; a set is used so edges can be removed in blank
time.

Answer 99

O(1)

Question 100

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

Answer 100

minimum spanning tree

Question 101

The graph must be blank and blank

Answer 101

weighted and connected

Question 102

A blank graph contains a path between every pair of vertices.

Answer 102

connected

Question 103

Blank determines the subset of a graph’s edges that connect all the graph’s vertices with the minimum possible sum of edge weights.

Answer 103

Kruskal’s minimum spanning tree algorithm

Question 104

Kruskal’s minimum spanning tree algorithm uses three collections:

Answer 104

edgeQueue
result
vertexSets:

Question 105

Blank: A priority queue of edges, initially containing all graph edges. Edge weights are priorities.

Answer 105

edgeQueue

Question 106

Blank: A collection of edges comprising the minimum spanning tree, initially empty.

Answer 106

result

Question 107

Blank: A collection of vertex sets. Each set represents vertices connected by edges in result. Initially, vertexSets contains one set for each vertex

Answer 107

vertexSets

Question 108

The Kruskal’s minimum spanning tree algorithm executes while blank has at least one edge. In each iteration, the edge with the lowest weight is removed from the edge queue. If the removed edge connects two different vertex sets, then the edge is added to the resulting minimum spanning tree, and the two vertex sets are merged.

Answer 108

edgeQueue

Question 109

Kruskal’s minimum spanning tree algorithm’s use of the edge list, collection of vertex sets, and resulting edge list results in a space complexity of blank. If the edge list is sorted at the beginning, then the minimum edge can be removed in constant time within the loop. Combined with a mechanism to map a vertex to the containing vertex set in constant time, the minimum spanning tree algorithm has a runtime complexity of blank.

Answer 109

O(|E| + |V|)
O(|E|log|E|)

Question 110

The minimum spanning tree algorithm requires a blank for edges, where each edge’s weight is the edge’s priority.

Answer 110

priority queue

Question 111

The blank class implements a simple edge object that stores to and from vertices, as well as weight.

Answer 111

EdgeWeight

Question 112

Blank are implemented such that edges are compared to each other using edge weights.

Answer 112

Comparison operators

Question 113

The blank data member is a dictionary that maps a vertex to the set containing the vertex. The get_set() method takes a vertex as an argument and returns the set containing the vertex.

Answer 113

vertex_map

Question 114

The blank takes two different sets as arguments and merges the two together internally. Ex: Suppose 5 vertices, A, B, C, D, and E, are represented in 3 sets in a collection: {A, E}, {B, C}, and {D}. If merge() is called on sets {A, E} and {D}, then the resulting collection contains two sets: {A, E, D} and {B, C}.

Answer 114

merge() method

Question 115

Blank algorithm is implemented in the minimum_spanning_tree() function. A graph is passed as the only argument, and a list of edges representing the graph’s minimum spanning tree is returned.

First, edge_list is initialized as a priority queue containing all edges from the graph. Python’s heapq module provides a heap-based priority queue implementation, but elements must support comparison. So each object in the queue is an EdgeWeight object.

Next, vertex_sets is initialized as a new VertexSetCollection and result_list is initialized as an empty list. Then the while loop runs as long as vertex_sets has more than one set and edge_list has at least one edge.

During each loop iteration, the edge with the lowest weight is removed from edge_list. set1 is assigned to the set containing the edge’s from_vertex and set2 is assigned to the set containing the edge’s to_vertex. If the two sets are not the same, the edge is added to result_list and set1 and set2 are merged within vertex_sets.

Answer 115

Kruskal’s minimum spanning tree

Question 116

An blank algorithm determines the shortest path between all possible pairs of vertices in a graph.

Answer 116

all pairs shortest path

Question 117

For a graph with vertices V, a blank represents the shortest path lengths between all vertex pairs in the graph. Each row corresponds to a start vertex, and each column in the matrix corresponds to a terminating vertex for each path. Ex: The matrix entry at row F and column T represents the shortest path length from vertex F to vertex T.

Answer 117

|V| x |V| matrix

Question 118

The blank algorithm generates a |V| x |V| matrix of values representing the shortest path lengths between all vertex pairs in a graph.

Answer 118

Floyd-Warshall all-pairs shortest path

Question 119

Graphs with cycles and negative edge weights are supported, but the graph must not have any blank. A blank is a cycle with edge weights that sum to a negative value.

Answer 119

negative cycles

Question 120

The Floyd-Warshall algorithm initializes the shortest path lengths matrix in 3 steps.

Answer 120

Every entry is assigned with infinity.
Each entry representing the path from a vertex to itself is assigned with 0.
For each edge from X to Y in the graph, the matrix entry for the path from X to Y is initialized with the edge’s weight.

Question 121

Although only shortest path lengths are computed by the Floyd-Warshall algorithm, the matrix can be used to blank the path sequence. Given the shortest path length from a start vertex to an end vertex is L. An edge from vertex X to the ending vertex exists such that the shortest path length from the starting vertex to X, plus the edge weight, equals L. Each such edge is found, and the path is reconstructed in reverse order.

Answer 121

reconstruct

Question 122

The Floyd-Warshall algorithm builds a |V| x |V| matrix and therefore has a space complexity of blank
. The matrix is constructed with a runtime complexity of blank
.

Answer 122

O(|V|^2)
O(|V|^3)

Question 123

The blank introduced in another section can be extended to assist with implementation of the all pairs shortest path algorithm

Answer 123

Graph class

Question 124

Takes a vertex label as an argument and returns the vertex in the graph with the specified label, or None if no such vertex exists.

Answer 124

get_vertex()

Question 125

Returns a list of all vertices in the graph. The all pairs shortest path algorithm commonly refers to vertices by index, so a linear list of all the graph’s vertices is more convenient than the graph’s adjacency_list dictionary.

Answer 125

get_vertex_list()

Question 126

Takes a vertex as an argument and returns a list of all edges from the graph that are incoming to that vertex.

Answer 126

get_incoming_edges()

Question 127

The Floyd-Warshall all pairs shortest path algorithm generates a blank of values representing the shortest path lengths between all vertex pairs in a graph. The all_pairs_shortest_path() function returns a list of lists, representing the |V| x |V| matrix of shortest path lengths. The list’s length equals the number of vertices in the graph. The length of each list in the list also equals the number of vertices in the graph.

Answer 127

|V| x |V| matrix

Question 128

The matrix returned from all_pairs_shortest_path() can be used to determine the list of edges in the shortest path between two vertices. The reconstruct_path() function takes 4 arguments

Answer 128

graph:
start_vertex
end_vertex
dist_matrix: The distances matrix built by all_pairs_shortest_path().

Question 129

Blank: The graph that the all pairs shortest path matrix was constructed for.

Answer 129

graph

Question 130

blank: Vertex at the start of the path.

Answer 130

start_vertex:

Question 131

Blank: Vertex at the end of the path.

Answer 131

end_vertex

Question 132

Blank: The distances matrix built by all_pairs_shortest_path().

Answer 132

dist_matrix