━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 第14回「グラフ 2」の要点
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

路
        グラフの頂点の系列のうち，隣り合う頂点間が辺になっているもの

閉路
        グラフの路のうち始点と終点が同じもの

連結
        無向グラフの任意の2頂点間に路があること

木
        閉路の無い連結無向グラフ

部分グラフ
        元のグラフから辺や頂点の部分集合を取り出したグラフ

スパニング木
        グラフの全ての頂点を含む部分グラフのうち，木になっているもの

深さ優先探索
        頂点を訪問後，未訪問の隣接頂点を一つずつ選んで再帰的に深さ優先探索

深さ優先スパニング木(森) (DFST)
        深さ優先探索で訪問した辺だけを残した部分グラフ

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/