大门|大门IT 2005 |问题15

在下表中，左栏包含标准图算法的名称，右栏包含算法的时间复杂性。将每个算法与其时间复杂度进行匹配。

（A） 1.→ C、 二,→ A、 三,→ B、 四,→ D （B） 1.→ B、 二,→ D、 三,→ C、 四,→ A. （C） 1.→ C、 二,→ D、 三,→ A、 四,→ B （D） 1.→ B、 二,→ A、 三,→ C、 四,→ D 答复: （A） 说明：

• 贝尔曼-福特算法 ：时间复杂度：O（VE）
• 克鲁斯卡尔算法 : 时间复杂性： O（ElogE）或O（ElogV）。边的排序需要O（ELogE）时间。排序后，我们迭代所有边，并应用find union算法。查找和联合操作可能需要atmost O（LogV）时间。所以总体复杂度是O（ELogE+ELogV）时间。E的值可以是atmost V^2，所以O（LogV）与O（LogE）相同。因此，总体时间复杂度为O（ElogE）或O（ElogV）
• 弗洛伊德·沃沙尔算法 : 时间复杂性 ：O（V^3）
• 拓扑排序 : 时间复杂性： 上述算法只是带有额外堆栈的DFS。所以时间复杂度和DFS一样，DFS是O（V+E）。

这个问题的小测验