C++で無向グラフの辺（エッジ）の数を数える方法

無向グラフと辺の数を数える問題

今回の課題は、無向グラフに含まれる辺の数を数えることです。無向グラフとは、複数の頂点（ノード）を双方向の辺で結んで構成されるグラフのことで、あるノードから接続先のノードへ、どちらの方向にも移動できるのが特徴です。

下図は無向グラフを視覚的に表したものです。

この問題では、与えられた無向グラフの中に辺が何本あるかを求めます。グラフにおける辺とは、2つの頂点を結ぶ線のことです。

入力：

insert(graph_list, 0, 1);
insert(graph_list, 0, 2);
insert(graph_list, 1, 2);
insert(graph_list, 1, 4);
insert(graph_list, 2, 4);
insert(graph_list, 2, 3);
insert(graph_list, 3, 4);

出力：

count of edges are: 7

問題を解くためのアプローチ

• グラフの全頂点の隣接リストを格納するリストを初期化し、値を順に挿入します。
• count_edges関数内で、辺の数を保持するための変数 count = 0 を宣言します。
• ループを使ってリストを最後の頂点まで走査し、各頂点の graph_list[i].size()（隣接する頂点の数＝次数）を count に加算していきます。
• 最後の頂点まで走査できたら、count の値を2で割り、結果を出力します。

なぜ2で割るのかというと、無向グラフでは1本の辺が両方の頂点からそれぞれカウントされるため、次数の合計は実際の辺数のちょうど2倍になるからです。したがって、合計を2で割ることで正確な辺の総数が求まります。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
// 頂点を挿入する関数
void insert(list<int> graph_list[], int u, int v){
    graph_list[u].push_back(v);
    graph_list[v].push_back(u);
}
// 辺の総数を数える関数
void count_edges(list<int> graph_list[], int v){
    int count=0;
    // 最後の頂点までループを走査する
    for (int i = 0 ; i < v ; i++){
        count += graph_list[i].size();
    }
    count = count/2;
    cout<<"count of edges are: "<<count;
}
int main(int argc, char* argv[]){
    // グラフに5つの頂点を作成する
    int vertices = 5;
    // グラフを作成するためのリストを宣言し、頂点数を渡す
    list<int> graph_list[vertices];
    // リスト変数、頂点、接続先の頂点を渡してinsert関数を呼び出す
    insert(graph_list, 0, 1);
    insert(graph_list, 0, 2);
    insert(graph_list, 1, 2);
    insert(graph_list, 1, 4);
    insert(graph_list, 2, 4);
    insert(graph_list, 2, 3);
    insert(graph_list, 3, 4);
    // 辺の数を数えるcount_edges関数を呼び出す
    count_edges(graph_list, vertices);
    return 0 ;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

count of edges are: 7