c++ - 生成随机图

Question

让某人输入一个整数 N 作为图中的顶点数。

• 在每条边上分配随机权重，范围从 1 到 10。并非所有可能的边虽然存在!如上例所示，用 X 表示不存在的边。
• 返回一对(M,L)，M和L分别为矩阵和列表表示您正在生成的(相同的)随机图。
• 使用非数字字符作为顶点名称，以避免与边权重混淆。

#include <iostream>
#include <stdlib.h>
using namespace std;
void gen_random_graph(int n)
{
    int adj_matrix[n][n];
    for(int u = 0; u < n; u++)
    {
        for (int v = 0; v < n; v++)
        {
            if(adj_matrix[u][v]==adj_matrix[v][u])
            {
                adj_matrix[u][v] = rand() % 10 + 1;
                cout << adj_matrix[u][v] << endl;
            }
        }
    }

}

int main()
{
    int N;
    cout << "enter number of vertices" << endl;
    cin >> N;
    gen_random_graph(N);

    return 0;
}

到目前为止，这是我的代码。它会产生权重吗？我必须退还一对是什么意思？

Answer 1

一个图可以表示为一个 N x N 的邻接矩阵(正如您已经设置的那样)，其中 matrix[i][j] 中的值对应于连接边的权重顶点 i 到顶点 j。零对应于 i 和 j 之间没有连接。如果 matrix[i][j] == matrix[j][i]，那么你有一个无向图。此外，随机图将具有随机值作为顶点之间的边。

在每条边存在或不存在的情况下(即权重为 0 或 1)，您可以采用以下方式:

这张图是从网上偷来的，所以我不相信它。请注意，您可以轻松确认第一个图是无向图，因为邻接矩阵是对称的。同样，第二个图是有向的，因为矩阵不是对称的。