DFS+回溯思想 or Hierholzer 算法:Leetcode332:重新安排行程
DFS+回溯思想 or Hierholzer 算法:Leetcode332:重新安排行程
问题:
思路:
DFS+回溯思想:
使用map保存邻接表,由于map是基于键值自动排序的,所以解决了要输出自然排序最小的行程组合的问题
map的键类型为string,而值类型不使用vector< string >而是使用map<string,int>,用int保存机票的数量,因为输入中可能出现相同的机票
DFS函数的作用是找到以参数start为起点的满足条件的路径,找到返回TRUE,否则返回FALSE。向DFS函数传参count,count表示已遍历的边数,若所有边均遍历,则DFS返回TRUE。
在路径中添加DFS当前正在访问的节点,已遍历的边数加1,对该节点的邻接表中的元素进行访问,进入循环:
在循环中,机票的数量充当了经典DFS中visited数组的作用,若机票数<=0,则证明该机票已被访问过,跳过该次访问,每次访问将其机票数减1,对该元素调用DFS函数,若返回TRUE,则当前DFS也返回TRUE,证明已找到路径。若返回FALSE,证明须回溯,将该元素的机票数+1,即还原
若遍历完所有该节点邻接表中的元素后,仍未找到路径,则在路径中删除该节点,返回FALSE
在主函数中进行邻接表的建立,并调用DFS函数,注意传递的参数count=-1,这样在最开始访问起点后,count即为0,表示已遍历的边数为0。
在代码中注意基于范围的For循环中,由于要修改元素,应使用for( auto& [ airport,number ] : adjtable[start] )
,使用&对容器进行遍历
Hierholzer 算法:
Hierholzer 算法描述见欧拉图、欧拉路径、Hierholzer 算法
Hierholzer算法就是证明了一点:当存在欧拉路径时,从合理的起始点无脑dfs遍历,得到的路径一定是欧拉路径。
因为题目规定了一定有欧拉路径,并且起点一定是JFK(所以这个起始点一定是合理的),所以根据Hierholzer算法,可以无脑dfs。
在DFS函数中对节点的邻居进行无脑DFS遍历,遍历过的边进行标记,当遍历完所有相邻节点后(对该节点邻接表中的元素调用DFS函数),当前节点没有可遍历的相邻边,根据Hierholzer 算法的思想,此时该节点在路径中,将其加入路径。
最后将得到的路径逆序输出即可
代码:
DFS+回溯思想:
class Solution {
public:
typedef unordered_map< string,map<string,int> > table;
int edge_num;
vector<string> ans;
bool dfs( table& adjtable,int count,string start )
{
ans.push_back( start );
count++;
if( count==edge_num )
return true;
for( auto& [ airport,number ] : adjtable[start] )
{
if( number<=0 )
continue;
number--;
if( dfs( adjtable,count,airport ) )
return true;
number++;
}
ans.pop_back();
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
table adjtable;
for( auto temp:tickets )
{
if( adjtable.find( temp[0] )==adjtable.end() )
adjtable[ temp[0] ]=map<string,int>();
if( adjtable[ temp[0] ].find( temp[1] )==adjtable[ temp[0] ].end() )
adjtable[ temp[0] ][ temp[1] ]=0;
adjtable[ temp[0] ][ temp[1] ]++;
}
edge_num=tickets.size();
dfs( adjtable,-1,"JFK" );
return ans;
}
};
Hierholzer 算法:
class Solution {
public:
typedef unordered_map< string,map<string,int> > table;
vector<string> ans;
void dfs( table& adjtable,string start )
{
for( auto& [ airport,number ] : adjtable[start] )
{
if( number<=0 )
continue;
number--;
dfs( adjtable,airport );
}
ans.push_back( start );
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
table adjtable;
for( auto temp:tickets )
{
if( adjtable.find( temp[0] )==adjtable.end() )
adjtable[ temp[0] ]=map<string,int>();
if( adjtable[ temp[0] ].find( temp[1] )==adjtable[ temp[0] ].end() )
adjtable[ temp[0] ][ temp[1] ]=0;
adjtable[ temp[0] ][ temp[1] ]++;
}
dfs( adjtable,"JFK" );
reverse( ans.begin(),ans.end() );
return ans;
}
};
上一篇: TIME_WAIT状态解读
下一篇: DT时代,什么样的程序员最好找工作?