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

发布时间：2021-10-15 21:54

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

【文章来源】：福建电脑. 2020,36(07)

【文章页数】：2 页

【文章目录】：
1 引言
2 任务及目标
    2.1 问题描述
    2.2 算法输入格式
    2.3 算法输出格式
3 算法分析和设计
    3.1 解决思路
    3.2 并查集优化Tarjan算法
    3.4 树的直径
    3.5 算法复杂的分析
        3.5.1 空间复杂度分析
        3.5.2 时间复杂度分析
4 缩点建图的推广与应用
5 结语



本文编号：3438685