The modified deep first search algorithm: functional implementation

Abstract

The article includes the modified deep first search algorithm (DFS) that allows, at a single traversal of a graph, to check its connectivity/biconnectivity, highlight the cut vertices, and build the spanning tree, the biconnected components, and the fundamental set of cycles. The proposed algorithm was implemented and tested in a functional style using Common LISP language.

Keywords

• undirected and biconnected graphs
• spanning tree
• $dfs$
• cut vertices
• fundamental cycles
• functional programming