algorithm - 完全なグラフのサブグラフに対する bfs アルゴリズムの効率的な実装

Question

私は次の問題で立ち往生しています：

完全なグラフの一部であるサブグラフの隣接リストがあります。私がやりたいことは、与えられたサブグラフの補数に bfs アルゴリズムを適用することです。そのためには、補数の各頂点の後続が必要です。

それを行う最も効率的な方法は何ですか？グラフには膨大な数の頂点とエッジ (~1 000 000) があります。