8
Thời hạn cho dự án này đang kết thúc nhanh chóng và tôi không có nhiều thời gian để giải quyết những gì nó còn lại. Vì vậy, thay vì tìm kiếm các thuật toán tốt nhất (và có lẽ phức tạp hơn/tốn thời gian), tôi đang tìm các thuật toán dễ nhất để thực hiện một vài thao tác trên một cấu trúc Graph.Gợi ý các thuật toán đơn giản nhất cho một số thao tác Biểu đồ
Các hoạt động tôi sẽ cần phải làm như sau:
- Liệt kê tất cả người dùng trong mạng theo đồ thị được đưa ra một khoảng cách X
- Liệt kê tất cả người dùng trong mạng theo đồ thị được đưa ra một khoảng cách X và loại các mối quan hệ
- Tính con đường ngắn nhất giữa 2 người dùng trên mạng theo đồ thị được đưa ra một loại quan hệ
- Tính khoảng cách tối đa giữa 2 người dùng trên mạng theo đồ thị
- Tính mo st người dùng kết nối từ xa trên mạng graph
Một vài lưu ý về thực hiện Graph tôi:
- Nút cạnh có 2 thuộc tính, là một trong những loại
charvàintkhác. Chúng đại diện cho loại quan hệ và trọng lượng tương ứng. - Đồ thị được triển khai với danh sách được liên kết, cho cả hai đỉnh và cạnh. Ý tôi là, mỗi đỉnh trỏ đến điểm tiếp theo và mỗi đỉnh cũng trỏ tới đầu của một danh sách liên kết khác, các cạnh của đỉnh cụ thể đó.
Những gì tôi biết về những gì tôi cần phải làm:
- Tôi không biết nếu điều này là đơn giản nhất như tôi đã nói ở trên, nhưng đối với con đường ngắn nhất giữa 2 người, tôi tin rằng các Dijkstra thuật toán là những gì mọi người dường như đề nghị khá thường xuyên vì vậy tôi nghĩ rằng tôi sẽ đi với điều đó.
- Tôi đã tìm kiếm và tìm kiếm và tôi thấy khó thực hiện thuật toán này, có ai biết về bất kỳ hướng dẫn nào hay dễ hiểu vì vậy tôi có thể tự thực hiện thuật toán này không? Nếu có thể, với các ví dụ mã nguồn C, nó sẽ giúp ích rất nhiều. Tôi thấy nhiều ví dụ với ký hiệu toán học nhưng điều đó chỉ làm tôi bối rối hơn.
- Bạn có nghĩ rằng điều này sẽ hữu ích nếu tôi "chuyển đổi" biểu đồ thành ma trận kề để đại diện cho trọng số liên kết và loại quan hệ? Nó sẽ được dễ dàng hơn để thực hiện các thuật toán trên đó thay vì các danh sách liên kết? Tôi có thể dễ dàng thực hiện một chức năng để thực hiện chuyển đổi đó khi cần thiết. Tôi đang nói điều này bởi vì tôi có cảm giác sẽ dễ dàng hơn sau khi đọc một vài trang về chủ đề này, nhưng tôi có thể sai.
- Tôi không có bất kỳ ý tưởng nào về 4 hoạt động, đề xuất khác?
1) Khoảng cách X, tôi giả sử nó giống như tổng trọng lượng giữa 2 nút. 2) Tôi không biết tần suất, các hoạt động ở trên là các tùy chọn trong menu Giao diện người dùng. 3) Nó giống như ~ 18000 đỉnh với ~ 520000 liên kết trên mẫu dữ liệu được cung cấp. 4) Ngoài ra, cảm ơn các liên kết, tôi sẽ điều tra ... –
Tôi đã cập nhật câu trả lời của mình và cũng đã thêm một số câu hỏi khác :). – IVlad
Không có đặc tính đặc biệt ... Vâng, nếu bạn nói không có thuật toán đặc biệt và sẽ mất quá nhiều thời gian với những thuật toán thông thường, hơn là tôi không hiểu điểm của các hoạt động này là một phần của dự án. Năm ngoái (mà tôi đã không hoàn thành vì các vấn đề cá nhân) dự án tương tự nhưng chỉ có con đường ngắn nhất được hỏi: S –