C++で航空券のリストから旅程を求めるアルゴリズムを解説

問題の概要

出発空港と到着空港のペア [from, to] で表される航空券のリストが与えられたとします。このとき、すべての航空券を一度ずつ使用して移動する完全な旅程を順番通りに求める必要があります。すべての航空券は、チェンナイから旅を始める一人の旅行者のものであるため、旅程は必ず「Chennai」から始まります。

たとえば、入力が [["Mumbai", "Kolkata"], ["Chennai", "Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", "Delhi"]] の場合、出力は ["Chennai", "Mumbai", "Kolkata", "Delhi", "Bangalore"] となります。

解き方のアプローチ

この問題は、グラフ理論でいうオイラー路(すべての辺=航空券をちょうど一度だけ通る経路)を求める問題です。これには「ヒールホルツァー法(Hierholzer's algorithm)」と呼ばれる古典的なアルゴリズムが有効で、深さ優先探索(DFS)を用いて効率的に解くことができます。手順は以下の通りです。

• 結果を格納する配列 ret と、各空港からの行き先を管理するマップ graph を定義します。
• 空港名を引数に取る visit メソッドを定義します。
• visit メソッド内では、graph[airport](その空港から到達できる空港の一覧)が空になるまで以下を繰り返します。
  • x := graph[airport] の先頭要素を取り出します。
  • graph[airport] から先頭要素を削除します。
  • visit(x) を再帰的に呼び出します。
• ループを抜けたら、現在の空港名を ret に追加します。
• メインの処理では、まずすべてのチケットについて u := tickets[i][0]、v := tickets[i][1] とし、v を graph[u] に挿入していきます。
• 旅程の起点となる visit("Chennai") を呼び出します。
• 最後に ret を逆順に並べ替えて返します。

行き先の格納に multiset を使うことで、同一区間の重複チケットも正しく扱え、かつ行き先が常に辞書順にソートされた状態で保持されます。また、帰りがけの順(事後順)で空港を記録し、最後に反転させることで、旅程が正しい順序で組み上がります。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        if(i > 0) cout << ", ";
        cout << v[i];
    }
    cout << "]" << endl;
}

class Solution {
    public:
    vector<string> ret;
    map< string, multiset<string> > graph;

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(int i = 0; i < tickets.size(); i++){
            string u = tickets[i][0];
            string v = tickets[i][1];
            graph[u].insert(v);
        }
        visit("Chennai");
        reverse(ret.begin(), ret.end());
        return ret;
    }

    void visit(string airport){
        while(graph[airport].size()){
            string x = *(graph[airport].begin());
            graph[airport].erase(graph[airport].begin());
            visit(x);
        }
        ret.push_back(airport);
    }
};

int main(){
    Solution ob;
    vector<vector<string>> v = {{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}};
    print_vector(ob.findItinerary(v));
    return 0;
}

実行結果

入力

{{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}

出力

[Chennai, Mumbai, Kolkata, Delhi, Bangalore]