leetcode 332. 重新安排行程【有向欧拉图,Hierholzer 算法】
程序员文章站
2022-04-24 12:39:48
...
题目
题目分析
我们首先把问题简化:
每张机票是有向图中的一个边,要求经过该图每条边一次且仅一次的走法,即求该图的欧拉回路(或欧拉迹),也可以理解为----一笔画。
题目中明确了,该图肯定存在欧拉回路(或欧拉迹)。
对与这种:给出一个有向图,且为欧拉图,求欧拉回路的问题,我们应用Hierholzer 算法。 该算法的大概流程如下:
- 选择任一顶点为起点,遍历所有相邻边。
- 深度搜索,访问相邻顶点。将经过的边都删除。
- 如果当前顶点没有相邻边,则将顶点入栈。
- 栈中的顶点倒序输出,就是从起点出发的欧拉回路。
要注意的是,入栈节点顺序与欧拉回路顺序相反,最后需要倒序输出。算法的具体证明见『图论』入门以及 Hierholzer 算法 ,这个文章的证明很详细,在这里我就不再赘述了,大概分为两部分证明:
- 第一个压入栈的节点,要么是欧拉回路中的起点,要么是欧拉迹中不同于起点的另一个奇数度的点,即终点;
- 节点压入栈的顺序和欧拉回路中节点倒序遍历的顺序相同。
下面应用该算法,给出C++代码。
C++代码
class Solution {
public:
vector<string>ret;
unordered_map<string, priority_queue<string,vector<string>,greater<string>> >mp;//<出发地,目的地集合(升序)>
int ticket_nums;
void dfs(string begin) { //出发地,已用票数
while (!mp[begin].empty()) {
string next = mp[begin].top();//取当前队首元素
mp[begin].pop();//遍历该边后,删除该边
dfs(next);
}
//没有出度之后,将该节点压入结果栈
ret.push_back(begin);
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
//保证遍历所有边
ticket_nums = tickets.size();//边的数量!!
for (auto ticket : tickets)
mp[ticket.front()].push(ticket.back());
dfs("JFK");
reverse(ret.begin(), ret.end());//ret中是逆序排列,所以反转
return ret;
}
};