アルゴリズム演習のためのグラフ理論ライブラリ
松下 浩明*

Graph Theory Programming Library for Use in Exercises of Graph Algorithms
Hiroaki MATSUSHITA*

Abstract
We have developed a library for graph theory to use by lessons or exercises. This programlibrary has comparatively simple structures so that we can master it in a short time. Thislibrary has the function of editing graphs in order to make creation of graph data easy.
Moreover, this library has the functions in which graph data can be saved to files, be inputtedfrom files and draw Graphs. We can describe intelligibly the Graph search functions, such as
depth first search, using this library. As a result of our using this library by lessons, we
confirmed that the opinions obtained were for the most part positive.
Keywords : Graph Theory，Programming，Library，Graph Algorithm

グラフのアルゴリズムを実際にプログラミン

１．まえがきグ言語で表現する場合，一からグラフのデータ構
グラフ理論のグラフは頂点集合とそれらを結 造を構築するには大変な労力を要する．限られたぶ辺集合で定義されるものである．グラフを用い 講義時間や演習時間のなかでそれを行うのは得ると都市間の交通網やインターネットの通信網， 策でない．そのため，グラフの基本的操作を用意
人と人の関係，作業工程表などさまざまな現実問 したグラフ理論ライブラリを利用する価値が生
題が厳密にモデル化できるため，グラフは工学上 じる．
有用な概念である 1)．

代表的なグラフ理論ライブラリとして，C++言情報工学や情報科学のカリキュラムの中では， 語上で動作する Boost Graph Library や LEDA，「データ構造とアルゴリズム」や「情報数学」な Java 言語上で動作する JGraphT がある 4)〜6)．
どの科目で，グラフ上のアルゴリズムの観点から Boost Graph Library は機能が豊富でさまざまな講義される場合が多い 2)．また，中学生を対象と 実現法に対応しているため，実用性の高いライブしたグラフ理論の講義例もある 3)．
ラリである．LEDA はグラフ理論，計算幾何を含グラフのアルゴリズムを講義するとき，二つの方 む広範囲のライブラリである．記述しやすく，実法がある．一つは理論的見地に沿って講義する方 用，教育の両面に対応している．JGraphT はグラ法であり，数学的素養を養う．もう一つは実際に フ理論の操作に特化し，比較的単純な構造をもつ
プログラミングを行い，創造的素養を養う方法で ライブラリであるため，理解しやすい．
ある．

一方，演習でグラフ理論ライブラリを使用する
工業系大学や高等専門学校など，実践的高度専 場合，Boost Graph Library に代表される従来の門技術者の養成を目的とする学校では，理論的素 グラフ理論ライブラリでは十分でない．最初の問
養を基礎にして，プログラミングなどの演習に力 題点はライブラリで用意すべき関数の揃え方に点を置く．
ついてである．
深さ優先探索の応用として，関節点問題を解く*香川高等専門学校詫間キャンパス情報工学科

アルゴリズムの演習を考えてみる．関節点アルゴ

159

香川高等専門学校研究紀要 5(2014)

リズムは複数存在するので，効率的ではないが理 き，プログラムの誤りがアルゴリズムに起因する
解しやすいアルゴリズムから理解しにくいが効 のか，入力データに起因するのか，学習者にとっ率的なアルゴリズムへと授業展開を進めるのが て判断が難しい．
妥当であろう．そのとき，プログラミングの複雑

従来のライブラリにおける第３の問題点はア

さも易しいものから難しいものへ連なっている ルゴリズムの途中結果を表示しないことである．
と都合がよい．しかし，従来のグラフ理論ライブ
ラリを用いるとそのようにならない．

学習者はアルゴリズムを理解するために，アル
ゴリズムの最終実行結果のみならず，アルゴリズ

Boost Graph Library や JGraphT では visitor ムの途中の実行結果も知りたい．しかし，従来のやそれと類似な概念を導入し，深さ優先探索をど ライブラリではアルゴリズムの最終結果しか知のような使い方にも対応できるようにしている りえない．
9)．この汎用性は教育上の使用においてはむしろ

このような状況のもとで，グラフアルゴリズム

欠点になる．授業展開上，先に教える理解しやす の演習に利用可能な教育用グラフ理論ライブラ
いアルゴリズムのコーディングがあまり簡単に リを開発した 10)．本グラフ理論ライブラリはプ
ログラミング言語 C#および Java から呼び出し可

ならないからである．

関数の揃え方についてのもう一つの観点は，入 能なライブラリであり，上記問題点を次のように出力関数と描画関数である．グラフの入出力関数 解決している．
や描画関数はグラフアルゴリズムの学習を容易 (1)

単純な構造

グラフの内部構造を頂点，辺間の隣接リストでにさせるために必要である．従来のグラフ理論ライブラリは入出力関数や描画関数を別のライブ 実現するものだけに限定した．このことにより，
ラリやライブラリ利用者に委ねている．これは頂 短い授業時間内でも習得できるよう比較的単純
点，辺への付加データを含むグラフデータの入出 な構造をもたせることができた．
力関数や描画関数を汎用的に記述する難しさに (2)

学習項目に対応した関数群

汎用的な１個の関数を用意するのでなく，学習起因している．

従来のライブラリにおける第２の問題点はプ 項目に対応した複数の関数群を用意した．
たとえば，深さ優先探索に関しては先行順の頂

