创建随机邻接矩阵，每个节点的最小度数为 'k'

Question

我想创建一个随机邻接矩阵，其中每个节点都连接到 'k' 个其他节点。邻接矩阵表示的图是无向的。

我从邻接矩阵中的 7 个节点开始，每个节点应该至少连接到其他 3 个节点。到目前为止，我已经能够得到这个：

0 1 1 0 0 0 0 
1 0 1 1 0 0 0 
1 1 0 1 1 0 0 
0 1 1 0 1 1 0 
0 0 1 1 0 1 1 
0 0 0 1 1 0 1 
0 0 0 0 1 1 0

从矩阵可以看出，第一行和最后一行的连接少于三个。

到目前为止我的实现是：

   for( int i= 0; i<7; i++){
  for( int j= i+1; j<7; j++){
    if(i==j){
        topo[i][j]=0;
     }
    else{    
        for(int k=j; k<i+3 && k<7; k++){
            int connectivity=0;
            while(connectivity<3){
           if(topo[i][k]!=1 && topo[k][i]!=1){
                   topo[i][k]=1;
               topo[k][i]=1;
               connectivity++;
                }
           else{
               connectivity++;
        }
             }
          }
      }
   }
}

Answer 1

我假设我们在这里讨论的是有向图。让我们假设 v 是一些顶点（节点）和 d 的顶点 A （度数，你的 k）是从 A到其他节点。

如果仔细观察，您会发现，k-th 节点的 d 值是 kth 行中的 1 的数字。所以唯一要做的就是为每一行绘制 0s 和 1s 的矢量 v-1 （我们不将节点与其自身连接）元素。

您可以通过向其中写入 d 个并随机排列来绘制由 0 和 1 组成的随机向量。

无向图的注意事项 - 您可以将此算法应用于右上矩阵三角形，将已知值动态改写为左下角的值。比从上到下的每一行你可以采用算法，绘制原始的其余部分。

创建随机邻接矩阵，每个节点的最小度数为 'k'

Create random adjacency matrix with each node having a minimum degree of 'k'

c++

networking

routing

graph

c++11