3
2次元平面上の点集合間のユークリッド距離に基づいて、最小スパニングツリーを計算します。私の現在のコードは、すべてのエッジを格納し、最小スパニングツリーを取得するためにPrimのアルゴリズムを実行します。しかし、私はこれを行うにはすべてのエッジのためにO(n^2)スペースを取ることを認識しています。ユークリッド最小スパニングツリーとドローネ三角形分割
最初にこの点集合のdelaunay三角測量を計算してから、PrimとKruskalのアルゴリズムを実行して最小スパニングツリーを取得すると、メモリとランタイムを最適化できることが明らかになりました。三角測量。
これはプログラミングコンテストの一部です（https://prologin.org/train/2017/qualification/taxi_des_neiges）ので、私はscipy.spatialを使用することはできません。 Delaunay三角測量に含まれるエッジを取得するだけの選択肢はありますか？
ありがとうございます。
おかげでDelaunay三角形分割を実施し、エッジを取得するためのコードを持ってどこかに、このフォルダ内の... ... QHullを、使用していますように見えますしかし、可能であれば、私はPythonのソースコードを望んでいます。 –
問題はありません、うまくいけば、wildwilhelmの答えが助けになるでしょう！彼はアルゴリズムの抽象的な記述を見つけたようです。 – Marviel
はい両方の答えが私を助けたので、ここに感謝のためのupvoteです！ –