ログラム誤りの見つけやすさに関するものである．頂点や辺の削除について考えてみる．繰り返 点列を戻す関数，後行順の頂点列を戻す関数，深し構文の中で，何も考慮せず削除を行うと実行時 さ優先探索木を戻す関数，先行順，後行順の入り
エラーになる 9)．これは削除により，グラフの内 混じった頂点，辺列を戻す関数，汎用的な深さ優
部データ構造が変化し，その結果繰り返しが正し 先探索関数を用意し，学習段階に応じて適切に関く行われなくなったためである．このエラーへの 数を使い分けできるようにした．
対処法は既知であり，ライブラリの使用に慣れた (3)
利用者はこのエラーを回避するプログラムをつ

グラフエディタと入出力関数

グラフデータは原理的には頂点間の隣接行列くることができる．しかし，授業の学習者にとっ で表現できる 7)．しかし，隣接行列で表現されたては余分な注意をしなければならなくなり，学習 グラフデータは誤りやすく，また，データの内容
者の注意が学習の本来の流れからずれることに を判別するのが困難である．そこでグラフデータの作成を容易にするために，さまざまなグラフエ

なる．

プログラム誤りの見つけやすさはグラフクラ ディタが開発されている 8)．本論文でも，本グラスの揃え方にも関係する．連結グラフというグラ フ理論ライブラリを用いてグラフエディタを開
フクラスは学習上よく現れるクラスである．しか 発した．また，グラフエディタで作成したグラフ
し，従来のライブラリでは無向グラフや単純グラ データを入出力する関数を用意した．
フなどのクラスは用意されているが，接続関係で (4)アルゴリズムの動作確認を容易にするために，特徴づけられる連結グラフというクラスは用意されていない．

描画関数

描画関数を用意した．このことにより，アルゴリ

学習者が連結グラフに対するアルゴリズムの ズムの実行途中や実行終了時のグラフの様子を演習を行うとき，入力グラフに誤って非連結グラ 視覚的に見ることができる．
フを用いることは起こり得ることである．そのと (5)160グラフクラス

松下浩明 : アルゴリズム演習のためのグラフ理論ライブラリ

汎用的なグラフクラスのほか，学習でよく使わ ゴリズムの扱うデータより高いため，プログラミれるグラフクラスを 11 種類用意した．これらの ングをより困難なものにしている．
グラフクラスを用いることにより，グラフデータ

グラフアルゴリズムを題材として，アルゴリズの誤りに起因したプログラムエラーを減少させ ム演習を構成するとき，演習の展開方法としては，ることができる．

アルゴリズムの理解向上を目的に展開する方法(6)とアルゴリズムの設計能力向上を目的に展開すアルゴリズムの途中動作の確認

アルゴリズムの途中まで実行できる関数群を る方法が考えられる．
用意した．これにより，アルゴリズムの最終結果 (1) アルゴリズムの理解向上を目的とする演習のみならず，途中の実行結果を得ることができる． アルゴリズムの理解向上を目的とする演習のまた，これらの関数群をグラフエディタに組込む 授業展開例を表１に示す．分節１では学習者にアことにより，アルゴリズムのステップごとの動作 ルゴリズムを説明し，教師が例題を解く．分節２を見ることができる．

では教師があらかじめ用意したグラフに対し，学(7)

習者に机上で課題を解かせる．分節３ではコンピ

頂点，辺データの拡張性

ライブラリを利用して応用プログラムを作成 ュータを用いて課題のグラフデータを作成する．
するとき，頂点，辺に付加データが必要な場合が 分節４ではコンピュータによる動作シミュレー
ある．本グラフ理論ライブラリでは，頂点，辺に ションを行い，分節２で学習者が解いた解と一致
付加データを容易につけることができる．また， するか調べさせる．グラフが複雑な場合や授業時
付加データつきのグラフの入出力を行うことが 間が短い場合はグラフデータを教師があらかじできる．

め用意することにより，分節３を省略してもよい．

グラフアルゴリズムの題材の代表例の１つで本論文では，2.でアルゴリズム演習，特にグラフ
アルゴリズム演習の目標と方法について述べる． ある最小木問題では，プリムのアルゴリズムとク
3.で本グラフ理論ライブラリの基本的な構成と ラスカルのアルゴリズムの２つのアルゴリズム
機能を述べる．4.で本グラフ理論ライブラリによるグラフアルゴリズム演習の支援例について述べる．5.でグラフ理論ライブラリを実際の授業に適用した実施例とその評価について述べる．

があるので，分節２から文節４を２回繰り返すことになる．このような授業展開を実施するためにはまず，グラフデータを容易に作成できることが必要である．次にアルゴリズムの最終的な実行結果ばかりでなく，アルゴリズムの途中の実行結果

2．アルゴリズム演習の目標と方法がステップごとに確認できなければならない．
(2)

アルゴリズムの設計能力向上を目的とする

コンピュータプログラムのアルゴリズムの題

演習

材としては，ソーティングアルゴリズムとグラフ

