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変数に格納します。

• 最後の頂点に到達したら、countの値を2で割り、結果を出力します。

例

#include<bits/stdc++.h>
using namespace std;
//function to insert vertices
void insert(list<int> graph_list[], int u, int v){
   graph_list[u].push_back(v);
   graph_list[v].push_back(u);
}
//function to count the total number of edges
void count_edges(list<int> graph_list[], int v){
   int count=0;
   //traverse the loop till the vertice is found
   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[]){
   //creating 5 vertices in a graph
   int vertices = 5;
   //declare list to create a graph and pass the vertices
   list<int> graph_list[vertices];
   //call insert function passing the list variable, vertice, linked vertice
   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);
   //calling count function that will count the edges
   count_edges(graph_list, vertices);
   return 0 ;
}

出力

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

count of edges are: 7