グラフ内の頂点のセットを分離する

Question

私は、グラフ内に分割されていない部分のセットを生成する簡単な方法を見つけたいと思っています。つまり、次のグラフでは、{A、B、C、D}と{E、F}の2つのセットを取得したいと考えています。

Answer 1

任意のグラフトラバーサルアルゴリズム（BFSおよびDFSが最も一般的です）を使用できます。

アルゴリズムが「スタック」している（トラバースするノードがもうない）ときはいつでも、1つのコンポーネントを見つけてマークし、次のコンポーネントを見つけるためにまだトラバースされていないランダムな頂点を選択します。