アルゴリズムの設計能力向上を目的とする演
アルゴリズムがよく取り上げられている 2)．これ 習の授業展開例を表２に示す．分節１では学習者らのアルゴリズムは時間計算量の解析など，理論 にアルゴリズムを箇条書きレベルの疑似コード的側面を教授する場合が多いが，実際にプログラ で説明する．この疑似コードは自然言語に近いもムを組み，その動作を実地に理解することも大切 のとする．また，アルゴリズムとは関連づけずにである．特に高等専門学校などの実践的高度専門 疑似コードとプログラミングコードの対応関係
技術者を養成することを目的とする学校におい を説明する．分節２では学習者に机上でプログラては，アルゴリズム演習によって，アルゴリズム ム記述を行わせる．分節３では学習者がコンピュ
設計能力，アルゴリズムに沿ったプログラミング
能力，検査能力を涵養することが目標になる．

表1

授業展開１

ところで，ソーティングアルゴリズムは，それ分節をプログラミングする場合，配列や再帰プログラ1

アルゴリズムの説明

一斉

ミングなどプログラミングの基礎を理解してお2

実行課題の解答

個別（机上）

れば，おおかた用が足りる．

3

グラフデータの作成

個別（PC）

4

動作シミュレーション

個別（PC）

一方，グラフアルゴリズムでは，グラフ，頂点，辺など，扱うデータの抽象度がソーティングアル

161

授業内容

授業形態

香川高等専門学校研究紀要 5(2014)

表2
分節

授業展開２

授業内容

授業形態

1

アルゴリズムの説明

一斉

2

作成課題の解答

個別（机上）

3

グラフデータの作成

個別（PC）

4

プログラミング

個別（PC）(a) Graphータを用いて，テストデータとして適切なグラフ

static void Main(string[] args)

データを作成する．分節４ではコンピュータ上で{プログラムコードの入力とコンパイル作業を行Graph<Vertex, Edge> G =わせ，エラーを訂正する．分節４において，アルnew Graph<Vertex, Edge>();

ゴリズムと直接関係ないコード部分についてはVertex v1 = G.NewVertex("v1");

あらかじめ学習者に知らせておく．

Vertex v2 = G.NewVertex("v2");

このような授業展開を実施するためにはまず，Vertex v3 = G.NewVertex("v3");

グラフデータはアルゴリズムが前提としたデー

v1.X = 100; v1.Y =タであるか否かを容易に検査できる必要がある．

v2.X =

また，グラフ，頂点，辺などのグラフオブジェク

50; v2.Y = 150;

v3.X = 150; v3.Y = 150;

トが容易に作成できなければならない．さらに，Edge e1 = G.NewEdge(v1, v2);

アルゴリズムが正しく動いていることを知るた

Edge e2 = G.NewEdge(v1, v3);

めにアルゴリズムの動作を直感的に把握できな}ければならない．
3.

50;(b) Program

グラフ理論ライブラリの構成と機能

図1

グラフの構築本 グ ラ フ 理 論 ラ イ ブ ラ リ に は C# 言 語 版 とJava 言語版の２種類があるが，本論文の説明は 有向辺を構築するには G.NewDiEdge(v1, v2)を用いる．図１(a)のグラフを構築するプログラムを
主に C# 言語版で行う．
本グラフ理論ライブラリはループ，多重辺をも 図１(b)に示す．
つ擬グラフを扱う．また，無向辺と有向辺がまじ
3.2

った混合グラフを扱う．

グラフ，頂点，辺の基本操作

グラフ，頂点，辺の基本操作関数にはグラフへ
3.1の頂点，辺の挿入，グラフからの頂点，辺の削除，グラフ，頂点，辺の構築

グラフの型は Graph<V, E> である．ここで V 頂点，辺がグラフに含まれているか否かの判定がは頂点の型を表すパラメータである．頂点の基底 ある．
また，グラフ内の全頂点，全辺の参照は

クラス BaseVertex とインタフェース IVertex を継承している．E は辺を表すパラメータで，頂点 G.Vertices() ， G.Edges() で 行 う ． そ れ ぞ れと同様な継承関係がある．頂点，辺の既定の型と List<V>，List<E>型である．また，G.VertexCount，
G.EdgeCount で全頂点の総数，全辺の総数を表す．

して Vertex，Edge を用意している．
グラフ，頂点，辺に共通の属性には名前，位置，重みがある．また，辺のみに存在する属性として， 3.3 削除操作を含む処理の繰り返し処理
グラフに属する全頂点，全辺を対象とした繰り
２つの端点および無向辺か有向辺かを示すタグ
返し処理において，各処理のなかに削除操作を行がある．

グ ラ フ G に 新 た な 頂 点 を 構 築 す る に は ， う場合，プログラムの記述に特別な方法が必要でG.NewVertex()を用いる．G に頂点 v1 と v2 を結 あり，学習者に過多な注意をしいる．
グラフのなかから孤立点（他のどの頂点とも隣ぶ無向辺を構築するには G.NewEdge(v1, v2)を，接していない頂点）を削除する処理を例に取り，

162

松下浩明 : アルゴリズム演習のためのグラフ理論ライブラリforreach (Edge e in G.E
EdgesOf(v))){te(v);
Vertex w = e.Opposit}(a) Graph
図3
グラフ
フ G の孤立点を取り除くア
アルゴリズム

隣接頂点
点の参照

がら
ら，このようななプログラムムコーディン
ング上の注(1) グ
グラフ G を入入力する

意事
事項は煩雑でああり，また，，実行時エララーが起き(2) グ
グラフ G の各頂点 v に対ししたととき，その原因因が分かりににくく，学習習者に余分

v の次数がが 0 ならばな負負担をしいるこことになる．
．

