Cho nhiệm vụ 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ị, mà tất cả các cạnh đều là hai chiều. Đồ thị vô hướng có thể di chuyển theo bất kỳ hướng nào từ một nút đến nút khác được kết nối.
Dưới đây là biểu diễn trực quan của đồ thị vô hướng.
Bây giờ, theo bài toán, chúng ta phải tìm số cạnh trong đồ thị vô hướng.
Cạnh trong đồ thị là các đường nối hai đỉnh 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 −
số cạnh là: 7
Phương pháp chúng ta sẽ chọn để giải quyết bài toán trên −
Khởi tạo một danh sách để lưu tất cả các đỉnh của danh sách đồ thị và chèn giá trị tương ứng.
Trong hàm count_edges, khai báo biến count=0 để trả về số cạnh.
Duyệt danh sách bằng vòng lặp cho đến khi đạt đỉnh cuối cùng và cộng giá trị count với graph_list[i].size() rồi lưu lại vào biến count.
Sau khi đạt đỉnh cuối cùng, chia giá trị count cho hai, và in kết quả.
Ví dụ
#include<bits/stdc++.h> using namespace std; //hàm chèn đỉnh void insert(list<int> graph_list[], int u, int v){ graph_list[u].push_back(v); graph_list[v].push_back(u); } //hàm đếm tổng số cạnh void count_edges(list<int> graph_list[], int v){ int count=0; //duyệt vòng lặp cho đến khi tìm thấy đỉnh 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[]){ //tạo 5 đỉnh trong đồ thị int vertices = 5; //khai báo list để tạo đồ thị và truyền đỉnh list<int> graph_list[vertices]; //gọi hàm insert truyền biến list, đỉnh, đỉnh liên kết 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); //gọi hàm count để đếm cạnh count_edges(graph_list, vertices); return 0 ; } Đầu ra
Nếu chúng ta chạy mã trên, chúng ta sẽ nhận được đầu ra sau −
count of edges are: 7