Hierholzer算法的应用

Hierholzer算法的基本过程

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

性质一：如果该图为欧拉图，则栈底的必定为起点。如果该图为半欧拉图，则栈底部存储的是与起点不同的另外一个奇度数顶点。

性质二：如果该图为欧拉图(/半欧拉图)，则栈中的自底到顶第$n$个顶点就是欧拉回路(/欧拉路径)上的第$n$个顶点。

问题一：LeetCode-332 重新安排行程

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。

示例 1:

1 2	输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] 输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2:

1
2
3

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

代码实现与注释

//声明全局变量
vector<string> ans;
unordered_map<string, map<string, int>> adjGraph;//构造邻接图，类似情况均可采用此数据结构
vector<vector<string>> tickets;//边的存在情况
//深度优先遍历
void dfs(string from){
  //遍历起点的所有边
  for(auto& [to,num]: adjGraph[from]){
    if(num <= 0) continue;//此时边不存在
    num--;
    dfs(to);//深度搜索下个顶点的所有边
  }
  ans.push_back(from);//最后才确定这条边是否可用
}
//主函数
vector<string> FindInternart(vector<vector<string>>& _tickets){
  tickets = _tickets;
  //构造邻接图
  for(auto& ticket: tickets){
    adjGraph[ticket[0]][ticket[1]]++;
  }
  dfs("JFK");
  //根据算法本质，是逆向推断，故需在最后反向处理
  reverse(ans.begin(), ans.end());
  return ans;
}

问题二：LeetCode-753 破解保险箱

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

示例1:

1
2
3

输入: n = 1, k = 2
输出: "01"
说明: "10"也可以打开保险箱。

示例2:

1
2
3

输入: n = 2, k = 2
输出: "00110"
说明: "01100", "10011", "11001" 也能打开保险箱。

提示：

n 的范围是 [1, 4]。
k 的范围是 [1, 10]。
k^n 最大可能为 4096。

Hierholzer算法

Hierholzer算法的应用

Hierholzer算法的基本过程

问题一：LeetCode-332 重新安排行程

问题二：LeetCode-753 破解保险箱

FEATURED TAGS

FRIENDS