資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
