C++에서 무방향 그래프의 간선 수 계산

무방향 그래프의 간선 수를 계산하는 작업이 주어집니다. 무방향 그래프는 모든 모서리가 양방향인 그래프를 형성하기 위해 함께 연결되는 정점 세트입니다. 무방향 그래프는 한 노드에서 다른 연결된 노드로 임의의 방향으로 이동할 수 있습니다.

아래는 무방향 그래프를 시각적으로 나타낸 것입니다.

이제 문제에 따라 무방향 그래프에서 간선의 수를 찾아야 합니다.

그래프의 간선은 두 정점이 연결되는 선입니다.

입력 -

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