Connectivity algorithm with depth first search (DFS) on simple graphs
Oky Riansanti, Mahyus Ihsan, D Suhaimi · Journal of Physics Conference Series · 2018
This paper discusses an algorithm to detect connectivity of a simple graph using Depth First Search (DFS). The DFS implementation in this paper differs than other research, that is, on counting the number of visited vertices. The algorithm obtains s from the number of vertices and visits source vertex, following by its adjacent vertices until the last vertex adjacent to the previous source vertex. Any simple graph is connected if s equals 0 and disconnected if s is greater than 0. The complexity of the algorithm is O(n 2 ) .