1

これは私のデータ構造コースの最初の割り当ての一部なので、動作するコードを投稿する代わりに、どこが間違っているかを教えていただければ幸いです。

次数列を与えられてグラフを描くプログラムを書くことになっています。グラフのデータ構造を書きましたが、2 つの頂点を適切に接続できます (graph.addConnection)。しかし、度数列からグラフを作成する方法を見つけることができませんでした。

このウィキペディアのページでは、単純なアルゴリズムが提供されています。

  1. エッジのないグラフから始めます。
  2. 次数要件がまだ満たされていない頂点のリストを、残りの次数要件の昇順でない順序で維持します。
  3. 最初の頂点をこのリストの次の d1 頂点に接続し、リストから削除します。リストを並べ替え、すべての学位要件が満たされるまで繰り返します。

そして、次のようにJavaで実装しました。

public static void populate(Graph graph, int[] degrees) {
    class DegreeMapping {
        int vertice=0;
        int degree=0;
    }

    ArrayList<DegreeMapping> degrees_ = new ArrayList<DegreeMapping>(degrees.length);
    for(int i=0; i<degrees.length; i++) {
        degrees_.add(new DegreeMapping());
        degrees_.get(i).vertice = i;
        degrees_.get(i).degree = degrees[i];
    }

    while(! degrees_.isEmpty()) {
        // Sort by degrees
        Collections.sort(degrees_, new Comparator<DegreeMapping>() {
                                @Override
                                public int compare(DegreeMapping o1, DegreeMapping o2) {
                                    return o2.degree - o1.degree ;
                                }
                            }); 
        for(DegreeMapping i: degrees_) System.out.printf("{%d, #%d} ", i.degree, i.vertice );
        System.out.println();

        for(int i=1; i<degrees_.get(0).degree+1; i++) {
            degrees_.get(i).degree--;
            graph.addConnection(degrees_.get(0).vertice, degrees_.get(i).vertice);
            System.out.printf("#%d <-> #%d \n", degrees_.get(0).vertice, degrees_.get(i).vertice);
        }

        degrees_.remove(0); 
    }
}

次数シーケンスに対して次の出力が得られます2 2 2 2 2 2 2 2。

{2, #0} {2, #1} {2, #2} {2, #3} {2, #4} {2, #5} {2, #6} {2, #7} 
#0 <-> #1 
#0 <-> #2 
{2, #3} {2, #4} {2, #5} {2, #6} {2, #7} {1, #1} {1, #2} 
#3 <-> #4 
#3 <-> #5 
{2, #6} {2, #7} {1, #4} {1, #5} {1, #1} {1, #2} 
#6 <-> #7 
#6 <-> #4 
{1, #7} {1, #5} {1, #1} {1, #2} {0, #4} 
#7 <-> #5 
{1, #1} {1, #2} {0, #5} {0, #4} 
#1 <-> #2 
{0, #2} {0, #5} {0, #4} 
{0, #5} {0, #4} 
{0, #4}

ご覧のとおり、頂点 {0, 1, 2} と {3, 4, 5, 6, 7} を持つ 2 つの異なるグループが作成されましたが、それらの間に接続はありません。ただし、作成するグラフは 1 つだけです。

私は何を間違っていますか？

4

2 に答える 2

1

ウィキペディアによると、そのアルゴリズムは単純なグラフを生成します。これは、ウィキペディアによると、「ループがなく、2 つの異なる頂点間にエッジが 1 つしかない無向グラフ」です。

得られるのは、2 つのグラフではなく、2 つの異なる連結要素を持つグラフであるため、アルゴリズムは正しく機能しているように見えます。

割り当てで、グラフを接続する必要があることが明示的に示されていない場合でも、心配する必要はありません。

于 2012-10-27T18:52:18.020 に答える
0

頂点番号でもソートするとうまくいくようです。

// Sort by degrees and then vertex number
Collections.sort(degrees_, new Comparator<DegreeMapping>() {
    @Override
    public int compare(DegreeMapping o1, DegreeMapping o2) {
        if (o1.degree == o2.degree) return o2.vertice - o1.vertice;
        return o2.degree - o1.degree;
    }
});

結果：

{2, #0}, {2, #1}, {2, #2}, {2, #3}, {2, #4}, {2, #5}, {2, #6}, {2, #7}
#0 <-> #1
#0 <-> #2
{2, #3}, {2, #4}, {2, #5}, {2, #6}, {2, #7}, {1, #1}, {1, #2}
#3 <-> #4
#3 <-> #5
{2, #6}, {2, #7}, {1, #1}, {1, #2}, {1, #4}, {1, #5}
#6 <-> #7
#6 <-> #1
{1, #2}, {1, #4}, {1, #5}, {1, #7}, {0, #1}
#2 <-> #4
{1, #5}, {1, #7}, {0, #1}, {0, #4}
#5 <-> #7
{0, #7}, {0, #1}, {0, #4}
{0, #1}, {0, #4}
{0, #4}

Mihail と Vishnoi による論文「On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications」によると、後でアルゴリズムの結果を変更することで接続グラフを作成できます。

このグラフが接続されていないことが判明した場合、接続されたコンポーネントの 1 つにサイクルが含まれている必要があります。( u , v ) をサイクル内の任意のエッジとし、( s , t ) を別の連結要素内のエッジとします。明らかに、グラフにはuとs のペアとvとtのペアの間にエッジがありません。エッジ ( u , v ) および ( s , t ) を削除し、エッジ( u , s ) および ( v , t )を挿入することによって)、これら 2 つのコンポーネントをマージします。結果のグラフは、指定された次数シーケンスを満たしていることに注意してください。このように進めていくと、接続されたトポロジーが得られます。

于 2012-10-27T18:34:21.730 に答える