G から v を削除する

本グ
グラフ理論ライイブラリでは
は，グラフのの内部デー
タ構
構造を直接アク
クセスして，，全頂点，全辺をたど(b) Pseudo Progrram

る G.EachVerex，G.
，G.EachEdge
ge 関数と，全全頂点，全辺ののコピーを作り，このコピ
ピー上の頂点点，辺をた
stat
tic void Ma
ain(string[] args)

どる
る G.Vertices，G.Edges 関関数を用意しし，前者を{応用用プログラム作
作成用，後者
者を学習用にに提供した．
raph<Vertex, Edge> G =Gr

学習
習者は後者を用用いることににより，アルルゴリズム

h<Vertex, Edge>();E
new Graphの理理解に集中できるようにしした．

G.Input("graph.dat");fo
oreach (Vertex v

3.4

in
n G.EachVerrtex) {

接続辺，隣隣接頂点の参参照

頂 点 v に 接続 す る 辺 集 合 を 参 照す る に は

if (G.Deg
greeOf(v) ==
= 0)

G.Ed
EdgesOf(v)を用用いる．G.Ed
EdgesOf(v)のの値はそれG.Remove(v);

ぞれれ List<E>型でである．またた，G.EdgeCoountOf(v)}で頂頂点 v に接続
続する辺集合のの総数を表すす．v が辺}e の端点であるとの端とき，e.Oppo
posite(v)で辺辺 e のもう一
一つの端点を表表す．図２にに頂点 v から
ら，接続辺を経経由して隣接頂点を参照す
するプログ ラムを示(c) Pseudo Progrram
図2

孤孤立点の削除
除処理

す．
．

説明する
る．図２(a)ののグラフにおおいて，頂点 v4 が 3.5
孤立点で
である．

グラフの入
入出力

グラフのファ
グ
ァイルからの入の入力はファ
ァイル名を孤立点
点を削除する
る処理は，グララフの全頂点
点をた 入力力ダイアログ
グで指定する
る関数とファァイル名おどっていいき，頂点のの次数が 0 なら
らば，それをを削除 よびびパスを文字列列で指定する
る関数がある
る．本グラする方法
法になる．図図２(b)に疑似似言語による
る孤立 フ理理論ライブラリの Java 版
版では，イン
ンターネッ
点削除処
処理を示す．
．図２(c)は本
本グラフ理論論ライ ト上
上での利用を考考えて，ユニニフォームリリソースロ
ブラリをを用いて，コ
コード化したものである．
．この ケーータを指定できる関数も用用意しているる．
プ ロ グ ラ ム は 実 行 時 エ ラ ー を 起 こ す ． BBoost

グラフ
グ
G のフ
ファイルへのの出力はファ
ァイル名をGraph Li
Library や JGraphT
JGを用い
いて，同様ののプロ 出力力ダイアログ
グで指定する
る関数とファ
ァイル名おグラムをを作成してもも，やはり実行
行時エラーをを起こ よびびパスを文字列列で指定する
る関数で行うう．
す．
その理
理由はグラフフの全頂点をを対象としたた繰り 3.6
返し処理
理の中で，グラフの内部デ
データ構造を
を変更

グラフの描
描画

グラフの描画グはグラフィ
ィックスを指定定して描したためめである．ここのような処理理においてはは，全 画すする関数が基本本である．そそのほか，基準点を指頂点のココピーを作成成し，コピーさされた頂点にに対し，定すする描画関数やや頂点，辺のの色，大きささなどを指繰り返しし処理を行わ
わなければな
ならない．しかかしな 定でできる描画関数数がある．

163

香川高等専門学校研究紀要 5(2014)4.

アルルゴリズム演演習の支援例

ゴリズムのゴi ステップ後のスの実行状態に
になる．
図５(a)
図
は最小
小木問題を解を解くプリムの
のアルゴ

4.1

グ
グラフデータのの作成支援

リズ
ズムの２ステップ目の実行
行表示であるる．頂点集

