kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

GRL_4_B: Topological Sort

閉路のない有向グラフの頂点を、各辺(u,v)についてuがvよりも
先に位置するように並べる

ヒントに深さ優先探索幅優先探索両方あるのはなんだ
両方組み合わせて使うってことだろうか

探索しているあいだに頂点間の大小関係が作れそう
大小関係が作れさえすればソートはできるか
挿入ソートみたいにすればいい?
いや、大小関係が完全に作れればsortを呼ぶだけで並べられるな
完全に、といっても大小をきちんと定められないところはあるけど
そういうところは大小どっちに決めても問題ないんじゃないか

始点や終点が1つとは限らないんだろうな
まず始点や終点を見つけないといけないかな?
それとも流れの中で勝手に決まる?
ひとつの頂点から上り下り両方に探索すれば全体を探索できる?
いやそんなことはなさそうだ
始点や終点を見つけるのも結局探索だし
手当たり次第に探索するのかな?
なんかあんまりカッコよくない気がする

それとも、ソートで比較する度に探索する?
探索して見つからなければ自分の方が大きいことにする、とか
メモ化すればそこまで計算量は多くはならない気もする

スッキリいいアイデアが浮かばないかと思って
ほぼ忘れてた幅優先探索を思い出しながら書いてみながら考えてみたけど

浮かばない