C++在网中,一个顶点可能会有若干个邻接点。有的邻接点离该顶点距离近,有的邻接点与该顶点距离远,本题要求实现一个函数,输出某个顶点的最远邻接点的值以及与最远邻接点相关联的边上的权值。
时间: 2024-03-25 19:39:49 浏览: 36
dsf.rar_有向图邻接表_有向邻接表
以下是使用深度优先遍历的 C++ 代码示例:
```c++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
void dfs(unordered_map<int, vector<pair<int, int>>>& graph, int node, int distance, int& max_node, int& max_distance, vector<bool>& visited) {
visited[node] = true;
if (distance > max_distance) {
max_node = node;
max_distance = distance;
}
for (auto& neighbor : graph[node]) {
if (!visited[neighbor.first]) {
dfs(graph, neighbor.first, distance + neighbor.second, max_node, max_distance, visited);
}
}
}
pair<int, int> find_farthest_neighbor(unordered_map<int, vector<pair<int, int>>>& graph, int start) {
vector<bool> visited(graph.size() + 1, false);
int max_node = start;
int max_distance = 0;
dfs(graph, start, 0, max_node, max_distance, visited);
return make_pair(max_node, max_distance);
}
int main() {
unordered_map<int, vector<pair<int, int>>> graph = {
{1, {{2, 10}, {3, 20}, {4, 30}}},
{2, {{1, 10}, {5, 40}}},
{3, {{1, 20}, {4, 50}}},
{4, {{1, 30}, {3, 50}, {5, 60}}},
{5, {{2, 40}, {4, 60}}}
};
int start = 1;
auto result = find_farthest_neighbor(graph, start);
cout << "Farthest neighbor from " << start << ": " << result.first << endl;
cout << "Distance: " << result.second << endl;
return 0;
}
```
其中,`graph` 是邻接表表示的图,`start` 是起始顶点。`dfs` 函数采用深度优先遍历,记录每个顶点到起始顶点的距离,最终距离最远的邻接点即为所求。最后在 `find_farthest_neighbor` 函数中调用 `dfs` 函数,返回距离最远的邻接点和对应的边权值。
阅读全文