グラフ

グラフとは

頂点(ノード)と頂点間を結ぶ辺(エッジ)で構成されるデータ構造をグラフという。

また、グラフの特別な状態を木構造と言ったりもする。

用語

各 ○ を頂点と呼び、頂点と頂点を結んでいる線を辺と呼ぶ。 この図のように辺で結んでいる両頂点を行ったり来たりすることができるグラフのことを無向グラフという。

図ではよく線が用いられる。

無向グラフとは違い、片方の頂点からは向かうことができるが、反対からは向かうことができない一方通行なグラフを有向グラフという。

図ではよく矢印が用いられる。

頂点間を移動できる 1 つの辺のことを路と呼び、路を通り同じ頂点に訪れない経路をパスといい、始点と終点が同じパスをサイクル(閉路)という。

グラフにおいて任意の頂点から全ての頂点へ訪れることが可能な時そのグラフは連結であるという。連結でない時連携していないグラフを連携成分といい、連結である場合は連結成分が1となる。

有向グラフにおいて任意の頂点から全ての頂点へ訪れることが可能な時そのグラフは強連結であるという。強連結ではないがサイクルができているものを強連結成分という。

グラフにおいて始点と終点が同じ辺をループ(自己ループ)と呼び、2 頂点間に複数の辺が存在するとき多重辺と呼ぶ。

無向グラフにおいて頂点に接続している辺の個数を次数と呼び、有向グラフにおいては入ってくる辺を入次数、出て行く辺を出次数と呼ぶ。

閉路のない有向グラフのことを DAG(Directed Acyclic Graph)という。

データの持ち方

データの持ち方は以下の 2 種類が存在する

• 隣接リスト表現
• 隣接行列表現

隣接行列表現

行列でデータを管理する表現方法である。

メリット

• O(1)で特定の辺が存在するか知ること
• 行列の掛け算や固有値が意味を持つことがある

デメリット

• メモリが頂点数*頂点数程度必要
• 次数を求めるのが O(頂点数)

表現方法

頂点数*頂点数の配列を用意し、i頂点とj頂点の間に辺が存在している場合は[i][j]に辺が存在しているフラグを保持する。

以下の図では[i][j] = 1の時、i頂点とj頂点の間に辺が存在し,[i][j] = 0の時、辺が存在しないことを表している。

※ = 1ではなく、重み(辺ごとに異なる)が入る場合もある。

プログラム

無向グラフ

Python

box = [[1,5],[3,1],[1,4],[4,3],[4,6],[6,2]]
graph = [[0] * 6 for _ in range(6)]
for i in range(len(box)):
    graph[box[i][0]-1][box[i][1]-1] = 1
    graph[box[i][1]-1][box[i][0]-1] = 1

C++

int main() {
    vector<pair<int,int>> box = {{1,5},{3,1},{1,4},{4,3},{4,6},{6,2}};
    vector<vector<int>> graph(6,vector<int>(6,0));
    for(int i = 0; i < box.size();++i){
        graph[box[i].first-1][box[i].second-1] = 1;
        graph[box[i].second-1][box[i].first-1] = 1;
    }
    return 0;
}

C#

public static void Main(string[] args)
{
    int[,] box = new int[,] { { 1, 5 }, { 3, 1 }, { 1, 4 }, { 4, 3 }, { 4, 6 }, { 6, 2 } };
    int[,] graph = new int[6, 6];
    for (int i = 0; i < box.Length/2; ++i)
    {
        graph[box[i, 0] - 1, box[i, 1] - 1] = 1;
        graph[box[i, 1] - 1, box[i, 0] - 1] = 1;
    }
}

有向グラフ

Python

box = [[1,5],[3,1],[1,4],[4,3],[4,6],[6,2]]
graph = [[0] * 6 for _ in range(6)]
for i in range(len(box)):
    graph[box[i][0]-1][box[i][1]-1] = 1
    # graph[box[i][1]-1][box[i][0]-1] = 1

