Search Algorithms

Section 8.2 Search Algorithms

The graph \(G' = (V', E')\) is a subgraph of \(G = (V, E)\) if \(V' \subseteq V\) and \(E' \subseteq \{\{u, v\} \in E \ |\ u, v \in V'\}\text{.}\)

The subgraph \(G' = (V', E')\) is a spanning subgraph of \(G = (V, E)\) if \(V' = V\text{.}\)

A spanning tree for the graph \(G\) is a spanning subgraph of \(G\) that is a tree.

Given a graph, various algorithms can calculate a spanning tree, including depth-first search and breadth-first search.

Breadth-first search algorithm

Choose a vertex of the graph (root) arbitrarily.
Travel all the edges incident with the root vertex.
Give an order to this set of new vertices added.
Consider each of these vertices as a root, in order, and add all the unvisited incident edges that do not produce a cycle.
Repeat the method with the new set of vertices.
Follow the same procedure until all the vertices are visited.

The output of this algorithm is a spanning tree.

The breadth_first_search() function provides a flexible method for traversing both directed and undirected graphs. Let’s consider the following graph:

In the example above, the start parameter begins the traversal at vertex a. The report_distance=True, parameter reports pairs in the format (vertex, distance). Distance is the length of the path from the start vertex. From the output above, we see:

The distance from vertex a to vertex a is 0.
The distance from vertex a to vertex d is 1.
The distance from vertex a to vertex e is 1.
The distance from vertex a to vertex c is 1.
The distance from vertex a to vertex b is 2.

We can also set the parameter edges=True to return the edges of the BFS tree. Sage will raise an error if you use the edges and report_distance parameters simultaneously.

The above graph is a spanning tree, but not necessarily a minimum spanning tree. Let’s check how many spanning trees exist.

Iterate over all the spanning trees of a graph with spanning_trees().

Given a weighted graph of all possible spanning trees we can calculate, we may be interested in the minimal one. A minimal spanning tree is a spanning tree whose sum of weights is minimal. Prim’s Algorithm calculates a minimal spanning tree.

Prim’s Algorithm: Keep two disjoint sets of vertices. One \((L)\) contains vertices that are in the growing spanning tree, and the other \((R)\) that are not in the growing spanning tree.

Choose a vertex \(u \in V\) arbitrarily. At this step, \(L = \{u\}\) and \(R = V - \{u\}\text{.}\)
In \(R\text{,}\) select the cheapest vertex connected to the growing spanning tree \(L\) and add it to \(L\)
Follow the same procedure until all the vertices are in \(L\)

The output of this algorithm is a minimal spanning tree.

We can ask Sage for the minimal spanning tree of this graph. By running Graph.min_spanning_tree?? We can see that min_spanning_tree() uses a variation of Prim’s Algorithm by default. We can also use other algorithms such as Kruskal, Boruvka, or NetworkX.

From the output of min_spanning_tree(by_weight=True), we see an edge list of the minimal spanning tree. Each element of the edge lis is a tuple where the first two values are vertices, and the third value is the edge weight or label.

Let’s visualize the minimal spanning tree.

Let’s define a function to view the minimal spanning tree in the context of the original graph. The function parameters include:

graph: A SageMath Graph object.
mst_color: Color for edges part of the MST (default: 'darkred').
non_mst_color: Color for edges not part of the MST (default: 'lightblue').
figsize: Dimensions for the graph image.

Let’s generate a random graph and view the minimal spanning tree.

The following graph contains 9 vertices.

The following graph contains 15 vertices.

Prev Top Next