BrownCoder

無能ですがAtCoderしてます。情報処理試験や機械学習、その他ベンダー資格時々数学など参考になった本の紹介や雑記を書いてます。

【螺旋本】グラフのめも

この記事をシェアする

 DFS(深さ優先探索)やBFS(幅優先探索)を書きたいと思ったのですが、グラフに関する表現の知識が全くなく、ARC037_Aで解放コード見ても理解が出来ませんでした。あいにくKindleに螺旋本が入っていたので読み進めることにしました。基本的に螺旋本の引用です。ご理解ください。


arc037.contest.atcoder.jp



 

グラフ

グラフとは、「対象の集合とそれらのつながり(関係)の集合」を表すデータ構造です。グラフにおける「対象」はノード(node)または頂点(vertex)と呼ばれます。「つながり」は頂点と頂点の関係を表し、エッジ(edge)または辺と呼ばれ、円と縁を結ぶ線または矢印で書きます。深さ優先探索(BFS)や幅優先探索(DFS)に利用されたり、多くのアルゴリズムの基礎となっています。

 

種類

  • 無向グラフ...エッジに方向がないグラフ
  • 有向グラフ...エッジに方向があるグラフ
  • 重み付き無向グラフ...エッジに重み(値)があり、方向がないグラフ
  • 重み付き有向グラフ...エッジに重み(値)があり、方向があるグラフ


f:id:noikari:20190317131237p:plain
引用:https://www1.doshisha.ac.jp/~mjin/R/61/61.html

グラフの表記と用語

頂点の集合がV、辺の集合がEであるようなグラフをG=(V, E)と表記する。また、G=(V, E)における頂点と辺の数をそれぞれ|V|, |E|と表す。

 

2つの頂点u, vを結ぶ辺をe=(u, v)と表記する。無向グラフの場合(u, v)と(v, u)は同じ辺をします。重み付きグラフの辺(u, v) の重みをw(u, v)とする。

 

無向グラフに辺(u, v)があるとき、頂点uと頂点vは隣接している(adjacent)と言う。隣接している頂点の列v_0, v_1, ..., V_kをパス(path)という。始点と終点が同じようなパスを閉路(cycle)と言います。
 

閉路のない有向グラフをDirected Acyclic Graph(DAG)と呼びます。

 

頂点uにつながっている辺の数を頂点uの次数(degree)と言います。有向グラフにおいては、頂点uに入る辺の数を頂点uの入次数、頂点uから出る辺の数を頂点uの出次数と言います。

 

グラフ G = (V, E)の任意の2つの頂点u, vに対して、uからvへパスが存在するとき、Gを連結なグラフと言います。

 

2つのグラフGとG'について、G'の頂点集合と辺集合の両方がGの頂点集合と辺集合の部分集合になっているとき、G'をGの部分グラフと言います。

隣接リストと隣接行列による表現

グラフG = (V, E) の表現方法には隣接リスト(adjacency list)による表現と隣接行列(adjacency matrices)による表現がある。

 

隣接リスト

Vの各頂点に対して1個、合計|V|個のリストAdj[|V|]でグラフを現します。頂点uに対して、隣接リストAdj[u]はEに属する辺(u, v_i)におけるすべての頂点V_iを含んでいます。つまり、Adj[u]はGにおいてuと隣接するすべての頂点からなります。

 

f:id:noikari:20190317132940p:plain
http://web-ext.u-aizu.ac.jp/course/alg1/ex/jp/ex13/

隣接行列表現

頂点iから頂点jへ辺がある場合a_ijが1、ない場合0であるような|V| * |V|の行列Aでグラフを表します。

f:id:noikari:20190317133100p:plain
http://web-ext.u-aizu.ac.jp/course/alg1/ex/jp/ex13/

メリット
  • M[u][v]で辺(u, v)を参照できるので、頂点uと頂点vの関係を定数時間(O(1))で確認することが出来る。
  • M[u][v]を変更することで辺の追加や削除を簡単かつ効率的に行うことができる(O(1))。
デメリット
  • 頂点の数の2乗に比例するメモリを消費するので、辺の数が少ない場合や頂点の数が多い場合はメモリの使い過ぎに注意をする。
  • 1つの隣接行列では、頂点uから頂点vへの関係を1つしか記録ができない。

隣接行列表現の実装

AOJの問題に実装する問題があるので実際に実装してみる

書いたコード

#include<bits/stdc++.h>
using namespace std;

int V[100][100] = {{0}};

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        int u, k; cin >> u >> k;
        for(int i = 0; i < k; i++){
            int v; cin >> v;
            V[u - 1][v - 1] = 1;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(j) cout << " ";
            cout << V[i][j];
        }
        cout << endl;
    }
}

judge.u-aizu.ac.jp

まとめ

グラフの基礎は理解が出来ました。いよいよ深さ優先探索幅優先探索を実際に実装していこうと思います。