最初に「あい」を学ぶことば日本語でプログラミング入門（Mindで定番アルゴリズム： 深さ優先探索 DepthFirstSearch）

はじめに

本記事シリーズは母国語のプログラミング言語が存在するという文化的価値をアピールするためのもので、プログラミング一般の入門を意図するものではありません。とはいっても題材としては定番アルゴリズムのいくつかを疑似言語ではなくコンパイル・実行可能なプログラミング言語の日本語で書いてみようというたてつけとなります。

Mind（マインド）

プログラミング言語Mind（マインド）は自然な日本語で記述できるスタック指向の軽量中間コードコンパイラ言語です。ただし単語間の分かち書きが必須であくまで形式言語です。逆ポーランド記法¹の範囲で分かち書きされた日本語単語の語順が自然と日本語の語順となるという意味の「自然さ」で書くことができ、独自の軽量中間コードのランタイム実行で非常に高速です。実装言語はCまたはMind。初版の登場は1985年で2025年は生誕４０周年となりました。

Mind（マインド）の入手方法

無償版のMind version 8 (windows版linux版)を下記の公式サイトからダウンロードできます。フリーメールでかまいませんのでメールアドレスをご登録くださいませ。

定番アルゴリズム：深さ優先探索（DepthFirstSearch）とは

アルゴリズムは、問題を解決するための手順や計算方法を意味します。アルゴリズムにはいくつかの定番ロジックが存在します。

ここではその中のひとつ「深さ優先探索（DFS）」を扱ってみます。「深さ優先探索」はグラフや木構造を探索するための定番アルゴリズムの一つです。可能な限り深く進み、終端に到達した場合とりあえず一つ戻って別の経路を探索するロジックです。

同様の定番アルゴリズムに「幅優先探索（BFS）」がありますが、それはまた別の記事で取り扱います。

お題のソースコード

今回は下記のような経路を想定します。数字は頂点の番号で４つの頂点があるとします。このロジックでは頂点同士が隣接しているかどうかが問題で、距離などの属性はありません。

  1 --→ 2 --→ 4
   \          ^
    \        /
     +-→ 3 ─+

上記のグラフの頂点間の関係を隣接行列で表現すると下記のようになります。

//F:From T:To
F/T 1 2 3 4
1   0 1 1 0 
2   0 0 0 1 
3   0 0 0 1 
4   0 0 0 0 

Mindの配列の添え字の基数は１から始まりますので、下記のような2次元配列で上記の隣接行列を記述します。

    隣接判定[1,2] = 1;
    隣接判定[1,3] = 1;
    隣接判定[2,4] = 1;
    隣接判定[3,4] = 1;

また、上記の疑似言語表現では一般的なプログラミング言語の配列表現でかぎカッコを使っていますが、Mindの場合はかっこ()表記となります。また、他の組み合わせは０で初期化されているものとします。

depthfirstsearch.src

頂点数最大は　       定数　４頂点。

隣接行列は　構造体
        隣接判定は　変数　　（頂点数最大と　頂点数最大の　変数）
    到達頂点は　頂点数最大の　隣接判定
全体は　頂点数最大の　到達頂点。　

Mindの２次元配列は上記のような構造体定義で宣言されます。

depthfirstsearch.src

隣接行列を初期化するとは （・　→　・）　    本定義
    探索済カウンタを　セットし
    ※1 → 2, 1 → 3, 2 → 4, 3 → 4
    隣接判定（１，２）を　セットし
    隣接判定（１，３）を　セットし
    隣接判定（２，４）を　セットし
    隣接判定（３，４）を　セットすること。

前記の２次元配列の初期化処理の疑似言語表現は、Mindの場合上記のようなイメージとなります。探索済カウンタは結果を表示するためのもので、このロジックの本質には無関係です。

下記がソースコード全文となります。仮定義を使ってメインが冒頭に来るようにして、各処理の実装はその後で定義してみました。

depthfirstsearch.src

頂点数最大は　       定数　４頂点。

隣接行列は　構造体
        隣接判定は　変数　　（頂点数最大と　頂点数最大の　変数）
    到達頂点は　頂点数最大の　隣接判定
