生成所有有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 之间有一个 link，另一个图在节点 3 和 1 之间有一个 link .那基本上就是同一个无向图

所以如果我是对的，我应该让我的程序不显示每张图两次，它应该可以工作。所以基本上我必须摆脱每个带有 "reversed" 节点的图表（所以如果我得到一个 link 在 1 和 3 之间的图表，我不应该得到另一个带有 link 的图表介于 3 和 1 之间，因为它们相同）。

我说得对吗？

如果可以，我该怎么做？

谢谢。

Answer 1

您的代码有问题：

tipar() 中 l 的值在赋值后没有增加。
邻接矩阵的大小是 n * n 而不是 k * k。

此代码按预期工作。

#include <iostream>
#include <fstream>

using namespace std;

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

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

int pow(int a, int b) {
    int r = 1;
    while (b) {
    if (b&1) r *= a;
    b >>= 1;
    a *= a;
    }
    return r;
}

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

int valid(int k)
{
    return 1;
}

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

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

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

Generate all undirected graphs with n nodes

c++

algorithm

graph-theory

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

Generate all undirected graphs with n nodes

c++

algorithm

graph-theory

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