資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究根據每個節點的元件大小構建圖
簡介
圖論是計算機科學中的一個基礎領域，它使我們能夠研究和視覺化物件或實體之間的關係。分析圖的一個重要方面是瞭解網路中元件或連線子圖的大小。在本文中，我們將探討如何使用 C++ 程式碼根據每個節點的元件大小構建圖。在圖論中，元件是指任何連線的子圖，其中該子圖內的任意兩個頂點之間都存在某種路徑。它有助於描繪整個圖結構中相互連線的節點的叢集或組。
根據每個節點的元件大小構建圖
在構建元件大小分佈圖之前，讓我們簡要了解一下鄰接表——一種在 C++ 等程式語言中表示圖的常用方法。鄰接表透過儲存每個頂點的鄰居資訊來表示節點之間的連線。
建立鄰接表表示
定義一個名為 Graph 的結構體，其中包含“值”和“鄰居”等屬性。
建立一個 Node 結構體的陣列（或向量）；其索引表示節點標籤或識別符號。
對於連線兩個頂點 A 和 B 的每條邊，在陣列或向量中各自對應的位置下將 A 和 B 作為鄰居新增。
查詢連通分量
現在我們已經使用鄰接表結構表示了我們的圖，我們可以透過深度優先搜尋 (DFS) 遞迴地查詢每個節點的連通分量。
將所有節點初始化為未訪問狀態。
遍歷每個未訪問的節點。
當透過 DFS 探索從一個節點遍歷到另一個節點時，檢查它們是否已被訪問。
如果尚未訪問，則將其標記為已訪問，並繼續對其鄰居進行 DFS 探索，直到沒有更多未訪問的鄰居為止。
在 DFS 遍歷期間訪問新發現的節點時，增加計數變數。
儲存每個單獨起始節點的連通分量計數。
用於根據每個節點的元件大小構建圖的 C++ 程式碼
演算法
步驟 1 - 包含所需的標標頭檔案。
步驟 2 - 建立一個帶有 ID 和鄰居向量的類 Graph。
步驟 3 - 建立一個函式 outputgraph()，它接收一對向量 components 和一個整數 n。
步驟 4 - 建立一個無序對映 mp 來儲存元件。
步驟 5 - 迴圈遍歷元件並將它們新增到對映中。
步驟 6 - 透過檢查每個元件中的節點數量是否可被元件的大小整除來檢查輸入是否有效。
步驟 7 - 在給定的程式碼中，可能存在兩個無法執行程式碼的可能性。
步驟 8 - 第一種情況是輸入本身錯誤，另一種情況是無法從輸入對形成邊。
步驟 9 - 可以藉助給定的元件大小和對的輸入來構建圖的邊。
示例
//Including the required header files
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Graph {
public:
// unique identifier for each node
// stores neighbor IDs
int id;
vector<int> neighbors;
Graph() { }
void addNeighbor(int neighborID) {
neighbors.push_back(neighborID);
}
};
//Defining the function with three parameters
//The parameters are the input pairs, their address of it, and the size
void outputgraph(vector<pair<int, int>> &components, int n) {
unordered_map<int, vector<int>> mp;
for (int m = 0; m < n; m++)//O(n) {
mp[components[m].second].push_back(components[m].first);
}
bool noEdgesExist = true;
for (auto a : mp)//O(n) {
int component_size, num_nodes;
component_size = a.first;
num_nodes = a.second.size();
if (component_size != 1)
noEdgesExist = false;
if (num_nodes % component_size != 0) {
cout << "Valid Graph cannot be constructed\n";
return;
}
}
//If the edges could not be constructed using the given pairs this statement gets executed
if (noEdgesExist){
cout << "Edges cannot be constructed for this possible graph\n";
return;
}
vector<pair<int, int>> edges;
for (auto a : mp){
vector<int> nodes = a.second;
int component_size = a.first;
// divide the nodes into groups of size= component_size
int numGroups = nodes.size() / component_size;
for (int m = 0; m < numGroups; m++){
int start = m * component_size;
for (int y = start + 1; y < start + component_size; y++){
edges.push_back({nodes[y], nodes[y - 1]});
}
}
}
//for loop will iterate through the pairs
for (int m = 0; m < edges.size(); m++){
cout << edges[m].first << ", "
<< edges[m].second;
if (m != edges.size() - 1){
cout << ", ";
}
}
}
//main function to test the implemented functions
int main() {
//component size is initialized as 2
int n = 2;
vector<pair<int, int>> components{{1,2}, {2,2}, {3,1}, {4,1}, {5,1}, {6,1}};
outputgraph(components, n);
return 0;
}
輸出
2,1
結論
該程式碼執行並根據輸入對和元件大小使用類方法以及布林功能給出邊對。透過本文中的詳細描述和提供的 C++ 實現示例，我們現在可以解決涉及構建圖的類似問題。
146 次檢視
