基于Tarjan算法的极大点连通子图研究  

Research on Connected Maximal Subgraphs Based on Tarjan Algorithm

作　　者：付海奎 陈国军 王文波[1] FU Hai-kui;CHEN Guo-jun;WANG Wen-bo(Anhui University of Science and Technology,Huainan 232001,China)

机构地区：[1]安徽理工大学,安徽淮南232001

出　　处：《电脑知识与技术》2021年第22期85-87,93,共4页Computer Knowledge and Technology

基　　金：大学生创新创业项目(项目编号:S202010361245)。

摘　　要：由于传统朴素算法求解无向图的双连通分量时间花费过高,为了在线性时间内求出双连通分量并得到极大连通子图。文章对Tarjan算法的思想以及具体实现做出了详细的分析。同时结合具体实例,验证了算法中割点的判定条件以及回溯数组初始化的有效性和适用性。最后,给出了Tarjan算法在求解极大连通子图过程中,结点和栈空间状态转化图。Because the traditional naive algorithm takes too much time to solve the biconnected component of undirected graph,in order to find the biconnected component in linear time and obtain the maximally connected subgraph.The idea and implementation of Tarjan algorithm are analyzed in detail in this paper.At the same time,the validity and applicability of the decision condition of the cut point and the initialization of the backtracking array in the algorithm are verified by a concrete example.Finally,the state transition diagrams of node and stack space in the process of solving the maximally connected subgraphs of Tarjan algorithm are given.

关 键 词：极大连通子图 双连通分量 Tarjan算法 

分 类 号：O157.5[理学—数学]