C++ 中重新排序路线以使所有路径都通往城市零

2025年2月7日 | 阅读8分钟

引言

图论中的一些问题涉及路径的操纵以满足给定的规范。例如，在有向图中重新排序路线，例如零号城市，它指挥所有路径。交通管理和网络路由等实际应用已在本章中得到说明。本文将概述问题陈述、解决方法以及 C++ 实现以实现此重新排序。

问题陈述

给定一个包含 n 个节点和 n-1 条边的有向图作为输入，表示由单向道路连接的城市。目标是重新排列这些道路，使得从每个城市到零号城市只有一条路径，即所有路线都直接或间接通向零号城市。

方法

要解决此问题，我们可以按以下步骤进行：

图表示：使用邻接表表示有向图。
遍历和重排：使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 来遍历图并定位需要重排的道路。
计算重排次数：跟踪确保每条路线都通向零号城市所需的重排次数。

方法 1：暴力法（Brute Force Approach）

暴力法探索所有可能的路线重排，并检查每种重排是否允许所有路径都通向零号城市。

算法

暴力法探索所有可能的路线排列，并检查每种排列是否使所有路径都终结于零号城市。

1. 生成排列

应生成所有连接组合。

2. 构建邻接表

每次排列都会创建一个邻接表，该表显示路线是直接的还是非直接的。
如果边从索引较低的节点流向索引较高的节点，则保持不变。
如果它反向流动，则翻转它并增加重排计数。

3. 检查有效性

可以使用 DFS 或 BFS 方法来确定是否可以从节点 0 到达所有节点。
如果图有效，则记录重排计数；

4. 跟踪最少重排次数

应跟踪所有有效排列中所需的最小重排操作次数。

程序

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
 
using namespace std;
 
bool isValid(vector<vector<int>>& adjList, int n) {
    vector<bool> visited(n, false);
    vector<int> stack;
    stack.push_back(0);
	visited[0] = true;
	
	while (!stack.empty()) {
    	int node = stack.back();
        stack.pop_back();
    	
    	for (int neighbor : adjList[node]) {
        	if (!visited[neighbor]) {
                visited[neighbor] = true;
                stack.push_back(neighbor);
        	}
    	}
	}
	
	for (bool v : visited) {
    	if (!v) return false;
	}
	
	return true;
}
 
int minReorder(int n, vector<vector<int>>& connections) {
    vector<int> indices(connections.size());
	for (int i = 0; i < connections.size(); ++i) {
        indices[i] = i;
	}
	
	int minReorders = INT_MAX;
	
	do {
        vector<vector<int>> adjList(n);
    	int reorderCount = 0;
    	
    	for (int i = 0; i < connections.size(); ++i) {
        	int u = connections[indices[i]][0];
        	int v = connections[indices[i]][1];
        	
        	if (find(adjList[v].begin(), adjList[v].end(), u) != adjList[v].end()) {
                adjList[u].push_back(v);
        	} else {
                adjList[v].push_back(u);
                reorderCount++;
        	}
    	}
    	
    	if (isValid(adjList, n)) {
            minReorders = min(minReorders, reorderCount);
    	}
	} while (next_permutation(indices.begin(), indices.end()));
	
	return minReorders;
}
 
int main() {
	int n = 6;
    vector<vector<int>> connections = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
	
	int result = minReorder(n, connections);
	cout << "Minimum reorders required: " << result << endl;
	
	return 0;
}

输出

Minimum reorders required: 2147483647

说明

1. 图有效性检查 (isValid 函数)

一个函数，它接受一个邻接表并确定列表中描述的图是否具有通向其上所有顶点 0 的路径。
此函数使用深度优先搜索 (DFS) 算法遍历此图，确保所有顶点之后都会被访问。

2. 主函数 (minReorder)

生成所有可能的连接排列，以模拟所有可能的重排。
对于每次排列，构建邻接表并计算所需的重排操作数。
使用 isValid 函数检查构造的图是否有效。
跨所有排列跟踪最小重排计数。

3. 主要执行

定义了节点数和连接数的示例。
调用 minReorder 函数并打印结果。

时间和空间复杂度

时间复杂度：暴力法的时间复杂度为 O((E!)⋅(N+E))，其中 E 是边的数量，N 是节点的数量。这意味着 T = O((E!)⋅(N+E))。

生成所有排列需要 O(E!)
对于每次排列，我们构建邻接表并检查图是否有效，这需要 O(N+E)。

