Đếm bậc cao nhất

Để tìm đỉnh có bậc cao nhất trong đồ thị, chúng ta cần tính bậc của mỗi đỉnh và sau đó tìm đỉnh có bậc lớn nhất. Dưới đây là mã nguồn cho thuật toán này sử dụng cả Python và C++.

Python
python
Sao chép mã
def find_highest_degree_vertex(n, adj):
max_degree = 0
max_vertex = -1
for i in range(n):
degree = len(adj[i])
if degree > max_degree:
max_degree = degree
max_vertex = i
return max_vertex, max_degree

# Ví dụ sử dụng
adj_list = [
[1, 2], # Đỉnh 0 kết nối với đỉnh 1 và 2
[0, 2, 3], # Đỉnh 1 kết nối với đỉnh 0, 2 và 3
[0, 1], # Đỉnh 2 kết nối với đỉnh 0 và 1
[1, 4], # Đỉnh 3 kết nối với đỉnh 1 và 4
[3] # Đỉnh 4 kết nối với đỉnh 3
]

vertex, degree = find_highest_degree_vertex(5, adj_list)
print(f"Đỉnh có bậc cao nhất: {vertex} với bậc là: {degree}")
C++
cpp
Sao chép mã
#include <iostream>
#include <vector>
using namespace std;

pair<int, int> find_highest_degree_vertex(int n, vector<vector<int>>& adj) {
int max_degree = 0;
int max_vertex = -1;
for (int i = 0; i < n; i++) {
int degree = adj[i].size();
if (degree > max_degree) {
max_degree = degree;
max_vertex = i;
}
}
return {max_vertex, max_degree};
}

int main() {
vector<vector<int>> adj_list = {
{1, 2}, // Đỉnh 0 kết nối với đỉnh 1 và 2
{0, 2, 3}, // Đỉnh 1 kết nối với đỉnh 0, 2 và 3
{0, 1}, // Đỉnh 2 kết nối với đỉnh 0 và 1
{1, 4}, // Đỉnh 3 kết nối với đỉnh 1 và 4
{3} // Đỉnh 4 kết nối với đỉnh 3
};

pair<int, int> result = find_highest_degree_vertex(5, adj_list);
cout << "Đỉnh có bậc cao nhất: " << result.first << " với bậc là: " << result.second << endl;
return 0;
}
Giải thích thuật toán:
Khởi tạo:

Biến max_degree để lưu trữ bậc lớn nhất tìm được. Ban đầu đặt là 0.
Biến max_vertex để lưu trữ đỉnh có bậc lớn nhất. Ban đầu đặt là -1.
Duyệt qua các đỉnh:

Với mỗi đỉnh, tính bậc của nó bằng cách đếm số lượng đỉnh kề trong danh sách kề (adjacency list).
So sánh bậc của đỉnh hiện tại với max_degree. Nếu bậc hiện tại lớn hơn max_degree, cập nhật max_degree và max_vertex.
Kết quả:

Sau khi duyệt qua tất cả các đỉnh, max_vertex sẽ là đỉnh có bậc cao nhất và max_degree là bậc của đỉnh đó.