由于传统朴素算法求解无向图的双连通分量时间花费过高,为了在线性时间内求出双连通分量并得到极大连通子图。文章对Tarjan算法的思想以及具体实现做出了详细的分析。同时结合具体实例,验证了算法中割点的判定条件以及回溯数组初始化的有效性和适用性。最后,给出了Tarjan算法在求解极大连通子图过程中,结点和栈空间状态转化图。
科研之友
微信
新浪微博
Facebook
分享链接
