深さ優先探索とは グラフにおいて、いけるところまで深くいき、いけなくなったら引き返してまた同じことをする探索を深さ優先探索という。 実装 実装方法として再帰関数を用いる方法とstackを用いる方法がある。 再帰関数を使う方法は逃げてなのでstackでや…

幅優先探索とは グラフにおいて、ある頂点から初めてそこからの最短距離が短い順にグラフの頂点を探索する方法である。 実装 これはVecDequeを用いて実現できる。これは前後から取り出しができるvectorである。 let mut q = std::collections::VecDeque::new…

すみません。人からライブラリを拝借して一旦終わります。 理解できないですこれ。 // ---------- begin scc ---------- pub fn strongly_connected_components<G, I>(size: usize, graph: G) -> (usize, Vec<usize>) where G: Fn(usize) -> I, I: Iterator<Item = usize>, { let mut or</item></usize></g,>…

プリム法と同様に、重み付き無向グラフにおいて最小全域木を求めるアルゴリズムである。 クラスカル法とは 以下のアルゴリズムである。 辺集合Eを重みの小さな順にsortする。 その辺を追加しても閉路ができないのであれば、その辺を答えに追加する。この閉路…

プリム法とは、クラスカル法と同様に重み付き無向グラフにおいて最小全域木（とその辺の重みの総和）を求めるアルゴリズムである。 プリム法とは ある頂点を一つ選ぶ。 確定している頂点から確定していない頂点への辺のうち、重みが最も小さなものを通る辺と…