A new algorithm for minimum spanning tree using depth-first-search in an undirected graph

Abstract

A new algorithm is presented for the minimum spanning tree problem in any undirected graph. The algorithm does not use any sorting algorithm or priority queue or binary heaps. The algorithm is based on Depth-First-Search (DFS) and the heaviest edge of the seen cycle in DFS is deleted. It takes in worst case a time of 0(Kε) for a graph with v vertices and e edges and K = ε — (v — 1).

Keywords:

• Spanning tree
• Depth-First-Search
• back edge
• on-tree graph
• acyclic graph

Keywords:

• C.R. Categories
• G.2.1.
• G.2.2.