日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス
Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
0. はじめに --- グラフ探索の動機 現代ではコンピュータはとても身近なものになりました。コンピュータの用途としては シミュレーションなどの大規模計算を行う 人工知能をつくる アプリを開発する などなど多様なものが考えられますが、「探索」もまた、コンピュータを用いるモチベーションとして、最も基本的かつ重要なものの一つだと思います。探索とは、与えられた対象の中から、目的に合うものを見つけ出したり、最良のものを見つけ出したり、条件を満たすものを列挙したりする営みです。 世の中における様々な問題は、探索によって、考えられる場合を調べ尽くすことによって原理的には解決できるものが多いです。例えば、現在地から目的地まで最速でたどり着く方法を求める問題は、原理的には、現在地から目的地へ到達する経路をすべて列挙することで解決できます1。将棋やオセロの必勝法を求める問題は、原理的には、考えられる局面と
Microsoft PowerPoint - ad09-09.ppt
アルゴリズムと データ構造 ６．２．１節：最小木 ２．５節：集合族の併合 塩浦昭義 情報科学研究科 准教授 shioura@dais.is.tohoku.ac.jp 今日の講義の概要 グラフのデータ構造 最小木問題 最小木を求める２つのアルゴリズム クラスカルのアルゴリズム アルゴリズムの計算時間の解析 集合族の併合のためのデータ構造 無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 無向グラフと有向グラフ 2 3 0 1 4 a c f e d b 2 3 0 1 4 a c f e d b 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v)頂点uは枝eの始点 頂点vは枝eの終点 グラフ G=(V, E) を表現す
アルゴリズムとデータ構造
アルゴリズムとデータ構造 第11回 グラフの探索 アルゴリズムとデータ構造#11 1 今日の内容 2 ◼ グラフ ◼ なんでグラフ？ ◼ グラフの数学的な定義 ◼ ネットワーク（重み付きグラフ）の定義 ◼ グラフデータの取り扱い方 ◼ 隣接行列による表現 ◼ 隣接リストによる表現 ◼ グラフの探索の仕方 ◼ 幅優先探索 ◼ 深さ優先探索 アルゴリズムとデータ構造#11 ケーニヒスベルクの橋 ◼ ケーニヒスベルクという街には プレーゲル川が流れ、 7つの橋が架かっていた ◼ Q： 7つすべての橋を、それぞれちょうど 1 回ずつ渡って歩く コースって、ある ? オイラー (Euler) 18世紀の数学者。天文学者や物理学者などでもある。 解析学、整数論、トポロジー、グラフ理論などに大きな足跡を残した。 A： ない。 その理由は … 図は、http://Wikipedia.org より ケーニヒ
グラフ探索アルゴリズム とその応用
グラフ探索アルゴリズム とその応用 2011 / 05 / 04 保坂和宏 内容 • グラフの扱い方 • 深さ優先探索 (DFS) – 橋，関節点 • 幅優先探索 (BFS) – Dijkstra 法, 0-1-BFS • 辞書順幅優先探索 (LexBFS) – cograph グラフ • グラフ理論からの出題 – Islands (IOI 2008) – Regions (IOI 2009) – Saveit (IOI 2010) – Regions (JOI 2010 春合宿) – Finals (JOI 2010 春合宿) – Joitter (JOI 2011 選考会) – Shiritori (JOI 2011 選考会) – Report (JOI 2011 選考会) – Orienteering (JOI 2011 選考会) グラフ • グラフとは？ – 「点が線で繋がった構造
NetworkXメモ（有向グラフ） - Qiita
概要 最近研究でNetworkXを使い出したので自分用のメモとしてよく使いそうなモジュールを書いていきます． Pythonを使い出して間もないので，スマートに書けてないと思います．あと言葉使いが間違ってる部分があるかもしれない(メソッドとかパッケージとか)． NetworkXパッケージの導入はpipでできます．pip install networkxでOKです． Reference : http://networkx.readthedocs.io/en/stable/ NetworkXパッケージのインポート まずNetworkXパッケージをインポートします．NetworkXのドキュメントではnxとして短縮名をつけています．
Algorithms with Python / 集合, グラフ, 経路の探索
簡単な例を示しましょう。a = Set([1, 2, 3, 4, 5]), b = Set([4, 5, 6, 7]), c = Set([6, 7]) とします。 a.issubset(b) => False c.issubset(b) => True a.union(b) => Set([1, 2, 3, 4, 5, 6, 7]) a.union(c) => Set([1, 2, 3, 4, 5, 6, 7]) a.intersection(b) => Set([4, 5]) a.intersection(c) => Set([]) a.difference(b) => Set([1, 2, 3]) a.difference(c) => Set([1, 2, 3, 4, 5]) ●プログラムの作成 それではプログラムを作りましょう。最初にクラスを定義します。 リスト : クラスの定義
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Depth First Search or DFS for a Graph - GeeksforGeeks