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 graphs. Let’s consider the following graph:In the example above, the breadth-first search algorithm function starts at vertex
0, and reports the length of each vertex from the starting point. Each element in the output is a tuple consisting of a vertex and its length from the starting vertex.Given a weighted graph, of all possible spanning trees that we can calculate, we may be interested in the minimal one. A minimal spanning tree is a spanning tree whose sum of wights is minimal. Prim’s Algorithm calculates a minimal spanning tree including.
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.
Let’s examine the following graph:
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.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.
