A Polynomial Time Algorithm to Determine Singly Connectivity in Directed Graph

Abstract: In this paper, we consider the problem of determining whether or not a directed graph is singly connectedi.e. a directed graph is singly connected if for any pair of vertices there exists at most one simple path connecting them and also undirected graph is singly connected if and only if it is a tree. We have given a straight forward implementation of this problem using DFS algorithm theory which takes polynomial time to check it.

Keywords: DFS; source vertex; cyclic; tree; spanning forest.