グラフの 上を あるく 二つの ほうほう

一つの 点から はじめる

前回 グラフを 見ましたね。
点は ノード、線は エッジ、
わが ない グラフが ツリーです。
今回は その 上を あるきます。
あるくには まず
どこから はじめるか きめます。
一つの 点を えらぶと、
すぐ つながった となりが 見えます。

点を クリックして 出発点を きめます。(出発点 = あお · すぐ つながった となり = あかるく)

出発点から 一ぽ いくと
となりに とどきます。
そこから また 一ぽ いくと
となりの となりです。
こうして 線に そって
あしを うつし、
点を 一つずつ ふむのが
グラフの 上を あるく ことです。

ちかい 順、はば ゆうせん

さいしょの あるきかたは 波です。
出発点の すぐ となりを ぜんぶ ふみ、
つぎに 一まい とおく、
また 一まい とおく。
いけに 石を なげると
わが ひろがる ように、
ちかい ところから 順に
そとへ ひろがります。

クリックするたびに 一まいずつ 波のように ひろがります。(ふんだ 点 = いろ · 同じ まいは 同じ きょり)

波が ひろがる あいだ、
まだ 行けない 点は
まつ れつに ならびます。
さきに ならんだ 点から
順に たちよります。
だから ちかい 点が
いつも とおい 点より さきです。
まいが そのまま きょりです。

さいごまで、ふかさ ゆうせん

二つめの あるきかたは めいろ たんけんです。
一つの みちを えらび
いける ところまで ずっと いきます。
もう いく ところが なければ
一ぽ もどって
まだ いってない よこみちへ また ずっと。
ひろく ひろがる かわりに
ふかく ほりさげます。

クリックで 一つの みちを さいごまで いき、いきどまりで もどります。(いまの 点 = あお · もどった みち = うすく)

もどるのを わすれない ように、
とおった 点を つみあげます。
つんだ やまの
いちばん 上から たどりなおして
よこみちを さがします。
だから ふかさ ゆうせんは
いちばん さいきん たちよった ところへ
さきに もどります。

はば ゆうせんが さいたんを くれます

波は ただ ひろがるのでは ありません。
ちかい まいから ふむので、
ある 点に はじめて とどいた しゅんかんが
そのまま いちばん はやい みちです。
線ごとの きょりが 同じなら、
何まいめで とどいたかが
そのまま 出発点からの きょりです。
まわり道が ありません。

クリックで 二つの あるきかたの とうちゃく 順を くらべます。(はば ゆうせんの まい ばんごう = そのまま さいたん きょり)

ふかさ ゆうせんは はやく とおくへ いきますが、
まわって とどく ことも あります。
だから さいたん きょりは
波、つまり はば ゆうせんの やくめです。
ただ いまは すべての 線を
きょりが 同じと みなしました。
線ごとに きょりが ちがえば
また べつの はなしで、それは つぎに。

まとめ

グラフの 上を あるく 二つの ほうほうを 見ました。
はば ゆうせんは 波のように
ちかい ところから 一まいずつ ひろがり、
ふかさ ゆうせんは 一つの みちを
さいごまで いって もどります。
どちらも すべての 点を ふみますが
じゅんばんが ちがいます。
きょりが 同じなら はば ゆうせんが さいたんです。

二つの あるきかたを おして つけて。(はば ゆうせん = 波 · ふかさ ゆうせん = さいごまで)

ちずで みちを さがす、
友だちの 友だちを たどる、
めいろを ぬける。
グラフの 上を あるく ことは
思ったより ちかくに あります。
つぎは 線ごとに きょりが ちがう
グラフで いちばん はやい みちを
さがす はなしを します。