ITリテラシ | ページ 2

[グラフ] クラスカル法

クラスカル法は、素集合データ構造を使い最小全域木の問題を解くアルゴリズムです。全域木ある無向グラフを考えた時、このグラフの全域木とは、グラフの頂点全てを使い構成される部分グラフで、木構造になるものです。全域木（ぜんいきぎ、英:Span...

以下のスライドがダントツで分かりやすいです。素集合データ構造素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割し...

DAG DAG とは Directed acyclic graph 有向非巡回グラフの略で、閉路のない有向グラフのことです。 DAGの例。有向グラフかつ閉路がない。有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんか...

ベルマンフォード法ベルマン–フォード法(英:Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキュー...

最短経路問題グラフ理論における最短経路問題（さいたんけいろもんだい、英:shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。出典: フリー百科事典『...

Python で深さ優先探索を実装します。ノードクラス幅優先探索と同じです。各ノードは自身の名前、隣接リスト、訪問済みかどうかのフラグを持ちます。 class Node(object): def __init__(s...

深さ優先探索深さ優先探索（ふかさゆうせんたんさく、英:depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始ま...

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

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

Python で三分探索木を実装してみます。ノードクラスそれぞれのノードは、その文字を持ち、左右と真ん中に子を持ちます。また、キーとしてその文字列が存在する場合は、値を持ちます。 class Node(object): ...