---
title: "Spanning Trees of a Graph or Digraph"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/spanning-tree.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/spanning-tree.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Matrices and Vector Spaces Associated with a Graph or Digraph", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/matrix-vector-space.md"}
next: {"title": "Directed Trees", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/directed-tree.md"}
intrinsics:
  - {"name": "SpanningTree", "signature": "SpanningTree(G): GrphUnd -> Grph, GrphVertSet, GrphEdgeSet"}
  - {"name": "SpanningForest", "signature": "SpanningForest(G): Grph -> Grph, GrphVertSet, GrphEdgeSet"}
  - {"name": "BreadthFirstSearchTree", "signature": "BreadthFirstSearchTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet"}
  - {"name": "BFSTree", "signature": "BFSTree(u): GrphVert -> Grph"}
  - {"name": "DepthFirstSearchTree", "signature": "DepthFirstSearchTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum"}
  - {"name": "DFSTree", "signature": "DFSTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum"}
---

<a id="spanning-tree"></a>
<a id="graph-sec-spanning"></a>
# Spanning Trees of a Graph or Digraph

<a id="function-spanningtree-grphund"></a>
## `SpanningTree(G): GrphUnd -> Grph, GrphVertSet, GrphEdgeSet`

Given a connected (undirected) graph $G$, construct a spanning tree for $G$ rooted at an arbitrary vertex of $G$. The spanning tree is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

<a id="function-spanningforest-grph"></a>
## `SpanningForest(G): Grph -> Grph, GrphVertSet, GrphEdgeSet`

Given a graph $G$, construct a spanning forest for $G$. The forest is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

<a id="function-breadthfirstsearchtree-grphvert"></a>
## `BreadthFirstSearchTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet`

<a id="function-bfstree-grphvert"></a>
## `BFSTree(u): GrphVert -> Grph`

Given a vertex $u$ belonging to the graph $G$, return a breadth-first search for $G$ rooted at the vertex $u$. The tree is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph. Note that $G$ may be disconnected.

<a id="function-depthfirstsearchtree-grphvert"></a>
## `DepthFirstSearchTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum`

<a id="function-dfstree-grphvert"></a>
## `DFSTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum`

Given a vertex $u$ belonging to the graph $G$, return a depth-first search tree $T$ for $G$ rooted at the vertex $u$. The tree $T$ is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph. Note that $G$ may be disconnected.

The fourth return argument returns, for each vertex $u$ of $G$, the tree order of $u$, that is, the order in which the vertex $u$ has been visited while performing the depth-first search. If $T$ does not span $G$ then the vertices of $G$ not in $T$ are given tree order from `Order(T) + 1` to `Order(G)`.