グラフ
フデータは頂頂点間の隣接接関係を表現現する 合 {v1}{から出出る重み最小 の辺 (v1, v2)
v
を最
隣接行列
列や，頂点と辺と辺間の接続関関係を表現すする接 小木
木の辺として選選び，次に頂頂点集合 {v1v1, v2} か
続行列でで表現するこことができる
る．しかし，ググラフ ら出出る重み最小の辺 (v1,, vv3) を最小木
木の辺と
がすこし
し大きくなる
ると間違いやすくなる．

してて選んだところろである．

グラフ
フデータの作作成のためにに，グラフエデ
ディタ

図５(b)
図
はク
クラスカルの アルゴリズ ムの２スを用意す
すると便利でである．グラフ
フデータの作作成支 テッ
ップ目の実行表表示である．
．全体の辺ののうち，重援のためめに，本グラ
ラフ理論ライブ
ブラリを用いいて作 み最最小の辺 (v1,
1, v2) を選び
び，次に２番目に重み成したグ
グラフエディ
ィタを用意しした．グラフエエディ が小小さい辺 (v3,
3, v4) を選んんだところでである．
タは本グ
グラフ理論ラライブラリ用
用のグラフを作を作成，編集するることができきる．

このようにステこ
テップごとのの動作を表示
示すれば，
学習
習者は個々ののアルゴリズ ムの動作ばか
かりでな

方眼紙
紙や地図を下下敷きにするる下絵機能にによっ く，，異なるアルゴ
異ゴリズムの動動作の違いををたやすくて，規則
則的なグラフやフや地図情報ににもとづいたたグラ 理解
解することがでできる．ステテップごとのの動作シミ
フの作成成が容易であある．また，ラランダムグララフを ュレレーションは現
現在，深さ優優先探索や最小木問題，
自動生成
成する．図４にグラフエデ
ディタの外観観を示 最短短経路問題，巡回セールス巡
スマン問題な
などで実現
す．
4.2

され
れている．
ア
アルゴリズムのの動作シミュ
ュレーションン

4.3

アルゴ
ゴリズムの動動作を理解するには，ステテップごとの動動作シミュレレーションが有有効である．
．

深さ優先探探索学習へのの支援

深さ優先探索深索はグラフ内のの頂点や辺を
を接続関係ににしたがって探探索する基本本的方法でああり，グラグラフ
フエディタにには下方にトトラックバー
ーがつフア
アルゴリズムムの題材の代表表例の１つでである．

いておりり，アルゴリ
リズムを選択すすれば，エデディタ
で編集中
中のグラフにに対し，動作シ
シミュレーシションを行うこことができるる．
トラッ
ックバーのス
スライダを左左端に合わせる
ると，全実行がが行われる．２番目の目盛
盛りにスライ
イダを合わせる
るとアルゴリ
リズムの実行
行前の状態になになる．
2 + i番
番目の目盛りりにスライダをを合わせるととアル(a) Prim Allgorithm(bb) Kruskal Allgorithm
図4

グラフエディ
ィタ

図5

164

アルゴリ
リズムの動作作シミュレーーション

松下浩明 : アルゴリズム演習のためのグラフ理論ライブラリ

それに基づいたさまざまなアルゴリズムが提案されている．深さ優先探索を用いるとさまざまな角度から議論を展開できるため，アルゴリズム演
習の題材としては適している．
深さ優先探索の学習は大きく２つに分かれる．
１つ目は深さ優先探索アルゴリズムの学習であり，２つ目は深さ優先探索を応用したアルゴリズ
ムの学習である．
(a) Graph
4.3.1

深さ優先探索アルゴリズムの学習

static Graph<Vertex, Edge> G =深さ優先探索アルゴリズムの学習では，深さ優

new Graph<Vertex, Edge>();

先探索の概念の学習と深さ優先探索の実現法のstatic List<Vertex> preorder =学習が行われる．前者は表１の授業展開１で，後者は表２の授業展開２で教授する．深さ優先探索

new List<Vertex>();
Dictionary<Vertex,

staticbool>の実現法には再帰を用いる方法とスタックを用いる方法がある．

visit = new

図 6(b) は本グラフ理論ライブラリを用いて，Dictionary<Vertex, bool>();static void Main(string[] args)

深さ優先探索を再帰法で実現した１例である．図{６(a) のグラフに対し，図６(c) の出力が得られG.Input("graph.dat");る．
このように，本グラフ理論ライブラリを用いれVertex start =G.GetVertex("v4");
foreach (Vertex v

ば，深さ優先探索の実現法を実際にプログラミン
グして確かめることができる．

in G.Vertices)
visit[v] = false;

4.3.2

深さ優先探索を応用したアルゴリズムの学習

DFS(start);

深さ優先探索を応用したアルゴリズムとして}
static void DFS(Vertex v)

は，無向グラフの連結成分を求めるアルゴリズム，{

無向グラフの関節点を求めるアルゴリズム，無閉
visit[v] = true;

路有向グラフに対するトポロジカルソートアル

preorder.Add(v);ゴリズムなどがある．
ここでは，無向グラフの関節点を求めるアルゴ

foreach (Edge ein G.EdgesOf(v)) {Vertex w = e.Opposite(v);リズムを例にとり，本グラフ理論ライブラリを用いた学習支援法を述べる．
グラフの関節点とは，グラフからその頂点とそ

if (!visit[w]) DFS(w);の頂点に接続する辺を取り除いたとき，グラフの}連結成分の個数が増加する頂点のことである．図}６(a) のグラフでは頂点 v3，v7 が関節点である．
(b) Algorithm

関節点を求めるアルゴリズムは３つ考えられる．
定義に基づいた方法，深さ優先探索の性質に基づ

v4 v3 v2 v1 v6 v7 v5 v8 v9 v10 v11 v12 v13(c) Output
図6

いた方法，効率のよい方法である．それらを関節
点アルゴリズム１，２，３と呼ぶことにする．表３に関節点アルゴリズムの授業展開例を示す．

深さ優先探索アルゴリズム

165

香川高等専門学校研究紀要 5(2014)

表3

授業展開３

分節

授業内容

1

関節アルゴリズム１の説

頂点 v がグラフ G の関節点か否か判定する
授業形態

アルゴリズム 1

一斉(1) v が孤立点ならば，偽を戻す

明(2) グラフ G のコピーH をつくる

2

作成課題１ を解く

個別（机上）

3

グラフデータの作成

個別（PC）(4) H から v を削除する

4

プログラミング１

個別（PC）(5) w から G および H 内を深さ優先探索でた

5関節アルゴリズム２の説

一斉(3) v に隣接する頂点のひとつを w とする

どり，それぞれの連結成分 C(G)，C(H)を

明

求める

6

作成課題２ を解く

個別（机上）

7

プログラミング２

個別（PC）

ければ偽を戻す．

8

関節アルゴリズム３の説

一斉

そうでなければ，真を戻す(6) C(G) の頂点数 ‑ 1 が C(H) の頂点数と等し明9

作成課題３ を解く

個別（机上）

10

プログラミング３

個別（PC）

図7

関節点アルゴリズム１

頂点 v がグラフ G の関節点か否か判定する(1)

定義に基づいた方法とそれに対する学習支

アルゴリズム 2援(1) v を開始点として G を深さ優先探索し，定義に基づいた方法では，グラフから頂点を取

探索木 T を得る

り除き，連結成分の個数が増えるかどうか調べる． (2) T において，v の次数が 2 以上ならば関節点，
図 7 にそのアルゴリズムを示す．
そうでなければ関節点でないと判断する
本グラフ理論ライブラリでは，連結成分を調べ

図8るために深さ優先探索関数 G.VerticesDFS(v) が関節点アルゴリズム２用意されている．G.VerticesDFS(v) は頂点 v に連結している頂点を深さ優先探索でたどり，そのグラフ G のすべての関節点を求める

頂点列を戻す．

アルゴリズム 3(2)(1) 深さ優先探索を行い，探索番号，探索木情報，

探索木に基づいた方法とそれに対する学習支援

辺の種類情報を得る

探索木に基づいた方法では，頂点 v を開始点と(2) G の各頂点 v に対し，low[v] を計算する

した深さ優先探索木を構成し，探索木における頂(3) G の頂点 root が関節点か否かを，

点 v の次数が２以上ならば頂点 v は関節点，そう

アルゴリズム 2 を用いて調べる

でなければ関節点でないと判定する．図 8 に探索(4) G の root 以外の各頂点 v については，

木に基づいたアルゴリズムを示す．

v の子 w で， low[w] ≧ v の探索番号 なる

本グラフ理論ライブラリには，探索木を構成すw が存在すれば，v は関節点である

るのに深さ優先探索関数 G.GraphDFS(v) が用意

図9

されている．G.GraphDFS(v) は頂点 v に連結している頂点を深さ優先探索でたどり，その探索木を戻す．
(3)

退辺である任意の頂点(c) low[z]，ただし，z は v の任意の子

効率のよい方法とそれに対する学習支援

効率のよい方法では，グラフ G の各頂点 v に対し，次に定義する値 low[v] を深さ優先探索順に計算し，関節点か否か調べる．

関節点アルゴリズム３

ここで，探索番号は深さ優先探索を行った順に１からつけた番号である．図 9 に効率のよいアルゴリズムを示す．
効率のよいアルゴリズムでは，各頂点の探索番

low[v] の定義

号や各辺が探索木を構成する辺か，後退辺かを知
low[v] は次の (a)〜(c) のうちの最小値である．
る必要がある．
(a) v の探索番号
本グラフ理論ライブラリには，探索番号やグラ(b) w の探索番号，ただし，w は辺 (v，w) が後

166

松下浩明 : アルゴリズム演習のためのグラフ理論ライブラリ

フ の 辺 の 種 類 を 調 べ る 深 さ 優 先 探 索 関 数 構築
築子で行われ，，その変換時時に，グラフフの制約がG.ResulltDFS(v) が用用意されていいる．

満た
たされているかか否かが検査査される．学習者は検学
査済済みの入力グララフに対し，，アルゴリズ
ズムを作成

グ
グラフのクラススとアルゴリ
リズム作成支支援

4.4する
る．このことににより，学習習者はアルゴ
ゴリズムのグラフ
フアルゴリズ
ズムが入力すするグラフはは連結 誤りりにのみ起因因したエラー
ーに対処する ことがで
グラフでであるとか無無閉路グラフフであるとかか制約 きるる．
条件のつついている場場合が多い．ところがアル
と
ルゴリ
ズム演習
習で入力グララフを学習者
者に個々に作
作成さ 4.5
せると，，制約条件に反反するグラフフを作成する
ること
がある．
．

付加データ
タと応用プロログラム作成支支援

グラフ理論ラグ
ライブラリを少を少し規模の大大きい応用ププログラムの作作成に利用ししようとする
ると，頂点

アルゴ
ゴリズム演習習において，作成したプロ作
ログラ や辺辺に付加データ
タを加えるこことが必要にになる．
ムをデババッグするととき，生じたエ
エラーがアルルゴリ

本グラフ理論ラ本
ライブラリで
では，頂点にに付加デーズムの誤誤りにのみにに起因する場合
合は，学習者
者は比 タ を 付 け 加 え る 場 合 ， 頂 点 の 基 底 ク ラ ス
較的容易易にエラーにに対処できる
る．しかし，入入力グ Base
seVertex およよび頂点インンタフェースス IVertex
ラフが制
制約条件に反反している場合
合，学習者ががエラ からら継承したクララスを定義しし，そのクララスのメン
ーの原因因をつかむののは難しい．

バ変
変数として，付
付加データをを定義する．
．また，辺

このよ
ような状況をを回避するたために，本グララフ理 に付
付加データを付付け加える場場合，辺の基底クラス
論ライブ
ブラリではささまざまな制
制約条件をももつグ Base
seEdge<V>およよび辺インタタフェース IE
Edge から
ラフのククラスをあららかじめ定義している．表
表４に 継承承したクラスをを定義し，そそのクラスののメンバ変本グラフ
フ理論ライブ
ブラリで用意意されているるグラ 数ととして，付加デ
データを定義義する．
フのクララスを示す．
．

AVertex,AVAEdg
dge が BaseVe
Vertex，IVer
ertex およ本グラ
ラフ理論ライ
イブラリで扱
扱うグラフののクラ び BaseEdge<V>，
Ba，IEdge からら継承したク
クラスであスは二分分類される．
．ひとつは GraphGrで，もうう一方 るととき，AVertex
ex, AEdge ははメンバ関数として，は ImmuutableGraph およびそれか
おから継承されれたク 引数
数のない構築子
子，付加デーータを頂点，，辺に設定
ラスであある．Graph はすべての基は基本操作を実実行す するる関数，頂点，，辺上の付加加データを文字列に変ることがができる．Im
ImmutableGraraph は基本操
操作の 換すする関数を定義
義しなければばならない．
．本グラフ
うち，頂頂点，辺の追追加，削除を実実行することとがで 理論
論ライブラリははこれらの関関数を用いて
て，付加デ
きない．
．

ータ
タのついたグララフのファイ
イル入出力をを行う．

Graphh から制約条
条件のあるググラフへの変換
換は

図 10 に付加デデータを用いいた応用プロログラムの例をを示す．このププログラムはは京都市内の
の観光ルー

表4

グラフのク
クラス

グラ
ラフクラス

意

味

Graph

混
混合，擬グララフ

ImmutabtableGraph

混
混合，擬グララフ

Pseudog
ograph

無無向，擬グララフ

Multigigraph無無向，多重ググラフ

MixedGGraph

混混合，単純ググラフ

SimpleG
leGraph無無向，単純ググラフ

DirectetedGraph

有有向，単純ググラフ

ConnecctedGraph

無無向，単純，，連結グラフBlock

無無向，単純，
２重連結グララフDag

有有向，単純，，無閉路グラフフ

Forest無無向，単純，，無閉路グラフフTree

無無向，単純，連連結，無閉路ググラ

ト検検索プログラムムである．学
学生が卒業研究として作成成したものであ
ある．

フ

図 10
1

167

応用プロ
ログラム

香川高等専門学校研究紀要 5(2014)

5.

授業
業への適用

5.1

授 業の概要問1

グラフエデ
ディタを用いたた地図データ作成

本グラ
ラフ理論ライ
イブラリを高高等専門学校
校専攻
科１年のの授業で 2012
12 年前期に使使用し，評価 した．
実施した
た授業科目はは「データ構造
造とアルゴリ
リズム」
である．
．この科目はは１回の講義時間が 90 分
分であ

問2

授業は
は２部からななる．第１部ででは，まず，，講義
ータ構造造を解説する
る．次に，「CC#解説本」の
の作成

問3

4

3

2

1

人数

7

5

7

0

0

本グラフ理
理論ライブラリ
リライブラリ
リを
評価段階

5

4

3

2

1

人数

7

5

6

1

0

グラフ，頂
頂点，辺オブジ
ジェクトに
対する理解
解

演習を１
１班 4〜5 名かからなるグル
ループで行うう．平均 30 ペ ージの「C#解解説本」がでできあがる．
．
第２部
部では，まずず，講義形式ででソートアル
ルゴリ
ズムやグ
グラフアルゴゴリズムを解説する．次に
に，グ

5

使用するた
ための参照設設定

り，半年
年 15 回の授業
業を行う．
形式でプ
プログラミンング言語 C#のの解説と基本
本的デ

評価段階

問4

評価段階

5

4

3

2

1

人数

8

5

5

1

0

ダイクスト
トラの最短経路
路
アルゴリズ
ズムの理解

ラフアル
ルゴリズムのの演習を行うう．
2012 年
年度のグラフフアルゴリズ
ズムの演習課課題は最短経路路問題であるる．１班 2 3 名からなるグ
名
グルー
プで，グ
グループごととに異なる国をを対象として
て，あ

問5

評価段階

5

4

3

2

1

人数

5

8

5

1

0

ダイクスト
トラの最短経路
路アルゴリズズム

る都市か
から他の都市
市への最短経路路問題を解くく．本を，本グラフ理論ライ
イブラリを用いいてグラフ理理論ライブララリはこの演習で用いる．
．最短

作成するプ
プログラム演演習

経路関数
数についてははライブラリ
リで用意され
れてい

評価段階

5

4

3

2

1

る関数で
ではなく，学生
生が自らコーーディングし
した関

人数

10

3

5

0

1

数を用い
いる．
図 11 ははあるグループのプログラ
ラム作成例でである．

図 12 アンケート
ト集計結果 １

フランス
スを対象としした都市間のの距離と移動
動に要する時間間を求め，またた，移動経路
路を表示してい
いる．
問6

授業内容は
は講義と演習でではどちらがよいか
5 を演習のの方がよい，11 を講義の方が
が
よいとする
る
評価段階

5

4

3

2

1

人数

10

3

5

0

1

問 7．授業におい7
いて難しいと感感じた項目
A．講義内容A
B．プログラミB
ミング言語 C#のの理解
C．地図データC
タの作成
D．本グラフ理D
理論ライブラリリの設定
E．本グラフ理E
理論ライブラリリによる最短経路プ
プログラムの作の作成
F．特になし
F

図 11

巡回路
路

評価項目

A

B

C

D

E

F

人数

4

14

2

5

3

4

図 13 アンケート集
ト集計結果 ２168

松下浩明 : アルゴリズム演習のためのグラフ理論ライブラリ

5.2

アンケート集計結果とそれに対する考察

リズムまで，本グラフ理論ライブラリを使用する

本グラフ理論ライブラリを使った演習の評価 と複数レベルのアルゴリズム演習が問題なく行を行うために，以下の 7 項目について受講した学 えることを示した．
生 19 名に対してアンケートを行った．評価は５本グラフ理論ライブラリに対するアンケート

段階評価で行い，評価項目は問１から問５につい では，学習に役立つという評価を得ることができては５を容易，１を難しいとした．

た．その一方で，アンケートではグラフ理論ライ

集計結果を図 12 および図 13 に示す．問１ではグ ブラリの土台となるプログラミング言語に対す
ラフエディタの扱いやすさについて調査を行っ る敷居が高かったという結果も出ている．プログ
た．アンケート結果から，半数以上がデータ作成 ラミングの初心者向けには指導支援ツールがいはどちらかといえば容易であると回答している． くつか提案されている 11) 12)．このような先行研
平均値が 4.0 であることから，グラフエディタは 究を参考にしつつ，プログラミング言語の理解も含めたアルゴリズム演習を構築することが今後演習教材として向いているといえる．