空间复杂度：在空间维度上，我们有 O(N+E) 的空间复杂度来存储邻接表和已访问数组。

方法 2：DFS 方法

1. 图构造

我们使用方向对（原始或反转）构造两个图。

2. DFS 遍历

从节点 0 开始使用队列进行 DFS。
如果当前节点有未访问的邻居，
- 如果边是原始的，则重排计数增加一。
- 将邻居标记为已访问并将其加入队列以供进一步遍历。

程序

#include <iostream>
#include <vector>
#include <unordered_set>
 
using namespace std;
 
void dfs(int node, vector<vector<int>>& graph, vector<vector<int>>& revGraph, vector<bool>& visited, int& reorderCount) {
    visited[node] = true;
	
	for (int neighbor : graph[node]) {
    	if (!visited[neighbor]) {
            reorderCount++;
            dfs(neighbor, graph, revGraph, visited, reorderCount);
    	}
	}
	
	for (int neighbor : revGraph[node]) {
    	if (!visited[neighbor]) {
            dfs(neighbor, graph, revGraph, visited, reorderCount);
    	}
	}
}
 
int minReorder(int n, vector<vector<int>>& connections) {
    vector<vector<int>> graph(n);
    vector<vector<int>> revGraph(n);
	
	for (const auto& conn : connections) {
        graph[conn[0]].push_back(conn[1]);
        revGraph[conn[1]].push_back(conn[0]);
	}
	
    vector<bool> visited(n, false);
	int reorderCount = 0;
	
	dfs(0, graph, revGraph, visited, reorderCount);
	
	return reorderCount;
}
 
int main() {
	int n = 6;
    vector<vector<int>> connections = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
	
	int result = minReorder(n, connections);
	cout << "Minimum reorders required: " << result << endl;
	
	return 0;
}

输出

Minimum reorders required: 3

说明

1. 图的表示

使用了两个邻居节点列表来表示图。
graph：包含原始有向边。
revGraph：表示图的反向，意味着其边是反向的。

2. 深度优先搜索 (DFS)

使用 DFS 方法从节点 0 开始遍历图。
在遍历期间，节点被标记为已访问，以跟踪可达性。

3. 边重排计数

由于 DFS 遍历了整个图，它还计算了需要重排的边的数量，以便所有顶点都可以从顶点 0 到达。
当从节点 u 遍历到 v 时，如果 v 最初无法从 u 到达，则计算边重排。

详细步骤

4. 图构造

根据这些连接，形成了两个邻接表（graph 和 revGraph）。原始边包含在 graph 中，而 revGraph 包含反向边。

5. DFS 遍历

主 DFS 函数从节点 0 开始，并使用 graph 和 revGraph 探索所有可达节点。
在遍历过程中，它会标记节点为已访问，以便在本次操作中每个节点只会被处理一次。

6. 计算订单

当通过 graph 中的边（原始方向）首次访问某个节点时，reorderCount 会增加一。
此计数告诉我们有多少个空位需要填补才能将所有其他节点与节点 0 连接起来。

时间复杂度

图构造：创建原始图和反向图都涉及遍历连接列表，这将花费 O(∣E∣) 时间，其中 E 是边的数量。
DFS 遍历：DFS 函数为每个节点调用一次，以确保所有节点和边都被访问。在最坏情况下，每个节点和边都会被访问一次，时间复杂度为 O(∣V∣+∣E∣)，其中 ∣V∣ 是顶点的数量。
总体：通过同时考虑图的构造和 DFS 遍历，可以得出总时间复杂度为 O(∣V∣+∣E∣)。

空间复杂度

图表示：原始图和反向图的邻接表占用 Ω (| V | + | E |) 空间。
DFS：DFS 的空间复杂度主要取决于递归堆栈，由于递归调用，堆栈可能高达 | V |，此外还需要已访问数组的空间，其大小为 O(V)。
总体：在主要因素方面，这导致空间复杂度由图表示和 DFS 遍历主导，即 Ω(|V|+|E|)。

方法 3：BFS 方法

算法

1. 图构造

使用方向对（原始或反转）构造图。

2. BFS 遍历

使用队列从节点 0 开始 BFS。
对于当前节点的每个邻居，如果它尚未被访问，
- 如果边是原始的，则增加重排计数。
- 将邻居标记为已访问并将其加入队列以供进一步遍历。

