生成具有n个节点的所有无向图

Question

我正在尝试使用递归回溯生成具有n个节点的所有无向图。我必须将它们的矩阵（我不知道它的英文名称-在我的语言中是相邻的矩阵-是吗？）写入文件中。

例如：

输入

输出

这是我的程序：

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("gengraf.in");
ofstream g("gengraf.out");

int st[100], n, adiacenta[100][100], l=1;

void tipar(int k)
{
    for (int i = 1; i < k; i++)
    {
        for (int j = i+1; j < k; j++)
        {
            adiacenta[i][j] = adiacenta[j][i] = st[l];
        }
        l++;
    }
    for (int i = 1; i < k; i++)
    {
        for (int j = 1; j < k; j++)
        {
            g << adiacenta[i][j] << " ";
        }
        g << endl;
    }
}

int valid(int k)
{
    return 1;
}

void back(int k)
{
    if (k == ((n - 1) * n / 2) + 1)
    {
        l = 1;
        tipar(k);
        g << endl;
    }
    else
    {
        for (int i = 0; i <= 1; i++)
        {
            st[k] = i;
            if (valid(k))
            {
                back(k + 1);
            }
        }
    }
}

int main()
{
    f >> n;
    g << pow(2, (n * (n - 1))/2);
    g << endl;
    back(1);
}

但是我的输出是：

而且我不知道该如何解决。

我知道为什么会发生-我生成2 ^（n *（n-1））/ 2）个图（因为这是n个节点的无向图的数量），而不是生成8个不同的图，我只得到4个不同的，显示2次。

那是（我想），因为我的程序输出的图具有节点1和3之间的链接，而另一个图具有节点3和1之间的链接。这基本上是相同的无向图。 >

因此，如果我是对的，我应该让我的程序不要两次显示每个图形，它应该可以工作。因此，基本上，我必须摆脱带有“反向”节点的每个图（因此，如果我得到一个链接在1和3之间的图，那么我不应该再获得另一个链接在3和1之间的图，因为它们是相同的）。

我对吗？

如果是这样，我该怎么做？

谢谢。

我正在尝试使用递归回溯生成具有n个节点的所有无向图。我必须写出它们的矩阵（我不知道它怎么用英语称呼-用我的语言来说是...

Answer 1

0
投票

您的代码有问题：

生成具有n个节点的所有无向图

问题描述投票：0回答：1

1个回答

最新问题

生成具有n个节点的所有无向图

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1