資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究圖中距離最遠節點的最小值
這裡的目標是從給定的起點確定到整個圖的終點的跳躍次數最少的路徑。可以使用多種方法計算此距離，包括專門為圖遍歷設計的那些方法（如廣度優先搜尋）和最短路徑發現方法（如 Dijkstra 演算法）。
使用的方法
廣度優先搜尋
Dijkstra 演算法
廣度優先搜尋方法
使用廣度優先搜尋演算法遍歷所有圖頂點。在繼續下一階段之前，先訪問源節點的所有鄰居。在無權圖中，BFS 確定最短路徑。透過對每個節點應用 BFS 並測量每個節點與最遠節點之間的最大距離，我們可以獲得最小的圖距離。
演算法
初始化最大距離陣列和 BFS 遍歷佇列。
將初始節點入隊，距離為 0。
出隊第一個節點。
如果與出隊節點相鄰的節點尚未訪問，則將該節點入隊，將其標記為已訪問，並將其距離更新為當前節點的距離加一。
遍歷圖後，找到距離陣列中的最大值。
最遠節點的最小距離就是最大距離。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include<bits/stdc++.h>
// Function to perform Breadth-First Search (BFS)
int bfs(const std::vector<std::vector<int>>& graph, int start) {
int numVertices = graph.size();
std::vector<bool> visited(numVertices, false);
std::vector<int> distance(numVertices, std::numeric_limits<int>::max());
std::queue<int> q;
q.push(start);
visited[start] = true;
distance[start] = 0;
while (!q.empty()) {
int currNode = q.front();
q.pop();
for (int neighbor : graph[currNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
distance[neighbor] = distance[currNode] + 1;
q.push(neighbor);
}
}
}
int maxDistance = *std::max_element(distance.begin(), distance.end());
return maxDistance;
}
// Function to find the minimum value of the distance of the farthest node using BFS approach
int findMinimumDistanceBFS(const std::vector<std::vector<int>>& graph) {
int numVertices = graph.size();
int minDistance = std::numeric_limits<int>::max();
for (int i = 0; i < numVertices; ++i) {
int maxDistance = bfs(graph, i);
minDistance = std::min(minDistance, maxDistance);
}
return minDistance;
}
int main() {
// Example usage
int numVertices = 6;
std::vector<std::vector<int>> graph(numVertices);
std::vector<std::vector<std::pair<int, int>>> weightedGraph(numVertices);
// Add edges to the graph
graph[0] = {1, 2};
graph[1] = {0, 2, 3};
graph[2] = {0, 1, 4};
graph[3] = {1};
graph[4] = {2, 5};
graph[5] = {4};
// Add weighted edges to the weighted graph
weightedGraph[0] = {{1, 1}, {2, 2}};
weightedGraph[1] = {{0, 1}, {2, 1}, {3, 1}};
weightedGraph[2] = {{0, 2}, {1, 1}, {4, 1}};
weightedGraph[3] = {{1, 1}};
weightedGraph[4] = {{2, 1}, {5, 2}};
weightedGraph[5] = {{4, 2}};
int minDistanceBFS = findMinimumDistanceBFS(graph);
std::cout << "Minimum value of distance of the farthest node using BFS: " << minDistanceBFS << std::endl;
return 0;
}
輸出
Minimum value of distance of the farthest node using BFS: 2
Dijkstra 演算法方法
在加權網路中查詢源節點和所有其他節點之間的最短路徑是圖遍歷技術（如 Dijkstra 演算法）的常見任務。它重複選擇最接近的節點並更新其鄰居的距離。Dijkstra 方法透過使用優先順序佇列有效地選擇距離最小的下一個節點來確保最佳距離。我們可以透過從每個圖節點執行 Dijkstra 方法並取最大距離來獲得最遠節點的最小距離。
演算法
Dijkstra 方法需要一個最大值距離陣列和優先順序佇列。
將起始節點及其距離 0 放入優先順序佇列。
出隊優先順序佇列中最接近的節點。
如果出隊節點尚未訪問，則將其標記為已訪問，如果其鄰居的距離更小，則調整其鄰居的距離。
遍歷圖後，找到距離陣列中的最大值。
最遠節點的最小距離就是最大距離。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include<bits/stdc++.h>
// Function to perform Dijkstra's algorithm
int dijkstra(const std::vector<std::vector<std::pair<int, int>>>& graph, int start) {
int numVertices = graph.size();
std::vector<int> distance(numVertices, std::numeric_limits<int>::max());
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int currNode = pq.top().second;
int currDist = pq.top().first;
pq.pop();
if (currDist > distance[currNode])
continue;
for (auto neighbor : graph[currNode]) {
int neighborNode = neighbor.first;
int neighborDist = neighbor.second;
if (distance[currNode] + neighborDist < distance[neighborNode]) {
distance[neighborNode] = distance[currNode] + neighborDist;
pq.push({distance[neighborNode], neighborNode});
}
}
}
int maxDistance = *std::max_element(distance.begin(), distance.end());
return maxDistance;
}
// Function to find the minimum value of the distance of the farthest node using Dijkstra's algorithm
int findMinimumDistanceDijkstra(const std::vector<std::vector<std::pair<int, int>>>& graph) {
int numVertices = graph.size();
int minDistance = std::numeric_limits<int>::max();
for (int i = 0; i < numVertices; ++i) {
int maxDistance = dijkstra(graph, i);
minDistance = std::min(minDistance, maxDistance);
}
return minDistance;
}
int main() {
// Example usage
int numVertices = 6;
std::vector<std::vector<int>> graph(numVertices);
std::vector<std::vector<std::pair<int, int>>> weightedGraph(numVertices);
// Add edges to the graph
graph[0] = {1, 2};
graph[1] = {0, 2, 3};
graph[2] = {0, 1, 4};
graph[3] = {1};
graph[4] = {2, 5};
graph[5] = {4};
// Add weighted edges to the weighted graph
weightedGraph[0] = {{1, 1}, {2, 2}};
weightedGraph[1] = {{0, 1}, {2, 1}, {3, 1}};
weightedGraph[2] = {{0, 2}, {1, 1}, {4, 1}};
weightedGraph[3] = {{1, 1}};
weightedGraph[4] = {{2, 1}, {5, 2}};
weightedGraph[5] = {{4, 2}};
int minDistanceDijkstra = findMinimumDistanceDijkstra(weightedGraph);
std::cout << "Minimum value of distance of the farthest node using Dijkstra's algorithm: " << minDistanceDijkstra << std::endl;
return 0;
}
輸出
Minimum value of distance of the farthest node using Dijkstra's algorithm: 3
結論
總之，網路中最遠節點的最小距離提供了對其範圍和覆蓋範圍的洞察。這個最小值有助於我們理解圖的結構、連通性和具有較大距離的重要節點或位置。我們討論了多種查詢最遠節點最小距離的方法。廣度優先搜尋 (BFS) 透過遍歷圖來查詢每個節點到其他每個節點的最大距離。使用 Dijkstra 方法，我們可以透過確定單個源節點的最大距離來獲得到最遠節點的最小距離。
更新於：2023年7月14日
273 次瀏覽
廣告