次に，問２，問３，問５は本グラフ理論ライブ の課題である．
ラリを用いたプログラミング演習についての評参価である．いずれも 3.8 から 4.0 という高い結果

考

文

献

が得られた．
問４は講義によるダイクストラアルゴリズム 1)

F. Harary，グラフ理論，池田貞雄（訳），の理解度に関するものであり，問５はプログラミ

共立出版，東京，1978．

ングを行うことによるダイクストラアルゴリズ 2)

A.V. Aho, J.E. Hopcroft, J.D. Ullman，

ムの理解度に関するものである．講義よりプログ

データ構造とアルゴリズム，大野義夫（訳），ラミングによる理解度がやや増えている．ただし，

培風館，東京，1999.

１名はプログラミングによる理解度で最低評価 3)

柳本朋子，中本敦浩，桝田尚之， グラフ理をしている．演習を行えば，必ず理解が深まると論の教育についていえないことは，演習を授業に組み込むときの留−中学生を対象として−，意点である．

大阪教育大学紀要第 V 部門，vol.50, no.2,
pp201‑212, Jan. 2002.

問７の結果では，多くの学生が C#言語が難し
いと答えていることから，プログラミング言語に 4)

J. Siek, L. Lee, A. Lumsdaine, "The Boost

対するサポートも考慮しなければならないこと

