グラフと木の違いを一言で言えますか？ - Schi Heil と叫ぶために最近 DirectShow や GStreamer などのマルチメディアフレームワークを勉強している。これらの特徴を表すキーワードとして pipe-and-filter とか graph-based とか filter chains とかいろいろ出てくるのだが、どうやら filter graph という用語が一般的のようだ (wikipedia に項目としてあるという意味で)。 ところで、グラフという言葉でふと思い出したのが表題の「グラフ(Graph) と 木(Tree) の違い」。グラフ理論の教科書に書いてあるような厳密な定義はおいておいて、要するに一言で言うと違いは何という部分。私なら、 木は各ノードへの入力(親)が必ず一個しかない。そうじゃないのが(親が複数あれば)グラフ。 という説明をする。木をその特殊なケースの二分木のことだと理解していると、子の数や深さを説明に出してしまう。もち
