数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究打印距离 K 内的所有邻居节点
为了确定是否存在满足给定条件的相关图表，我们可以使用一种基本方法。条件规定图表必须至少有一个具有奇数度的中心节点，并且所有其他中心节点都必须具有偶数度。我们可以通过从单个中心节点开始并逐步添加中心节点并将它们成对连接来创建这样的图表。对于添加的每个未使用的中心节点，我们将其连接到一个现有的中心节点，确保现有的中心节点具有偶数度，而新中心节点具有奇数度。通过继续此过程，直到所有中心节点都已连接，我们可以构建一个满足给定条件的相关图表。
使用的方法
广度优先搜索（BFS）
带有回溯的修改后的深度优先搜索（DFS）
广度优先搜索（BFS）
要打印距离 K 内的所有邻居节点，可以使用广度优先搜索 (BFS) 算法。首先初始化一个队列并将源节点入队。然后，当队列不为空时，出队一个节点，打印它，并将它的未访问邻居节点入队。为每个节点维护一个变量来跟踪它们与源节点的距离。继续遍历图表，直到距离达到 K。这种方法确保节点按层级遍历，从而允许您有效地打印所需距离内的所有节点。
算法
创建一个名为 printNeighborsWithinK 的函数，该函数将图表、源节点和 K 作为参数。
在函数中，初始化一个队列数据结构以存储用于 BFS 遍历的节点。
创建一个布尔数组 visited 来跟踪已访问的节点。最初将所有节点标记为未访问。
将源节点入队并将其标记为已访问。
创建一个变量 currentDistance 并将其设置为 0。
当队列不为空时，执行以下步骤
从队列中出队一个节点并打印它。
将 currentDistance 加 1。
如果 currentDistance 等于 K，则停止遍历。
遍历已出队节点的邻居节点。
如果邻居节点未被访问，则将其标记为已访问，将其入队，并继续遍历。
示例
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void printNeighboursWithinK(vector<vector<int>>& graph, int source, int K) {
int numNodes = graph.size();
vector<bool> visited(numNodes, false);
queue<int> q;
q.push(source);
visited[source] = true;
int currentDistance = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int node = q.front();
q.pop();
cout << node << " ";
if (currentDistance == K) {
continue;
}
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
currentDistance++;
}
}
int main() {
// Example usage
vector<vector<int>> graph = {
{1, 2},
{0, 3, 4},
{0, 5},
{1},
{1, 6},
{2},
{4}
};
int sourceNode = 0;
int distanceK = 2;
printNeighboursWithinK(graph, sourceNode, distanceK);
return 0;
}
输出
0 1 2 3 4 5
带有回溯的修改后的深度优先搜索（DFS）
要打印距离 K 内的所有邻居节点，可以使用带有回溯的修改后的深度优先搜索 (DFS) 算法。从起点开始，我们探索它的邻居并将它们标记为已访问。如果距离小于或等于 K，则打印邻居节点。然后，我们递归地探索未访问的邻居节点，直到达到距离限制。回溯用于回溯到先前的节点并探索其他未访问的邻居节点。这种方法确保打印距离 K 内的所有可到达的邻居节点，同时有效地利用回溯来回溯和探索不同的路径。
算法
初始化一个 visited 数组来跟踪已访问的节点。
定义一个函数 DFS(node, distance)
将当前节点标记为已访问。
如果距离小于或等于 K，则打印节点。
如果距离大于 K，则返回。
对于当前节点的每个邻居
i. 如果邻居节点未被访问，则递归调用 DFS(neighbour, distance + 1)。
将当前节点标记为未访问（回溯）。
从起始节点开始。
调用 DFS(initialNode, 0)。
此算法使用 DFS 探索图表，在我们从一个节点导航到另一个节点时递增距离。每当距离在所需限制 K 内时，我们都会打印节点。该算法有效地回溯以探索不同的路径，并确保打印距离 K 内的所有可到达的邻居节点。
示例
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<bool> visited;
void DFS(int node, int distance, int K) {
visited[node] = true;
if (distance <= K) {
cout << node << " ";
}
if (distance > K) {
return;
}
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
DFS(neighbor, distance + 1, K);
}
}
visited[node] = false; // Backtrack
}
int main() {
int numNodes, numEdges, initialNode, K;
cout << "Enter the number of nodes: ";
cin >> numNodes;
cout << "Enter the number of edges: ";
cin >> numEdges;
graph.resize(numNodes);
visited.resize(numNodes, false);
cout << "Enter the edges (node1 node2): " << endl;
for (int i = 0; i < numEdges; i++) {
int node1, node2;
cin >> node1 >> node2;
graph[node1].push_back(node2);
graph[node2].push_back(node1);
}
cout << "Enter the initial node: ";
cin >> initialNode;
cout << "Enter the distance limit (K): ";
cin >> K;
cout << "Nodes within distance " << K << " from node " << initialNode << ": ";
DFS(initialNode, 0, K);
return 0;
}
输出
Enter the number of nodes: Enter the number of edges: Enter the edges (node1 node2): Enter the initial node: Enter the distance limit (K): Nodes within distance -1812956864 from node 21980:
结论
本文阐明了两种不同的方法来打印图表中距离 K 内的所有邻居节点。第一种方法使用广度优先搜索 (BFS) 算法，而第二种方法使用带有回溯的修改后的深度优先搜索 (DFS) 算法。这两种算法都确保节点按层级遍历，并有效地打印所需距离内的节点。本文包含算法的详细说明以及 C 语言中的示例代码。
99 次浏览
