擬似言語のグラフ・経路探索の読み方｜隣接する節点をたどる手順

グラフの問題が出ると、二次元配列の0と1を見た瞬間に頭が止まってしまう。

図なら分かるのに、表になった途端に読めなくなっていませんか？

大丈夫です。グラフの問題は、行と列の意味さえ決めてしまえば、あとは配列を1マスずつ読むだけの作業になります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。駅や拠点のつながりを扱う機能や、画面同士の遷移をチェックする仕組みなど、実務でもつながりをデータで表して処理する場面は意外と多くあります。

そのとき最初にやるのは、いつも同じです。どの行がどこからのつながりで、どの列がどこへのつながりなのかを紙に書き出すことでした。

この記事では、文法の解説ではなく、グラフを表す配列の読み方と、隣接する節点をたどって経路を求める手順を、擬似言語のコードとトレース表で確かめていきます。

科目B全体の中でアルゴリズムがどう問われるのかを先に押さえておきたい人は、親記事から読むと位置づけがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

グラフとは何か¶

まずは、グラフという言葉の意味から確認しましょう。ここでいうグラフは、棒グラフや折れ線グラフのことではありません。

点と点を線でつないだ図のことを、アルゴリズムの世界ではグラフと呼びます。駅と路線、人と人の友達関係、ページとリンクなど、つながりを持つものは何でもグラフで表せます。

グラフの問題でよく出てくる用語を、先に表で整理しておきます。

この中で特に大事なのは、有向か無向か、そして重みがあるかどうかの2点です。この2つで、配列の読み方がはっきり変わります。

木とグラフの違い¶

二分木を学んだ人は、木もグラフの一種だと考えてかまいません。木は、ぐるっと回って元に戻れる道がなく、親から子へ一方向に広がる特別なグラフです。

一般のグラフには、そうした制限がありません。1周して元の節点に戻れる道があるので、同じ節点を二度数えない工夫が必要になります。

隣接行列の読み方¶

擬似言語でグラフを扱うとき、多いのが二次元配列でつながりを表す方法です。これを隣接行列と呼びます。

節点 i と節点 j が辺でつながっていれば adj[i, j] に 1、つながっていなければ 0 を入れます。二次元配列の添字の読み方があいまいな人は、行と列の数え方を先に確かめておくと安心です。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

無向グラフの隣接行列¶

例として、節点 1 から 4 までの無向グラフを考えます。1 と 2、1 と 3、2 と 4、3 と 4 がつながっているとします。

これを隣接行列にすると、次のようになります。行が出発側、列が相手側の節点です。

左上から右下への斜めの線を境に、左右が鏡のように同じ形になっていますね。無向グラフでは 1 から 2 へ行けるなら 2 から 1 へも行けるので、adj[1, 2] と adj[2, 1] が必ず同じ値になります。

ある節点の隣を知りたいときは、その節点の行を左から右へ読みます。行2を読むと列1と列4が 1 なので、節点 2 の隣は 1 と 4 だと分かります。

有向グラフでは行と列の意味が大事になる¶

有向グラフでは、この鏡の形が崩れます。1 から 2 へは行けても、2 から 1 へは行けない、ということが起こるからです。

このとき adj[1, 2] は 1 でも、adj[2, 1] は 0 になります。行が出発、列が到着という約束を問題文で必ず確かめてください。

行を横に読むと、その節点から出ていく辺が分かります。列を縦に読むと、その節点に入ってくる辺が分かります。

隣の数を数えるコード¶

隣接行列を読むコードの基本形を見てみましょう。IPAの公開問題そのものではなく、試験でよく見かける形をもとに作った例です。

大域: 整数型の二次元配列: adj

○整数型: countNext(整数型: v, 整数型: n)
  整数型: j
  整数型: count ← 0
  for (j を 1 から n まで 1 ずつ増やす)
    if (adj[v, j] が 1 と等しい)
      count ← count + 1
    endif
  endfor
  return count

v の行を列1から列n まで順に見て、1 の数を数えています。先ほどの無向グラフで countNext(2, 4) を呼ぶと、戻り値は 2 です。

添字が adj[v, j] なのか adj[j, v] なのかで、有向グラフでは結果が変わります。前者は出ていく辺、後者は入ってくる辺の数です。

隣接する節点をたどって経路を探す¶

隣が分かれば、隣の隣、さらにその隣とたどっていくことで、ある節点から別の節点までの経路を探せます。これが経路探索です。

たどる順番には、近い節点から広がる方法と、一本道で奥まで進む方法があります。この2つの訪問順の違いは、キューと再帰で比べたこちらの記事で詳しく解説しています。

【関連記事】擬似言語で見る幅優先探索と深さ優先探索の違い｜たどる順番を解説

ここでは一歩進んで、辺に重みがあるときの最短経路を考えます。通る辺の本数ではなく、重みの合計が一番小さい道を探す問題です。

例として使う重み付きグラフ¶

節点は 1 から 5 までの5つで、次のように辺がつながっているとします。重みは、たとえば駅と駅の間の所要時間だと考えてください。

節点 1 から 5 へ行く道は何通りもあります。1、2、4、5 と進むと辺は3本で、重みの合計は 8 です。

一方、1、3、2、4、5 と進むと辺は4本に増えますが、重みの合計は 7 です。辺の本数が少ない道が、いつも一番速いとは限らないのです。

ダイクストラ法のコード¶

重み付きグラフの最短経路を求める代表的な方法が、ダイクストラ法です。考え方はシンプルで、まだ確定していない節点のうち、出発点からの距離が一番小さいものを1つずつ確定させていきます。

