C++のすべての頂点の特定の次数からグラフを作成します

頂点のリストがあり、それらの次数が与えられているとします。その次数シーケンスから1つの無向グラフを生成する必要があります。ループや複数のエッジは含まれません。したがって、次数シーケンスが[2、2、1、1]のような場合、グラフは次のようになります

これを解決するには、次の手順に従います-

• グラフを保存するための隣接行列adjを定義します

• 頂点iごとに、実行

  • 有効な各頂点jについて、i

    の隣

    • 頂点iとjの次数がゼロより大きい場合は、それらを接続します

• マトリックスを表示します。

例

#include <iostream>
#include <iomanip>
using namespace std;
void generateGraph(int vert_degree[], int n) {
   int adj_mat[n][n];
   for(int i = 0; i<n; i++){
      for(int j = 0; j < n; j++){
         adj_mat[i][j] = 0;
      }
   }
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (vert_degree[i] > 0 && vert_degree[j] > 0) {
            vert_degree[i]--; vert_degree[j]--;
            adj_mat[i][j] = adj_mat[j][i] = 1;
         }
      }
   }
   cout << endl << setw(3) << " ";
   for (int i = 0; i < n; i++)
      cout << setw(3) << "(" << i << ")";
      cout << endl << endl;
   for (int i = 0; i < n; i++) {
      cout << setw(4) << "(" << i << ")";
   for (int j = 0; j < n; j++)
      cout << setw(5) << adj_mat[i][j];
      cout << endl;
   }
}
int main() {
   int vert_degree[] = { 2, 2, 1, 1, 1 };
   int n = sizeof(vert_degree) / sizeof(vert_degree[0]);
   generateGraph(vert_degree, n);
}

出力

      (0)   (1)  (2)  (3)  (4)

(0)    0    1    1    0    0
(1)    1    0    0    1    0
(2)    1    0    0    0    0
(3)    0    1    0    0    0
(4)    0    0    0    0    0