Lesson 4

As we have already seen, for many connected graphs, there are many ways to remove some edges from them so that the remaining graph turns out to be a tree. Such a tree is called spanning. There are also many ways to construct such trees. Two common construction strategies are depth-first search and breadth-first search. Each of these searches starts constructing a spanning tree from a given vertex \(s\), with breadth-first search traversing vertices in order of increasing distance from \(s\), and depth-first search repeatedly going to an unvisited neighbor whenever possible. These two strategies are often used in algorithms.

from networkx import Graph, dfs_tree, bfs_tree, nx_agraph

graph = Graph([(1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9), (1, 4), (4, 7), (2, 5), (5, 8), (6, 9)])

nx_agraph.to_agraph(dfs_tree(graph, source=1)).draw('dfs_tree.png', prog='dot')
nx_agraph.to_agraph(bfs_tree(graph, source=1)).draw('bfs_tree.png', prog='dot')