資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學統計圖中鄰居節點之和最多為 K 的節點數量
介紹
無向圖是計算機科學和圖論中的一個重要組成部分，它表示由邊連線的頂點集合，且邊沒有方向性。與無向圖相關的常見問題之一是統計圖中鄰居節點之和最多為 K 的節點數量。在計算機科學中，圖論領域將處理給定矩陣中元素之間的連線。通常，圖由邊和節點組成。
統計圖中節點的數量
在這種情況下，使用的圖是無向圖。無向圖包含 'N' 個節點、'M' 條邊，需要滿足條件才能獲得最多為 K 的節點計數。下面給出一個包含四個節點的無向圖的常見示例：
示例
鄰接矩陣作為輸入，其中包含四個頂點的值。
1 2 2 3 3 4 4 5
鄰居是來自節點左側或右側的節點。在上述情況下，節點 1 返回鄰居之和為 1，節點 2 返回鄰居之和為 2，節點 3 返回鄰居之和為 3，節點 4 返回鄰居之和為 2，最後節點 5 返回鄰居之和為 1。我們需要檢查節點的和，當鄰居之和小於或等於 K 時。因此，節點 1 是唯一滿足條件的節點，它返回的值為 1。
方法 1：使用遞迴函式計算圖中鄰居節點之和最多為 K 的節點數量的 C 程式碼
鄰接矩陣被初始化為輸入，為了遍歷列表，我們可以使用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 演算法。
演算法
步驟 1 − 將所需的標標頭檔案 stdio 和 stdlib 包含在給定的程式中。
步驟 2 − 使用三個引數定義函式：圖、N 和 K（int 資料型別）。
步驟 3 − 將計數變數初始化為 0，並使用 for 迴圈迭代圖的鄰接列表（從 1 到 N）。
步驟 4 − 邊連線兩個點 A 和 B，它是給定鄰接列表中的相鄰節點。
步驟 5 − 將 sum 變數儲存在名為“sum”的變數中，該變數對給定頂點中的權重或屬性的值求和。
步驟 6 − 檢查條件：如果 sum 值小於或等於 K，則將計數加一。
步驟 7 − 最終輸出包含圖中節點的數量，當鄰居節點之和最多為 K 時。
示例
//The header files are included
#include <stdio.h>
#include <stdlib.h>
// Function defined with three arguments and declared as output
int output(int** graph, int node, int edges) {
//Initializing the variable as 0
int val = 0;
//for loop will iterate through the values
for (int m = 1; m <= node; ++m) {
int sum = 0;
for (int neighbor = 1; neighbor <= node; ++neighbor) {
sum += graph[m][neighbor];
}
//To check for the condition whether the sum value is less than or equal to edges
if (sum <= edges) {
//When equal it is incremented by one
val++;
}
}
return val;
}
// Main function to test the code
int main() {
//Initializing the variables with values
int node = 5, M = 4, edges = 2;
int** graph = (int**)malloc((node+1)*sizeof(int*)); // Indexed from 1 to N
for(int i=0; i<=node; ++i){
graph[i] = (int*)malloc((node+1)*sizeof(int));
for(int j=0; j<=node; ++j){
graph[i][j] = 0;
}
}
// The edges values are declared in the graph
graph[1][2] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[3][2] = 1;
graph[3][4] = 1;
graph[4][3] = 1;
graph[4][5] = 1;
graph[5][4] = 1;
//The function is called recursively with the parameters
int nodeCount = output(graph, node, edges);
printf("The total number of nodes with a sum of neighbors less than or equal to %d:\n%d\n", edges, nodeCount);
return 0;
}
輸出
The total number of nodes with a sum of neighbors less than or equal to 2: 5
結論
使用 C 程式構建程式碼——我們可以使用遞迴函式實現給定無向圖的計數。該函式與三個引數一起遞迴呼叫。條件是透過 pushback 函式以及透過新增使用者給定的值的相鄰元素獲得的。
172 次瀏覽
