
7.11
幅優先検索の利用
145
このクエリからわかるとおり、最も頻繁なノンストップフライトの上位 2つは LAX(ロサンジェルス)
とSFO(サンフランシスコ)間のフライトです。これらのフライトがこれほど頻繁だということは、航
空マーケットにおけるこれらの空港の重要性を示しています。2016 年4 月4日号のニューヨークタイム
ズの記事に書かれているとおり、アラスカ航空はバージンアメリカをウェストコーストへの鍵だと見な
しており(http://nyti.ms/2ea1uZR)、バージン航空をアラスカ航空が買収した理由の 1つは、この 2つ
の空港のスロットを獲得することだったのです。グラフだけを見てみてもおもしろくはありませんが、
その中にはビジネス上の強力な知見が潜んでいるのです!
7.11
幅優先検索の利用
幅優先検索(Breadth-First Search = BFS)はGraphFramesの新しいアルゴリズムの 1つで、頂点
の1つの集合から別の集合への最短経路を見つけ出してくれます。このセクションでは、BFSを使って
tripGraph
をトラバースして目的の頂点(空港)と辺(フライト)を見つけることにします。さあ、本
章のデータセットに基づき、都市間の最短の経路を見つけ出してみましょう。ただし、この例では時間
や距離は考慮せず、都市間のホップ数だけを見ていることに注意してください。たとえば、シアトルと
サンフランシスコ間の直接のフライト数は、次のクエリでわかります。
# SEA
と
SFO