图论缩点算法在城市道路问题的应用  

Connected-Block Algorithm and Its Application in Routing Problem

作　　者：黄检宝 王凌聪 HUANG Jianbao;WANG Lingcong(University of South China,Hengyang,China,421000)

机构地区：[1]南华大学,湖南衡阳421000

出　　处：《福建电脑》2020年第7期175-176,共2页Journal of Fujian Computer

摘　　要：本文使用图论算法对岛国城市道路问题进行建模,利用并查集对双连通分量进行优化,对岛国城市道路进行缩点,并重新建图,通过树的直径求解出城市任一两点间桥数量的最大值,最后总结了图论相关的缩点算法。

关 键 词：并查集 双连通分量 树的直径 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]