資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝研究
法律研究利用 C++ 中所有頂點的給定度數構建一張圖
假設我們有一個頂點列表，並且給出了它們的度數。我們必須根據那個度數序列生成一個無向圖。它將不包括環路或多重邊。所以，如果度數序列類似於 [2、2、1、1]，則該圖可以如下所示
為了解決這個問題，我們將遵循以下步驟：
定義相鄰矩陣 adj 來儲存該圖
對於每個頂點 i，執行
對於下一個與 i 相鄰的每個有效頂點 j
如果頂點 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
更新日期：2020 年 1 月 3 日
252 次瀏覽
廣告