程序

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int minReorder(int n, vector<vector<int>>& connections) {
    vector<vector<pair<int, bool>>> graph(n);
	for (const auto& conn : connections) {
        graph[conn[0]].emplace_back(conn[1], true);  // original edge
        graph[conn[1]].emplace_back(conn[0], false); // reversed edge
	}
	
    vector<bool> visited(n, false);
    queue<int> q;
	int reorderCount = 0;
 
	q.push(0);
	visited[0] = true;
 
	while (!q.empty()) {
    	int node = q.front();
    	q.pop();
 
    	for (const auto& [neighbor, isOriginal] : graph[node]) {
        	if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
                if (isOriginal) {
                    reorderCount++;
                }
        	}
    	}
	}
 
	return reorderCount;
}
 
int main() {
	int n = 6;
    vector<vector<int>> connections = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
	
	int result = minReorder(n, connections);
	cout << "Minimum reorders required: " << result << endl;
	
	return 0;
}

输出

Minimum reorders required: 3

说明

1. 图的表示

图由邻接表和一对对邻居节点表示，这些节点具有原始边（true）或反向边（false）。

2. 广度优先搜索 (BFS)

可以使用 BFS 遍历图。在实现方面，这种方法通常比 DFS 更易于迭代实现。
在这种情况下，队列数据结构用于组织要访问的节点。
当节点被推入队列时，节点会被标记为已访问，这样就不需要重复执行了。

3. 跟踪重排次数

例如，当 BFS 遍历期间由于原始边而发生重排计数时，如前所述，它将具有另一个对应项，以便跟踪重排。
这确保每个节点不会被计算多次，因为我们只处理未访问的邻居。

时间复杂度

上述讨论的优化解决方案时间复杂度可以这样分析：

1. 图构造

构建图时会考虑所有连接，因此其顺序由 O(E) 给出，其中 E 代表边的数量（连接）。

2. BFS 遍历

最坏情况是我们处理图中的每个节点和每条边。o 时间复杂度为 O(V+E)，其中 V 是顶点的数量（节点），E 是边的数量，这表示访问所有节点并测试连接到它们的每条边。

通过合并这些步骤，总时间复杂度变为 O(V+E)。

空间复杂度

优化解决方案的空间复杂度包括：

1. 图的表示

邻接表表示一个图。对于每个节点，它存储其邻居以及它们之间的边是否存在，即原始或反向类型的边，这会带来 O(V+E) 的空间使用。

2. 已访问数组

为了跟踪已访问的节点，我们使用了一个布尔数组 visited[V]。这需要 O(V) 的空间。

3. BFS 队列

在某些情况下，BFS 遍历的同一级别上的所有节点都可能保留在队列中；因此，它需要在任何给定时间点容纳最多 V 个元素，从而需要 O(V) 的空间。

将这些结合起来，总空间复杂度为 O(V+E)。

总结

时间复杂度：O(V+E)
空间复杂度：O(V+E)

结论

总之，这个经典的图问题有很多实际应用，例如您想更改有向图中的路线，以便所有路径都返回到像零这样的特定城市。为了得出答案，我们应该构建相应的图，通过 DFS 探索它，并计算这些排列，例如——某些路径改变方向，而另一些则不。

下一主题二进制迷宫中的最短路径

C++ 中重新排序路线以使所有路径都通往城市零

引言

问题陈述

方法

方法 1：暴力法（Brute Force Approach）

算法

程序

输出

说明

时间和空间复杂度

方法 2：DFS 方法

1. 图构造

2. DFS 遍历

程序

输出

说明

详细步骤

时间复杂度

空间复杂度

方法 3：BFS 方法

算法

1. 图构造

2. BFS 遍历

程序

输出

说明

时间复杂度

空间复杂度

总结

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

C++ 中重新排序路线以使所有路径都通往城市零

引言

问题陈述

方法

方法 1：暴力法（Brute Force Approach）

算法

程序

输出

说明

时间和空间复杂度

方法 2：DFS 方法

1. 图构造

2. DFS 遍历

程序

输出

说明

详细步骤

时间复杂度

空间复杂度

方法 3：BFS 方法

算法

1. 图构造

2. BFS 遍历

程序

输出

说明

时间复杂度

空间复杂度

总结

结论

相关帖子

数组中每个元素左边大于或等于它的最近元素

k 路归并排序

双向归并排序

不同的栈操作类型

如何知道一个数组是否是双峰的

归并排序的递归关系

设计和实现特殊栈数据结构

循环双向链表的应用、优点和缺点

滚入迷宫的球