全体は　頂点数最大の　到達頂点。　

探索済は　頂点数最大の　変数。　
探索順は　頂点数最大の　変数。
探索済カウンタは　      変数。　

隣接行列を初期化するとは （・　→　・）　    仮定義。
隣接行列を表示するとは （・　→　・）　      仮定義。
深さ優先で探索するとは （・　→　・）　      仮定義。
結果を表示するとは （・　→　・）　          仮定義。

メインとは （・　→　・）
    隣接行列を初期化し
    １で　深さ優先で探索し
    隣接行列を表示し
    結果を表示すること。

隣接行列を初期化するとは （・　→　・）　    本定義
    探索済カウンタを　セットし
    ※1 → 2, 1 → 3, 2 → 4, 3 → 4
    隣接判定（１，２）を　セットし
    隣接判定（１，３）を　セットし
    隣接判定（２，４）を　セットし
    隣接判定（３，４）を　セットすること。

深さ優先で探索するとは （頂点No　→　・）　      本定義
        頂点Noは　変数

    頂点Noに　入れ
    探索済（頂点No）を　セットし
    探索順（探索済カウンタ）に　頂点Noを　入れ
    探索済カウンタを　一つ増加し

    頂点数最大で　回数指定し
        隣接判定（頂点No，回数）が　１に　等しい
        かつ　探索済（回数）が　偽？
        ならば
            回数で　深さ優先で探索する
        つぎに
    繰り返すこと。

隣接行列を表示するとは （・　→　・）　    本定義
        頂点No１は　変数
        頂点No２は　変数
    「隣接行列の状態」を　一行表示し
    「F/T 1 2 3 4」を　一行表示し
    頂点No１に　１を　入れ
    頂点数最大で　回数指定し
        頂点No１を　数値表示し　「   」を　表示し
        頂点No２に　１を　入れ
        頂点数最大で　回数指定し
            隣接判定（頂点No１，頂点No２）を　数値表示し
            「 」を　表示し
        
            頂点No２を　一つ増加
        繰り返す
        改行し
        頂点No１を　一つ増加 
    繰り返すこと。

結果を表示するとは （・　→　・）　          本定義
    「深さ優先探索での探索済頂点No順」を　一行表示し
    頂点数最大で　回数指定し
        「探索済頂点No：」を　表示し　探索順（回数）を　数値表示し　改行し
    繰り返すこと。

「深さ優先で探索する」は再帰的に実装されています。DFSは一般的にスタックのデータ構造の例で説明されますが、再帰的に実装していることによりスタックの役割が機能していることになります。

お題のソースコードをコンパイル

では、コンパイルしてみます。Mind8によるコンパイル結果です。

C:\developments\vscode\mind9\algorithm>mind depthfirstsearch file

日本語プログラミング言語 Ｍｉｎｄ Version 8.07 for Windows
          Copyright(C) 1985 Scripts Lab. Inc.
コンパイル中 .. 終了
Coping.. c:\pmind\bin\mindex.exe --> depthfirstsearch.exe

実行結果

実行結果です。

C:\developments\vscode\mind9\algorithm>depthfirstsearch
隣接行列の状態
F/T 1 2 3 4
1   0 1 1 0 
2   0 0 0 1 
3   0 0 0 1 
4   0 0 0 0 
深さ優先探索での探索済頂点No順
探索済頂点No：1
探索済頂点No：2
探索済頂点No：4
探索済頂点No：3

かなり芸のない出力ですが、探索順が出力されました

おわりに

いかがでしたでしょうか？わたしはわが国に母語によるプログラミング言語が存在することを誇りに思っております。言語は文化。こんにちの日本語のポップスやアニメソングなどが海外でそのまま歌われるような近況を鑑みますと、純然たる技術基盤として超強力な米欧発プログラミング言語勢と存在意義を争うこともなく、日本語の文化として海外でも日本語プログラミング言語の愛される日が来るのやもしれません。

1. 演算子を被演算子の中間に記述する中置記法 1 + 2、前に記述する前置記法（ポーランド記法）+ 1 2、後に記述する後置記法（逆ポーランド記法）1 2 +がある。日本語は１と ２を 足す。 ↩