C++

int main() {
    vector<pair<int,int>> box = {{1,5},{3,1},{1,4},{4,3},{4,6},{6,2}};
    vector<vector<int>> graph(6,vector<int>(6,0));
    for(int i = 0; i < box.size();++i){
        graph[box[i].first-1][box[i].second-1] = 1;
        // graph[box[i].second-1][box[i].first-1] = 1;
    }
    return 0;
}

C#

public static void Main(string[] args)
{
    int[,] box = new int[,] { { 1, 5 }, { 3, 1 }, { 1, 4 }, { 4, 3 }, { 4, 6 }, { 6, 2 } };
    int[,] graph = new int[6, 6];
    for (int i = 0; i < box.Length/2; ++i)
    {
        graph[box[i, 0] - 1, box[i, 1] - 1] = 1;
        //graph[box[i, 1] - 1, box[i, 0] - 1] = 1;
    }
}

隣接リスト表現

頂点数分の配列を用意し、存在する辺のみを管理する表現方法である。

メリット

• メモリが辺の数で済む
• 次数を求めるのが速い

デメリット

• 特定の辺が存在するかの判定に最悪 O(頂点数)かかる

表現方法

頂点数分の配列を用意し、存在する辺と繋がっている反対の頂点番号を保持する。

プログラム

無向グラフ

Python

box = [[1,5],[3,1],[1,4],[4,3],[4,6],[6,2]]
graph = [[] for _ in range(6)]
for i in range(len(box)):
    graph[box[i][0]-1].append(box[i][1]-1)
    graph[box[i][1]-1].append(box[i][0]-1)

C++

int main() {
    vector<pair<int,int>> box = {{1,5},{3,1},{1,4},{4,3},{4,6},{6,2}};
    vector<vector<int>> graph(6);
    for(int i = 0; i < box.size();++i){
        graph[box[i].first-1].push_back(box[i].second-1);
        graph[box[i].second-1].push_back(box[i].first-1);
    }
    return 0;
}

C#

public static void Main(string[] args)
{
    int[,] box = new int[,] { { 1, 5 }, { 3, 1 }, { 1, 4 }, { 4, 3 }, { 4, 6 }, { 6, 2 } };
    List<List<int>> graph = new List<List<int>>();
    for (int i = 0;i < 6; ++i)
    {
        graph.Add(new List<int>());
    }
    for (int i = 0; i < box.Length/2; ++i)
    {
        graph[box[i, 0] - 1].Add(box[i, 1] - 1);
        graph[box[i, 1] - 1].Add(box[i, 0] - 1);
    }
}

有向グラフ

Python

box = [[1,5],[3,1],[1,4],[4,3],[4,6],[6,2]]
graph = [[] for _ in range(6)]
for i in range(len(box)):
    graph[box[i][0]-1].append(box[i][1]-1)
    # graph[box[i][1]-1].append(box[i][0]-1)

C++

int main() {
    vector<pair<int,int>> box = {{1,5},{3,1},{1,4},{4,3},{4,6},{6,2}};
    vector<vector<int>> graph(6);
    for(int i = 0; i < box.size();++i){
        graph[box[i].first-1].push_back(box[i].second-1);
        // graph[box[i].second-1].push_back(box[i].first-1);
    }
    return 0;
}

C#

public static void Main(string[] args)
{
    int[,] box = new int[,] { { 1, 5 }, { 3, 1 }, { 1, 4 }, { 4, 3 }, { 4, 6 }, { 6, 2 } };
    List<List<int>> graph = new List<List<int>>();
    for (int i = 0;i < 6; ++i)
    {
        graph.Add(new List<int>());
    }
    for (int i = 0; i < box.Length/2; ++i)
    {
        graph[box[i, 0] - 1].Add(box[i, 1] - 1);
        // graph[box[i, 1] - 1].Add(box[i, 0] - 1);
    }
}