プログラミング | ページ 16

[Python] クラスカル法

クラスカル法を用いて、重み付き無向グラフの最小全域木を求めます。以下の記事の続きです。プリム法は、ある頂点を選び、その頂点と繋がる辺の中で最小のものを選ぶことで、結果的に最小全域木を得ることができるアルゴリズムです。クラスカル法は、閉路を作...

プリム法を用いて、重み付き無向グラフの最小全域木を求めます。プリム法はダイクストラ法とほぼ同じで、コードもダイクストラ法のものをほぼ流用しています。全域木全域木とは、グラフの中の全ての頂点を使って作られる木のことです。全域木（ぜ...

Pythonで、ベルマン–フォード法を使って、重み付きの有向グラフの単一始点最短経路問題を解きます。以下の続きです。ダイクストラ法は辺の重みがゼロ以上の場合でしたが、ベルマン–フォード法は辺の重みが負の場合に使われます。負の閉路がある場合...

Python で、ダイクストラ法を使って、重み付きの有向グラフの単一始点最短経路問題を解きます。以下の続きです。ダイクストラ法ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが...

Python で重み無しの有向グラフの単一始点最短経路問題を解きます。以下の続きです。最短経路問題グラフ理論における最短経路問題（さいたんけいろもんだい、英:shortest path problem）とは、重み付きグラフの与えられた2つの...

トポロジカルソートを Python で書きます。以下の続きです。トポロジカルソートトポロジカルソート（英:topological sort）とは、グラフ理論において、有向非巡回グラフ（英:directed acyclic graph, DA...

無向グラフをBFSで探索するアルゴリズムを Python で記述します。以下の続きです。幅優先探索幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(...

無向グラフをDFSで探索するアルゴリズムを Python で記述します。グラフは隣接リストを用いて表現します。深さ優先探索深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）...

下記の記事の続きです。 Python で隣接リストを用いてグラフを表現します。隣接リスト隣接リスト（英: adjacency list）は、グラフ理論でのグラフにある頂点または辺を全てリスト（一覧）で表現したものである。出典: フリー百...

Python で隣接行列を用いてグラフを表現します。グラフ理論については、下記を読んでいる途中です。グラフ理論講義ノート隣接行列グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英:adjacency matrix）は、...