5

いくつかのグラフ アルゴリズムを調べています (これは宿題ではありません。アルゴリズムとデータ構造についてブラッシュアップしているだけです)。質問があります。次の無向グラフがあるとします。

var graph = {
    9: [19, 26],
    13: [19, 5],
    17: [],
    26: [11, 18],
    18: [9],
    19: [],
    23: [24],
    24: [],
    11: [],
    18: []
};

グラフは基本的に次のようになります。

ここに画像の説明を入力

このグラフにはいくつの連結成分がありますか? グラフだけ見ると、3 つのコンポーネントがあるように見えます。しかし、実際にアルゴリズムを実装すると (各頂点を反復処理し、その頂点が検出されない場合はその頂点を開始点として使用して bfs を実行します。また、bfs は検出された頂点をマークします)。

から開始すると9、最終的に次のノードが検出されます: [19, 26, 11, 18]。ただし、の隣接リスト13にないため、 は検出されません。19ただし、19は13の隣接リストにあります。これが、1 つの余分なコンポーネントになってしまう理由です。

これは正しいです？実際には 4 つの個別のコンポーネントがありますか?もしそうなら、接続されたコンポーネントの私の理解は間違っていますか?

4

2 に答える 2

4

問題は、無向グラフの隣接リスト表現の場合、次のいずれかを行う必要があることです。

(1) 対称隣接リストを使用します。つまり、新しいエッジを配置する場合abは、追加bしadjlist[a] 、その逆も同様です。

また

(2) エッジの存在を探すたびに、すべての頂点の隣接リストを走査します。

(2) は非常に効率が悪いため、通常は (1) を使用します。これは、一般的に使用される adj リストの規則でもあります。私があなたのadjリストを提示された場合、グラフは方向付けられていると思います.

于 2013-04-07T01:45:48.980 に答える
3

隣接リストの表現を変更できます。表現は「有向」ですが、画像は無向です。エッジ (a,b) グラフ {a: [b], b:[a]} の場合

于 2013-04-07T01:46:15.280 に答える