无向图关键点遍历的最小代价：深度优先搜索算法详解

问题描述

给定一张包含 n 个点 m 条边的无向连通图，点标号为 0∼n−1，其中前 c 个点为关键点。每个点有点权 a_i，边有边权 w_e。关键点还额外有一个权值 b_i。

你需要选定一个起点，从起点开始，中间经过至少 t 个关键点（允许重复经过一个关键点，但只统计一次），最后回到起点。起点可以是关键点，也可以不是。可以待在起点不移动，但那样所统计的关键点仅包括起点本身。

规定该方案的代价为 路径长度 + a_起点 + Σb_q (q∈所有被经过的关键点)，如果一个关键点被多次经过也只统计一次。

你需要对 t=1,2,3,…,c 求出最小代价。

注意： 不保证无重边自环。

思路

构建图： 使用邻接表存储图的信息，包括每个点的邻接边以及边权。2. 最短路径预处理： 使用 Dijkstra 算法计算从每个关键点出发到其他所有点的最短路径，并将结果保存在距离数组中。3. 深度优先搜索（DFS）： * 对每个关键点作为起点，进行深度优先搜索。 * 在搜索过程中，记录当前路径长度、经过的关键点数量以及当前所在的节点。 * 当经过的关键点数量达到 t 且回到起点时，更新最小代价。4. 输出结果： 返回存储了不同 t 值对应最小代价的数组。

代码实现 (C++)cpp#include #include #include #include #include

using namespace std;

// 定义边结构体struct Edge { int from; int to; int weight; Edge(int f, int t, int w) : from(f), to(t), weight(w) {}};

// 定义节点结构体struct Node { int weight; int shortestPath; Node(int w) : weight(w), shortestPath(INT_MAX) {}};

// Dijkstra 算法计算最短路径void Dijkstra(int start, int n, vector<vector>& graph, vector& nodes) { vector visited(n, false); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, start)); nodes[start].shortestPath = 0;

while (!pq.empty()) {        int curr = pq.top().second;        pq.pop();        if (visited[curr]) {            continue;        }        visited[curr] = true;

    for (int i = 0; i < graph[curr].size(); ++i) {            Edge& e = graph[curr][i];            int next = e.to;            int weight = e.weight;

        if (nodes[curr].shortestPath + weight < nodes[next].shortestPath) {                nodes[next].shortestPath = nodes[curr].shortestPath + weight;                pq.push(make_pair(nodes[next].shortestPath, next));            }        }    }}

// 深度优先搜索void DFS(int curr, int start, int t, int count, int length, vector<vector>& graph, vector& nodes, vector& costs) { if (count >= t && curr == start) { costs[t - 1] = min(costs[t - 1], length + nodes[start].weight); return; }

for (int i = 0; i < graph[curr].size(); ++i) {        Edge& e = graph[curr][i];        int next = e.to;        int weight = e.weight;

    DFS(next, start, t, count + (next < (int)costs.size() ? 1 : 0), length + weight, graph, nodes, costs);    }}

int main() { int n, m, c; cin >> n >> m >> c;

vector<Node> nodes(n, Node(0));    vector<vector<Edge>> graph(n, vector<Edge>());

for (int i = 0; i < n; ++i) {        cin >> nodes[i].weight;    }

for (int i = 0; i < c; ++i) {        int key;        cin >> key;        nodes[key].weight += nodes[key].weight;     }

for (int i = 0; i < m; ++i) {        int u, v, w;        cin >> u >> v >> w;        graph[u].push_back(Edge(u, v, w));        graph[v].push_back(Edge(v, u, w));    }

for (int i = 0; i < c; ++i) {        Dijkstra(i, n, graph, nodes);    }

vector<int> costs(c, INT_MAX);    for (int i = 0; i < c; ++i) {        DFS(i, i, i + 1, nodes[i].weight, 0, graph, nodes, costs);    }

for (int i = 0; i < c; ++i) {        cout << costs[i] << ' ';    }    cout << endl;

return 0;}

复杂度分析

时间复杂度: O(c * (m + nlogn) + m^c)，其中 c 为关键点数量，n 为节点数量，m 为边数量。Dijkstra 算法的时间复杂度为 O(c * (m + nlogn))，DFS 的时间复杂度最坏情况下为 O(m^c)。* 空间复杂度: O(m + n + c)，其中 m 为边数量，n 为节点数量，c 为关键点数量。主要开销来自于存储图、距离数组以及递归调用栈。

总结

本文介绍了使用深度优先搜索算法解决无向图关键点遍历最小代价问题的方法，并提供了详细的代码实现和复杂度分析。该算法能够有效地解决该问题，但需要注意时间复杂度在极端情况下可能较高