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

DFS+回溯思想 or Hierholzer 算法:Leetcode332:重新安排行程

程序员文章站 2022-04-24 14:07:01
...

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;
    }
};