グラフ理論 | ページ 2

[グラフ] 幅優先探索

幅優先探索幅優先探索（はばゆうせんたんさく、英:breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノー...

グラフ理論グラフ理論（グラフりろん、英:Graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ（データ構造）などの応用がある。出典: フリー百科事典『ウィキペディア（Wikipedi...

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

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

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

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

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

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

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