資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究列印節點具有最大度和最小度
在圖論的概念中，節點的度數是連線它的邊的總數。查詢圖中度數最高和最低的節點可以揭示有關網路連線和結構的重要資訊。在本文中，我們將使用 CPP 演算法探討三種解決此問題的方法。我們將介紹每種方法的演算法，提供相關的程式碼示例，並展示每種方法的獨特結果。
使用的方法
暴力方法
優先佇列
鄰接表
暴力法
暴力法涉及在遍歷所有節點時計算網路中每個節點的度數。當我們遇到具有更高或更低度數的節點時，我們會更新具有最高和最低度數的節點。
演算法
在演算法中，使用最高和最低度數以及相關節點初始化引數。
迭代遍歷圖中的每個節點。
確定每個節點的度數，並將其與現有的最高和最低度數進行比較。
示例
#include <iostream>
#include <vector>
using namespace std;
void printNodesWithMaxMinDegrees(const vector<vector<int>>& graph) {
int numVertices = graph.size();
int maxDegree = 0;
int minDegree = numVertices + 1;
vector<int> nodesWithMaxDegree;
vector<int> nodesWithMinDegree;
for (int i = 0; i < numVertices; i++) {
int degree = 0;
for (int j = 0; j < numVertices; j++) {
if (graph[i][j] == 1) {
degree++;
}
}
if (degree > maxDegree) {
maxDegree = degree;
nodesWithMaxDegree.clear();
nodesWithMaxDegree.push_back(i);
} else if (degree == maxDegree) {
nodesWithMaxDegree.push_back(i);
}
if (degree < minDegree) {
minDegree = degree;
nodesWithMinDegree.clear();
nodesWithMinDegree.push_back(i);
} else if (degree == minDegree) {
nodesWithMinDegree.push_back(i);
}
}
// Print nodes with maximum degree
cout << "Nodes with maximum degree (" << maxDegree << "): ";
for (int node : nodesWithMaxDegree) {
cout << node << " ";
}
cout << endl;
// Print nodes with minimum degree
cout << "Nodes with minimum degree (" << minDegree << "): ";
for (int node : nodesWithMinDegree) {
cout << node << " ";
}
cout << endl;
}
int main() {
// Create a graph represented by an adjacency matrix
vector<vector<int>> graph = {
{0, 1, 1, 1, 0},
{1, 0, 0, 1, 0},
{1, 0, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 0, 1, 0, 0}
};
// Call the printNodesWithMaxMinDegrees function
printNodesWithMaxMinDegrees(graph);
return 0;
}
輸出
Nodes with maximum degree (3): 0 Nodes with minimum degree (1): 4
優先佇列
第三種方法涉及使用優先佇列輕鬆找到具有最高和最低度數的節點。將每個節點的度數新增到優先佇列後，優先佇列預設按非遞增順序保持度數的順序。
演算法
建立一個優先佇列，並將所有節點的度數放入其中。
將所有節點的度數新增到最高優先順序佇列中。
要獲取具有最低度數的節點，請移除最高元素。
要獲取具有最高度數的節點，請移除最低元素。
示例
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
vector<vector<int>> adjacencyMatrix;
public:
Graph(const vector<vector<int>>& adjMatrix) : adjacencyMatrix(adjMatrix) {}
int getNumVertices() const {
return adjacencyMatrix.size();
}
int getDegree(int vertex) const {
int degree = 0;
for (int i = 0; i < adjacencyMatrix.size(); i++) {
if (adjacencyMatrix[vertex][i] == 1) {
degree++;
}
}
return degree;
}
};
void printNodesWithMaxMinDegrees(Graph graph) {
int numVertices = graph.getNumVertices();
priority_queue<int, vector<int>, greater<int>> pq;
// Insert degrees of nodes into priority queue
for (int i = 0; i < numVertices; i++) {
pq.push(graph.getDegree(i));
}
// Node with minimum degree
int minDegreeNode = pq.top();
pq.pop();
// Node with maximum degree
int maxDegreeNode;
while (!pq.empty()) {
maxDegreeNode = pq.top();
pq.pop();
}
// Print nodes with minimum and maximum degrees
cout << "Node with minimum degree: " << minDegreeNode << endl;
cout << "Node with maximum degree: " << maxDegreeNode << endl;
}
int main() {
// Create an example adjacency matrix
vector<vector<int>> adjacencyMatrix = {
{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0}
};
// Create a Graph object and call the printNodesWithMaxMinDegrees function
Graph graph(adjacencyMatrix);
printNodesWithMaxMinDegrees(graph);
return 0;
}
輸出
Node with minimum degree: 2 Node with maximum degree: 3
鄰接表
第四種方法涉及構建一個鄰接列表來表示圖。當我們遍歷鄰接列表時，會記錄具有最低和最高度數的節點。
演算法
使用以下演算法建立圖的鄰接列表表示。
設定引數以儲存最高和最低度數以及相關節點。
透過迭代遍歷鄰接列表來確定每個節點的度數。
根據需要更新節點、最高和最低度數。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Graph {
private:
vector<vector<int>> adjacencyList;
public:
Graph(const vector<vector<int>>& adjList) : adjacencyList(adjList) {}
int getNumVertices() const {
return adjacencyList.size();
}
const vector<vector<int>>& getAdjacencyList() const {
return adjacencyList;
}
};
void printNodesWithMaxMinDegrees(Graph graph) {
int numVertices = graph.getNumVertices();
vector<int> degrees(numVertices);
const vector<vector<int>>& adjacencyList = graph.getAdjacencyList();
// Calculate degrees of nodes
for (int i = 0; i < numVertices; i++) {
degrees[i] = adjacencyList[i].size();
}
// Find node with minimum degree
int minDegreeNode = min_element(degrees.begin(), degrees.end()) - degrees.begin();
// Find node with maximum degree
int maxDegreeNode = max_element(degrees.begin(), degrees.end()) - degrees.begin();
// Print nodes with minimum and maximum degrees
cout << "Node with minimum degree: " << minDegreeNode << endl;
cout << "Node with maximum degree: " << maxDegreeNode << endl;
}
int main() {
// Create an example adjacency list
vector<vector<int>> adjacencyList = {
{1, 2},
{0, 2, 3},
{0, 1, 3},
{1, 2}
};
// Create a Graph object and call the printNodesWithMaxMinDegrees function
Graph graph(adjacencyList);
printNodesWithMaxMinDegrees(graph);
return 0;
}
輸出
Node with minimum degree: 0 Node with maximum degree: 1
結論
在這篇博文中，我們探討了三種不同的方法，利用 CPP 演算法生成具有最高和最低度數的節點。從暴力迭代到更有效的方法，例如使用優先佇列和建立鄰接列表，每種方法都提供了獨特的方法。這些方法使識別對圖連線至關重要的節點變得容易。根據圖的大小和結構，特定方法在效率和複雜性方面可能優於其他方法。最終，要使用的方法取決於當前問題的具體需求。
更新於: 2023-07-14
97 次瀏覽
廣告