期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2019
卷号：97
期号：16
页码：4439-4452
出版社：Journal of Theoretical and Applied
摘要：Finding strongly connected components (SCCs) in a directed graph (digraph) has been investigated extensively. Tarjan�s algorithm is the most fundamental method of finding SCCs in digraphs that uses Depth-First Search (DFS) and it has a linear time complexity. On the other hand, the Forward-Backward (FW-BW) algorithm is another well-known method that is based on the divide-and-conquer approach, yet it is time consuming. In this paper, we introduce a new approach for finding the SCCs in digraphs in linear time using Grey Wolf Optimizer (GWO), which is a recent metaheuristic algorithm. Experimental results show that finding SCCs using GWO outperforms FW-BW in terms of run time. In this context, GWO achieved 62.27% average run time improvement over FW-BW. Furthermore, average solution quality (accuracy) from GWO compared to the exact algorithm FW-BW is 97.57%.
