欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 332. 重新安排行程【有向欧拉图,Hierholzer 算法】

程序员文章站 2022-04-24 12:39:48
...

题目

leetcode 332. 重新安排行程【有向欧拉图,Hierholzer 算法】

题目分析

我们首先把问题简化:
每张机票是有向图中的一个边,要求经过该图每条边一次且仅一次的走法,即求该图的欧拉回路(或欧拉迹),也可以理解为----一笔画。
题目中明确了,该图肯定存在欧拉回路(或欧拉迹)。
对与这种:给出一个有向图,且为欧拉图,求欧拉回路的问题,我们应用Hierholzer 算法。 该算法的大概流程如下:

  1. 选择任一顶点为起点,遍历所有相邻边。
  2. 深度搜索,访问相邻顶点。将经过的边都删除
  3. 如果当前顶点没有相邻边,则将顶点入栈
  4. 栈中的顶点倒序输出,就是从起点出发的欧拉回路。

要注意的是,入栈节点顺序与欧拉回路顺序相反,最后需要倒序输出。算法的具体证明见『图论』入门以及 Hierholzer 算法 ,这个文章的证明很详细,在这里我就不再赘述了,大概分为两部分证明:

  1. 第一个压入栈的节点,要么是欧拉回路中的起点,要么是欧拉迹中不同于起点的另一个奇数度的点,即终点;
  2. 节点压入栈的顺序和欧拉回路中节点倒序遍历的顺序相同。

下面应用该算法,给出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;
	}
};