1

这是我的数据结构课程的第一个作业的一部分，所以如果你只是告诉我我错在哪里而不是发布工作代码，我会很高兴。

我们应该编写一个程序，给定一个度数序列，绘制一个图形。我为图编写了数据结构，它可以正确连接两个顶点（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} 的不同组，它们之间没有任何联系。但它应该只创建一个图表。

我究竟做错了什么？

4

2 回答 2

1

根据维基百科，该算法产生一个简单的图，再次根据维基百科，它是“一个无向图，没有环，任何两个不同顶点之间不超过一条边”。

你得到的是一个具有两个不同连通分量的图，而不是两个图，所以算法似乎工作正常。

如果您的作业没有明确说明应该连接图表，您不必担心。

于 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”，您可以通过之后修改算法的结果来创建连通图。

如果该图证明是未连接的，则连接的组件之一必须包含一个循环。令 ( u , v ) 为循环中的任何边，令 ( s , t ) 为不同连通分量中的边。显然，图在对u , s和v , t之间没有边。通过删除边 ( u , v ) 和 ( s , t )，并插入边 ( u , s ) 和 ( v , t)，我们合并这两个组件。请注意，结果图仍然满足给定的度数序列。以这种方式进行，我们可以得到一个连接的拓扑。

于 2012-10-27T18:34:21.730 回答