アルゴリズムとデータ構造

【アルゴリズムとデータ構造】グラフ

グラフとは?

グラフは、VとEの組の集合にです。2つのノードを決めたら通りかたが2通り以上あるもの。\(G(V,E)\)と表記します。他の表記法として、\(G(V={v_1,v_2,…v_m},E={e_1,e_2,…,e_n})\)や\(G({v_1,v_2,…v_m},{e_1,e_2,…,e_n})\)のように表します。

そして
\(V = \{v_1,v_2,…v_m\},\)\(m = |V|\)とはvertice(node,vertex)(頂点)
\(E = \{e_1,e_2,…e_n\},\)\(n = |E|\)とはedge(辺)です

グラフの種類

有向グラフ(A Directed Graph)

\(G(V=\{a,b,c,d,e,f\}\)\(,E=\{(a,b),(a,c),(a,d),(b,a),(b,c),\)\((c,e),(d,b),(d,c),(d,e),(f,d),(f,e)\}\)

辺は\((a,b)\neq (b,a)\)なので2回書いても重複にはなりません。

 

無向グラフ(An Undirected Graph)

\(G(V=\{a,b,c,d,e,f\},)\)\(,E=\{(a,b),(a,c),(a,d),(b,c),(b,d),\)\((c,d),(c,e),(d,e),(d,f),(e,f)\}\)

辺は\((a,b)= (b,a)\)なので2回かくと重複になってしまいます。

プログラムの中でのグラフの表現

Adjacency Matrix

2次元の配列Aを使って表します。A[i][j]=1だったら頂点iが頂点jとつながっていることを表します。A[i][j]が0だったら頂点iが頂点jとつながってないことを表します。

Adjacency List

連結リストを用いて表します。この表し方は、グラフがsparseの時に使用できます。

・dence
EがVに比べ比較的多いグラフを密グラフ。

・sparse
EがVに比べ比較的少ないグラフのこと。Eが\(V \log V\)以下のグラフのこと

Matrix vs List

・Adjacency Matrix
頂点の数が\(n\)だとすると、\(n^2\)の領域が必要になる。

・AdjacencyList
辺が存在するか確認するために時間がかかる