Đếm số cạnh trong đồ thị vô hướng trong C ++

Nhiệm vụ được giao là đếm số cạnh trong một đồ thị vô hướng. Đồ thị vô hướng là một tập hợp các đỉnh được kết nối với nhau để tạo thành một đồ thị, có tất cả các cạnh đều có hướng. Đồ thị vô hướng có thể di chuyển theo bất kỳ hướng nào từ nút này đến nút được kết nối khác.

Dưới đây là phần trình bày trực quan của biểu đồ vô hướng.

Bây giờ, theo bài toán, chúng ta phải tìm số cạnh trong biểu đồ vô hướng.

Các cạnh trong biểu đồ là các đường mà hai đỉnh được nối với nhau.

Đầu vào -

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);

Đầu ra -

count of edges are: 7

Phương pháp tiếp cận mà chúng tôi sẽ chọn để giải quyết vấn đề trên -

• Khởi tạo danh sách để lưu trữ tất cả các đỉnh của danh sách biểu đồ và chèn các giá trị tương ứng.

• Trong hàm count_edges, khai báo một biến count =0 để trả về số lượng các cạnh.

• Duyệt qua danh sách bằng một vòng lặp cho đến khi chúng ta đến đỉnh cuối cùng và thêm giá trị của số đếm với graph_list [i] .size () và lưu trữ trở lại biến đếm.

• Sau khi chúng ta đến đỉnh cuối cùng, hãy chia giá trị của số đếm cho hai và in kết quả.

Ví dụ

#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 ;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

count of edges are: 7