資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中最大化圖中不屬於任何邊的節點數
給定一個包含節點和邊的圖，目標是找到可能連線到圖的任何邊的最大節點數。我們知道，節點數始終小於或等於完全圖中的邊數。
我們將透過嘗試建立一個完全圖來實現這一點，如果節點數為n，則將有n(n-1)/2條邊。
邊數 = n(n-1)/2 (其中n為節點數)
2 * 邊數 = n(n-1)。一旦n(n-1) > 邊數，我們就有了額外的節點。所以從i=1迭代到i=n。
直到i(i-1) > 2 * 邊數。返回n-i作為結果。
讓我們透過例子來理解：
**輸入** - 節點數=5，邊數=2
**輸出** - 圖中不屬於任何邊的最大節點數為：2
**解釋** -
2條邊至少可以有3個節點，最多可以有4個節點。
對於3個節點，沒有邊的最大剩餘節點數=2
**輸入** - 節點數=2，邊數=1
**輸出** - 圖中不屬於任何邊的最大節點數為：0
**解釋** -
至少需要2個節點才能構成一條邊。在這種情況下，兩個節點都被佔用。沒有剩餘節點。
下面程式中使用的演算法如下：
我們使用兩個變數nodes和edges來儲存可用資料。
函式maximum(int nodes, int edges) 將節點數和邊數作為引數，並返回圖中不屬於任何邊的最大節點數。
使用變數i，temp和max。
從i=0開始迴圈，直到i<=nodes
計算temp = i*(i-1)
計算變數total為2*edges
當temp大於total時，中斷迴圈
計算max為max = nodes - i
返回結果max。
示例
#include <bits/stdc++.h>
using namespace std;
int maximum(int nodes, int edges){
int i, temp = 0, max;
for (i = 0; i <= nodes; i++){
temp = i * (i - 1);
int total = 2* edges;
if (temp >= total){
break;
}
}
max = nodes - i;
return max;
}
int main(){
int nodes = 10;
int edges = 5;
cout<<"Maximize number of nodes which are not part of any edge in a Graph are:"<<maximum(nodes, edges) << endl;
}輸出
如果執行以上程式碼，將生成以下輸出：
Maximize number of nodes which are not part of any edge in a Graph are: 6
更新於：2020年8月31日
69 次瀏覽
廣告