久々のお絵描き講座です。10枚の絵を描いたぞ(って、落描きみたいなモンですけど)。 有向グラフは計算科学(コンピューティング・サイエンス)で頻出する大事なデータ構造です。コンピュータで扱えるのは有限グラフですが、無限グラフが登場しないのかというと、そうではありません。コンピュータでも、可能性として無限となりうるデータ構造を扱います。とはいえ、何の秩序もない無限データはさすがに扱いにくいので、有限的に定義できる無限構造が興味の対象となります。 ここでは、無限な有向グラフのなかで最もよく使う無限ツリーを考えます。さらに、次の条件を満たすものを例題に使います。 末端のノード(リーフノード)には整数の値が付着している。 中間の分岐ノードは特に値を持たない。 絵を描くときは、末端ノードには単に整数だけを書き、中間ノードは黒丸にします。ルートノードを識別するためには、「ルート」とラベルを書いた矢印を使
![お絵描きで学ぶ・無限正規ツリーとBNF(バッカス/ナウア形式) - 檜山正幸のキマイラ飼育記 (はてなBlog)](https://cdn-ak-scissors.b.st-hatena.com/image/square/c1dcb06af86372e1d54311aa45ce55e42b531a55/height=288;version=1;width=512/http%3A%2F%2Fwww.chimaira.org%2Fimg2%2Fregtree-0.gif)