An Efficient Approach for Constructing Spanning Trees by Applying BFS and DFS Algorithm Directly on Non regular Graphic Sequences
Realization of graphic sequences and finding the spanning tree of a graph are two popular problems of combinatorial optimization. A simple graph that realizes a given non negative integer sequence is often termed as a realization of the given sequence. In this paper we have proposed a method for obtaining a spanning tree directly from a degree sequence by applying BFS and DFS algorithm separately, provided the degree sequence is graphic and non regular. The proposed method is a two step process. First we apply an algorithm to check whether the input sequence is realizable through the construction of the adjacency matrix corresponding to the degree sequence. Then we apply the BFS and DFS algorithm separately to generate the spanning tree from it.