For a practice question I have been given I have been told to find a spanning tree using a breadth first search for the following graph:
From this point onwards I know only to construct an adjacency matrix and that is all. How would I go about doing a breadth first search? Also, how would I choose the initial nodes to begin the search?
$\endgroup$2 Answers
$\begingroup$First, you should choose an arbitrary vertex, let it be $1$ to make it simple.
Then, the algorithm starts, $1$ is "done", now we check all neighbours of $1$, and we write them to our list: $1,2,3$. (We made the edges (1,2) and (1,3)). No more neighbours, so we check for new ones. $2$ has no more neighbours, $3$ has $4$ as a neighbour, so we have $1,2,3,4$(We made edge (3,4)). After this, we have $1,2,3,4,5,6$(We made edge(4,5)(4,6)). If you start the algorithm with $1$, then this is your result.
Your spanning tree: Vertexes are $1,2,3,4,5,6$, edges are $(1,2),(1,3), (3,4), (4,5),(4,6)$.
My description was not very "professional", but hope you understand the task. :)
Here is an other example to make it clearer, from Wikipedia:
We want to make a spanning tree from Frankfurt. This is the result if you run BFS:
In general, you can use any searching method on a connected graph to generate a spanning tree, with any source vertex.
Consider connecting a vertex to the "parent" vertex that "found" this vertex. Then, since every vertex is visited eventually, there is a path leading back to the source vertex.
By picking $2$ vertices $a, b$ and their paths to the source vertex, we see that there is a path between $a$ and $b$. Hence the graph is connected. Every vertex other than the source vertex generates an edge, so this graph has $n-1$ nodes. As such, it is a spanning tree of the original graph.
$\endgroup$