Graph Library,"が分かった．

http://www.boost.org/doc/libs/1̲52̲0/libs/graph/doc/index.html, 2000.

6.

5)

むすび

浅野哲夫，小保方幸次，K. Mehlhorn， LEDA:
複雑なアルゴリズムも簡単にプログラム化
できる魔法のツール， 情報処理, vol.41,

本論文では，学習者に比較的容易に扱えるグラ

no.7, pp.854‑861, Jul. 2000.

フ理論ライブラリを構築し，アルゴリズム演習へ
6)の適用可能性について調べた．
グラフアルゴリズムの演習のためにはグラフ

B. Naveh, "JGraphT,"
http://www.jgrapht.org/, 2003.

データを容易に作成できる機能が必要であるこ 7)

松原勇，" グラフ理論を用いた授業設計支と，アルゴリズムのステップごとの動作確認でで援に関する一考察，"信学論 (A),きる機能が必要なこと，グラフアルゴリズムを容vol.J69‑A, no.9, pp.59‑64, Sep. 1986.

易にプログラム化できること，グラフの操作，特 8)

畠山誠，佐藤公男，" グラフ理論学習用エに頂点，辺の削除操作に関し，学習者を混乱させ

ディタの開発，"仙台電波工業高専研究紀ないことを述べた．