重みは二次元配列 w に入れ、辺がなければ 0 とします。まだ道が見つかっていない節点の距離には、十分に大きな値 INF を入れておきます。

大域: 整数型の二次元配列: w
大域: 整数型: INF ← 9999

○整数型の配列: shortest(整数型: start, 整数型: n)
  整数型の配列: dist ← {n個の INF}
  論理型の配列: done ← {n個の false}
  整数型: i, j, v, minDist
  dist[start] ← 0
  for (i を 1 から n まで 1 ずつ増やす)
    v ← 0
    minDist ← INF
    for (j を 1 から n まで 1 ずつ増やす)
      if ((done[j] が false と等しい) and (dist[j] < minDist))
        v ← j
        minDist ← dist[j]
      endif
    endfor
    if (v が 0 と等しい)
      return dist
    endif
    done[v] ← true
    for (j を 1 から n まで 1 ずつ増やす)
      if ((w[v, j] > 0) and (dist[v] + w[v, j] < dist[j]))
        dist[j] ← dist[v] + w[v, j]
      endif
    endfor
  endfor
  return dist

長く見えますが、外側の for の中身は2つのブロックに分かれています。前半の for で次に確定させる節点 v を選び、後半の for で v の隣の距離を更新しています。

後半の if は、今わかっている距離より、v を経由したほうが短ければ書き換える、という意味です。ここが経路探索の心臓部なので、声に出して読めるくらいまで慣れておきましょう。

トレース表で距離の変化を追う¶

では、出発点 1 で動かしてみます。外側の for が1周するごとに、確定した節点と、そのあとの dist の中身を書き出していきます。

2周目に注目してください。節点 3 を確定させたとき、3 を経由すると 2 まで 1 + 2 = 3 で行けることが分かり、dist[2] が 4 から 3 に書き換わりました。

3周目も同じです。2 を経由すると 4 まで 3 + 1 = 4 で行けるので、dist[4] が 6 から 4 に縮みました。

最終的に dist[5] は 7 になり、先ほど手で数えた 1、3、2、4、5 の道と一致します。値が小さくなる瞬間を表で見つけられれば、このアルゴリズムは読めたも同然です。

グラフ問題で間違いやすいポイント¶

ここまでの内容を、試験で失点しやすい場面に当てはめて整理します。どれも、表を書いて確かめれば防げるものばかりです。

特に多いのが、一つ目の行と列の取り違えです。無向グラフでは結果が変わらないので気づきにくく、有向グラフの問題でだけ急に間違えるようになります。

私も実務で、画面の遷移元と遷移先を逆に登録してしまい、戻るボタンが意図しない画面へ飛ぶ不具合を出したことがあります。向きのあるつながりは、どちらからどちらへなのかを最初に決めておくことが本当に大切だと実感しました。

二重ループの形に目を慣らす¶

グラフのコードは、ほとんどが for の中に for が入った二重ループの形をしています。外側で節点を選び、内側で全部の相手を1つずつ調べる、という流れです。

この形に慣れていないと、どの変数がどこで動いているのか分からなくなります。二重ループの読み方に不安がある人は、こちらで外側と内側の役割を確かめておきましょう。

【関連記事】擬似言語の多重ループ（入れ子の繰返し）がわからない人へ｜二重forの読み方を解説

初見のグラフ問題への構え方¶

試験では、ダイクストラ法そのものではなく、少し形を変えたグラフの処理が出ることもあります。それでも、読む順番は変わりません。

最初に配列の意味を決め、次に外側のループが何を1つずつ選んでいるかを見て、最後に内側の if で何を書き換えているかを確かめます。この3段階で読めば、知らない名前のアルゴリズムでも落ち着いて追えるはずです。

シミュレーターで動かして確かめる¶

紙の上でトレース表を書けたら、最後は実際に動かして確かめましょう。自分の表と実際の値が一致すれば、理解が本物になります。

Giji Academyの擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行しながら、変数や配列の値が変わる様子を見ることができます。dist の値が小さく書き換わる瞬間を目で見ると、経由したほうが近いという考え方がすっと腹に落ちます。

おすすめは、重みを1つだけ変えて試すことです。たとえば 2 と 3 の間の重みを 2 から 5 に変えると、最短経路がどう変わるかを予想してから動かしてみてください。

予想と結果がずれたら、そこが理解のすき間です。二次元配列や繰返しの講座から始めたい人は、Giji Academyの擬似言語シミュレーターで自分に合う講座を選んでみてください。

グラフ以外に科目Bで出るアルゴリズムも合わせて整理したい人は、型ごとにまとめたこちらの記事から次に学ぶものを決めるのもおすすめです。

【関連記事】擬似言語で押さえるアルゴリズム一覧｜科目Bで出る型を整理して解説

まとめ¶

グラフは、節点と辺でつながりを表したものです。擬似言語では、二次元配列の隣接行列で表されることが多く、行と列の意味を決めれば1マスずつ読めるようになります。

無向グラフの隣接行列は斜めの線を境に左右対称になり、有向グラフでは対称が崩れます。行は出ていく辺、列は入ってくる辺という読み方を、問題文で必ず確かめましょう。

隣接する節点をたどれば、経路を探せます。重み付きグラフの最短経路では、辺の本数ではなく重みの合計で比べ、経由したほうが短ければ距離を書き換える、という動きがダイクストラ法の中心でした。

グラフの問題は、見た目のわりに一つひとつの処理は単純です。表を書きながらゆっくり追えば、必ず読めるようになりますよ。