数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告