k近傍検索はグラフ構造において特定の頂点からk個の近傍を特定する検索であり，検索の高速化が重要となっている．代表的な高速化手法としてグラフを用いたインデックスを作成する方法があり，様々なインデックスが考案されている．しかし，それらのインデックスは主に交通ネットワークなどの単純なグラフに特化しており，ソーシャルネットワークなどの複雑なグラフに適用するのが難しい．そこで本稿では，複雑なグラフでも検索を高速に処理できる最小全域木を基にしたグラフ型インデックスを提案する．実データを用いた実験を行い，既存の手法に比べてインデックス作成時間を最大181倍高速に計算できることを確認した．