要,vol.33, pp.20‑27, 2003.

上記の問題を解決するために，グラフエディタ 9)

松下浩明，"グラフ理論ライブラリの比較−を作成し，その機能を説明した．また，深さ優先

Boost, JGraphT, Arena−，"探索を例にとり，効率的ではないが理解しやすい

http://www.di.kagawa‑nct.ac.jp/

アルゴリズムから効率的であるが複雑なアルゴ

matusita/Arena/boost‑jgrapht‑arena/169

香川高等専門学校研究紀要 5(2014)index.htm, 2011.

島川博光，" C 言語関数呼出しの記録を用

10) 丸岡将大，松下浩明，" グラフ理論ライブ

いた演習過程での習得項目の把握，"

ラリ Arena の構築と授業への適用，"信学技

信学論 (D), vol.J95‑D, no.12,

報, vol.111, no.473, ET2011‑119,

pp.2079‑2089, Dec. 2012.

pp.107‑112, Mar. 2012.
11) 中島秀樹，高橋直久，細川宣秀，" プログ
ラミング学習のための QA サイクル
−受講者の習得度に応じた問題提示メカニ
ズム−，"信学論 (D‑I), vol.J88‑D‑I,
no.2, pp.439‑450, Feb. 2005.
12) 谷川紘平，ディンドンフォン，原田史子，170