（初心者向け）グラフの実装について

タイトルの通り初心者向けです。よかったらゆっくり見ていってください。

さて、競技プログラミングの過去問を解いていると最短経路の問題など、頂点と辺に関する問題が現れます。
町Aと町Bを連結している道路dみたいな感じです。このようなグラフの問題は既にたくさんのアルゴリズムの記事があるのですが、逆に簡単な実装の記事があまり見当たりませんでした。
なので今回は単純な実装ができるようになることを目標とします。

まずは隣接行列といった形です。簡潔でごり押しなので単純に書きたいときに役立ちます。

とりあえず、辺があるか否かの確認から。一番簡単な形です。

#include <iostream>

using namespace std;

bool graph[1010][1010];//グローバルな場所に配列を置くとすべて0に初期化される。

int main() {
    int V, E;//頂点の数V(vertex)と辺の数E(edge)がよく与えられる
    cin >> V >> E;

    graph[1][3] = true;//町1から町3に辺が出ている

    //無向グラフの場合は以下のように両方から書いておく必要があります。
    graph[3][4] = true;//町3から町4に辺が出ている
    graph[4][3] = true;//町4から町3に辺が出ている

    for (int i = 0; i < E; i++) {//入力例
        int a, b;
        cin >> a >> b;
        graph[a][b] = true;
        graph[b][a] = true;
    }

    //問題　goalまで町1から一つの町を通っていけるかどうか
    int g = 8;
    //goalの頂点が8のパターンとする
    for (int i = 0; i < E; i++) {
        if (graph[1][i] == true && graph[i][g] == true) {
            cout << "GOAL" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;//今回はNO
}

次にコストなどがある重み付きグラフのパターン。
道路を渡るコストが存在するとき、先ほどtrueとしたところをかかるコストに変えることで実装できます。

#include <iostream>

using namespace std;

int graph[1010][1010];

int main() {
    int V, E;//頂点の数V(vertex)と辺の数E(edge)がよく与えられる
    cin >> V >> E;

    graph[1][3] = 5;//町1から町3に行くにはコスト5が必要

    //無向グラフの場合は以下のように両方から書いておく必要があります。
    graph[3][4] = 10;//町3から町4には10必要
    graph[4][3] = 10;//町4から町3にも10必要

    for (int i = 0; i < E; i++) {//入力例
        int a, b, cost;
        cin >> a >> b >> cost;
        graph[a][b] = cost;
        graph[b][a] = cost;
    }

    //問題　goalまで町１から一つだけ町を通ってコスト15以内でたどり着けるか。
    int g = 4;
    //goalの頂点が4のパターンとする
    for (int i = 0; i < E; i++) {
        if (graph[1][i]!=0 && graph[i][g]!=0 && graph[1][i] + graph[i][g] <= 15) {
            cout << "GOAL" << endl;//今回は成功
            return 0;
        }
    }
    cout << "NO" << endl;
}

といった具合。頂点aから頂点bまで[a][b]=cost;となり、見やすいのが特徴。ちなみにダイクストラ法の簡単な実装も可能。
でも辺が少ないと配列のメモリの消費量が大きいのがちょっと辛い。

そこで次は隣接リストといった形。先ほどより少し難しいのでまずは簡単な例を書きます。

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[1050];

int main() {

    graph[2].push_back(7);//頂点2から頂点7へ
    graph[3].push_back(5);//頂点3から頂点5へ
    graph[3].push_back(2);//頂点3から頂点2へ

    cout << graph[2][0] << endl;//7
    cout << graph[3][0] << endl;//5
    cout << graph[3][1] << endl;//2
}

リスト番号をiとすると、graph[a][i]=bとなっています。これが隣接リストです。
先ほどと違う点は、隣接行列なら簡単にコストを入れることが出来ましたが、
こちらではその分をリストの番号に割り振ったといった感じでしょうか。

また隣接リストを用いると、ループについてかなり書きやすくなります。

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[1050];

int main() {

    graph[3].push_back(5);//町3から町5へ
    graph[3].push_back(2);//町3から町2へ
    graph[3].push_back(8);//町3から町8へ

    int a = 3;
    for (int i = 0; i < graph[a].size(); i++) {
        //頂点aに連結しているすべての頂点を最小回数で洗い出せる
        cout << graph[a][i] << ' ';//5 2 8
    }
}

いかがでしょうか。このループは上手く使えば計算量も少なくなりそうで、中々に使い道がありそうです。

最後に、隣接リストにおける重み付きグラフ、すなわちコストの存在する場合の実装のコード例を載せます。

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, cost;
};

vector<edge> graph[1050];//構造体にて二つの成分を持てるようになった

int main() {

    int a = 2, b = 3, co = 6;//町aから町bに行くときのコストco
    edge e = { b,co };
    graph[a].push_back(e);

    a = 2, b = 4, co = 5;
    e = { b,co };
    graph[a].push_back(e);

    for (int i = 0; i < graph[a].size(); i++) {
        edge e = graph[a][i];//aからの行き先とaからのコストを取り出せる
        cout << e.to << ' ' << e.cost << endl;
    }
}

といった感じ。構造体の知識や、vectorを使いこなす必要があるけど、とても便利。

今回はここまで。グラフを初めて見たときは実装する方法が全くわからなかったので、そういった点に絞りました。
ここまで理解すれば最短経路問題のアルゴリズムのコードは大体読めるようになっていると思います。（特にダイクストラ法）
競プロはアルゴリズムの勉強も大事だけど、基礎的な実装も大事！