从所有顶点的给定度数构造一个图-yiteyi-C++库

这是一个C++程序，用于生成给定固定度序列的图。该算法生成给定度序列的无向图。它不包括自边和多条边。 例如：

null

Input : degrees[] = {2, 2, 1, 1}Output :  (0)  (1)  (2)  (3)    (0)    0    1    1    0                                  (1)    1    0    0    1                       (2)    1    0    0    0                           (3)    0    1    0    0     Explanation : We are given that thereare four vertices with degree of vertex0 as 2, degree of vertex 1 as 2, degreeof vertex 2 as 1 and degree of vertex 3as 1. Following is graph that followsgiven conditions.                       (0)----------(1)     |            |      |            |      |            |    (2)          (3)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 1-输入顶点数及其对应的度数。 2-声明邻接矩阵，mat[][]以存储图形。 3-要创建图形，请创建第一个循环以连接每个顶点“i”。 4秒嵌套循环，将顶点“i”连接到它旁边的每个有效顶点“j”。 5-如果顶点“i”和“j”的阶数大于零，则连接它们。 6-打印邻接矩阵。基于上述解释，以下是实现：

C++

                         // C++ program to generate a graph for a                       
                         // given fixed degrees                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A function to print the adjacency matrix.                       
                         void                                     printMat(                                     int                                     degseq[],                                     int                                     n)                       
                         {                       
                                                 // n is number of vertices                       
                                                 int                                     mat[n][n];                       
                                                 memset                                     (mat, 0,                                     sizeof                                     (mat));                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++) {                       
           
                                                 // For each pair of vertex decrement                       
                                                 // the degree of both vertex.                       
                                                 if                                     (degseq[i] > 0 && degseq[j] > 0) {                       
                                                 degseq[i]--;                       
                                                 degseq[j]--;                       
                                                 mat[i][j] = 1;                       
                                                 mat[j][i] = 1;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Print the result in specified format                       
                                                 cout <<                                     ""                       
                                                 << setw(3) <<                                     "     "                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << setw(3) <<                                     "("                                     << i <<                                     ")"                                     ;                       
                                                 cout <<                                     ""                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 cout << setw(4) <<                                     "("                                     << i <<                                     ")"                                     ;                       
                                                 for                                     (                                     int                                     j = 0; j < n; j++)                       
                                                 cout << setw(5) << mat[i][j];                       
                                                 cout <<                                     ""                                     ;                       
                                                 }                       
                         }                       
           
                         // driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     degseq[] = { 2, 2, 1, 1, 1 };                       
                                                 int                                     n =                                     sizeof                                     (degseq) /                                     sizeof                                     (degseq[0]);                       
                                                 printMat(degseq, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to generate a graph for a                       
                         // given fixed degrees                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // A function to print the adjacency matrix.                       
                         static                                     void                                     printMat(                                     int                                     degseq[],                                     int                                     n)                       
                         {                       
                                                 // n is number of vertices                       
                                                 int                                     [][]mat =                                     new                                     int                                     [n][n];                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ; j < n; j++)                       
                                                 {                       
           
                                                 // For each pair of vertex decrement                       
                                                 // the degree of both vertex.                       
                                                 if                                     (degseq[i] >                                     0                                     && degseq[j] >                                     0                                     )                       
                                                 {                       
                                                 degseq[i]--;                       
                                                 degseq[j]--;                       
                                                 mat[i][j] =                                     1                                     ;                       
                                                 mat[j][i] =                                     1                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Print the result in specified format                       
                                                 System.out.print(                                     ""                                     + setw(                                     3                                     ) +                                     "     "                                     );                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(setw(                                     3                                     ) +                                     "("                                     + i +                                     ")"                                     );                       
                                                 System.out.print(                                     ""                                     );                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 System.out.print(setw(                                     4                                     ) +                                     "("                                     + i +                                     ")"                                     );                       
                                   
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < n; j++)                       
                                                 System.out.print(setw(                                     5                                     ) + mat[i][j]);                       
                                                 System.out.print(                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         static                                     String setw(                                     int                                     n)                       
                         {                       
                                                 String space =                                     ""                                     ;                       
                                                 while                                     (n-- >                                     0                                     )                       
                                                 space +=                                     " "                                     ;                       
                                                 return                                     space;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     degseq[] = {                                     2                                     ,                                     2                                     ,                                     1                                     ,                                     1                                     ,                                     1                                     };                       
                                                 int                                     n = degseq.length;                       
                                                 printMat(degseq, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python3

                         # Python3 program to generate a graph                       
                         # for a given fixed degrees                       
           
                         # A function to print the adjacency matrix.                       
                         def                                     printMat(degseq, n):                       
                                   
                                                 # n is number of vertices                       
                                                 mat                                     =                                     [[                                     0                                     ]                                     *                                     n                                     for                                     i                                     in                                     range                                     (n)]                       
           
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n):                       
           
                                                 # For each pair of vertex decrement                       
                                                 # the degree of both vertex.                       
                                                 if                                     (degseq[i] >                                     0                                     and                                     degseq[j] >                                     0                                     ):                       
                                                 degseq[i]                                     -                                     =                                     1                       
                                                 degseq[j]                                     -                                     =                                     1                       
                                                 mat[i][j]                                     =                                     1                       
                                                 mat[j][i]                                     =                                     1                       
           
                                                 # Print the result in specified form                       
                                                 print                                     (                                     "      "                                     , end                                     =                                     " "                                     )                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (                                     " "                                     ,                                     "("                                     , i,                                     ")"                                     , end                                     =                                     "")                       
                                                 print                                     ()                       
                                                 print                                     ()                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (                                     " "                                     ,                                     "("                                     , i,                                     ")"                                     , end                                     =                                     "")                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 print                                     (                                     "     "                                     , mat[i][j], end                                     =                                     "")                       
                                                 print                                     ()                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 degseq                                     =                                     [                                     2                                     ,                                     2                                     ,                                     1                                     ,                                     1                                     ,                                     1                                     ]                       
                                                 n                                     =                                     len                                     (degseq)                       
                                                 printMat(degseq, n)                       
           
                         # This code is contributed by PranchalK                       

C#

                         // C# program to generate a graph for a                       
                         // given fixed degrees                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         // A function to print the adjacency matrix.                       
                         static                                     void                                     printMat(                                     int                                     []degseq,                                     int                                     n)                       
                         {                       
                                                 // n is number of vertices                       
                                                 int                                     [,]mat =                                     new                                     int                                     [n, n];                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++)                       
                                                 {                       
           
                                                 // For each pair of vertex decrement                       
                                                 // the degree of both vertex.                       
                                                 if                                     (degseq[i] > 0 && degseq[j] > 0)                       
                                                 {                       
                                                 degseq[i]--;                       
                                                 degseq[j]--;                       
                                                 mat[i, j] = 1;                       
                                                 mat[j, i] = 1;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Print the result in specified format                       
                                                 Console.Write(                                     ""                                     + setw(3) +                                     "     "                                     );                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(setw(3) +                                     "("                                     + i +                                     ")"                                     );                       
                                                 Console.Write(                                     ""                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 Console.Write(setw(4) +                                     "("                                     + i +                                     ")"                                     );                       
                                   
                                                 for                                     (                                     int                                     j = 0; j < n; j++)                       
                                                 Console.Write(setw(5) + mat[i, j]);                       
                                                 Console.Write(                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         static                                     String setw(                                     int                                     n)                       
                         {                       
                                                 String space =                                     ""                                     ;                       
                                                 while                                     (n-- > 0)                       
                                                 space +=                                     " "                                     ;                       
                                                 return                                     space;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     []degseq = { 2, 2, 1, 1, 1 };                       
                                                 int                                     n = degseq.Length;                       
                                                 printMat(degseq, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Princi Singh                       

Javascript

                         <script>                       
           
                         // JavaScript program to generate a graph for a                       
                         // given fixed degrees                       
           
                         // A function to print the adjacency matrix.                       
                         function                                     printMat(degseq,n)                       
                         {                       
                                                 // n is number of vertices                       
                                                 let mat =                                     new                                     Array(n);                       
                                                 for                                     (let i=0;i<n;i++)                       
                                                 {                       
                                                 mat[i]=                                     new                                     Array(n);                       
                                                 for                                     (let j=0;j<n;j++)                       
                                                 mat[i][j]=0;                       
                                                 }                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 for                                     (let j = i + 1; j < n; j++)                       
                                                 {                       
                                   
                                                 // For each pair of vertex decrement                       
                                                 // the degree of both vertex.                       
                                                 if                                     (degseq[i] > 0 && degseq[j] > 0)                       
                                                 {                       
                                                 degseq[i]--;                       
                                                 degseq[j]--;                       
                                                 mat[i][j] = 1;                       
                                                 mat[j][i] = 1;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Print the result in specified format                       
                                                 document.write(                                     "<br>"                                     + setw(3) +                                     "     "                                     );                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(setw(3) +                                     "("                                     + i +                                     ")"                                     );                       
                                                 document.write(                                     "<br><br>"                                     );                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 document.write(setw(4) +                                     "("                                     + i +                                     ")"                                     );                       
                                   
                                                 for                                     (let j = 0; j < n; j++)                       
                                                 document.write(setw(5) + mat[i][j]);                       
                                                 document.write(                                     "<br>"                                     );                       
                                                 }                       
                         }                       
           
                         function                                     setw(n)                       
                         {                       
                                                 let space =                                     ""                                     ;                       
                                                 while                                     (n-- > 0)                       
                                                 space +=                                     "&nbsp"                                     ;                       
                                                 return                                     space;                       
                         }                       
           
                         // Driver Code                       
                         let degseq=[2, 2, 1, 1, 1];                       
                         let n = degseq.length;                       
                         printMat(degseq, n);                       
           
                         // This code is contributed by rag2127                       
           
                         </script>                       

输出：

        (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

时间复杂性： O（v*v）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章