大门|大门-CS-2006 |问题47

考虑下面的图表： 以下哪一项不能是使用Kruskal算法按顺序添加到最小生成树的边序列？

（A） （a-b）、（d-f）、（b-f）、（d-c）、（d-e） （B） （a-b）、（d-f）、（d-c）、（b-f）、（d-e） （C） （d-f）、（a-b）、（d-c）、（b-f）、（d-e） （D） （d-f）、（a-b）、（b-f）、（d-e）、（d-c） 答复: （D） 说明： 边（d-e）不能在中的（d-c）之前考虑 Kruskal最小生成树算法 因为Kruskal的算法在每一步从当前的边集合中选取权重最小的边。 这个问题的小测验