Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Xây dựng đồ thị từ một ma trận

  1. #1
    Ngày gia nhập
    09 2008
    Bài viết
    2

    Mặc định Xây dựng đồ thị từ một ma trận

    Các bác pro ơi giúp em với! Mọi người có thể chỉ cho em giải thuật của bài toán này không?

    Bài toán giả định: 3 nước A, B, C đang chiếm giữ một số đảo trên quần đảo Thiên đường. nước A muốn xây dựng một hệ thống cầu phao để nối liền các đỉnh do mình chiếm giữ. Để đơn giản coi bản đồ quần đảo là một ma trận kích thước MxN. Trong đó ô kí hiệu "x" là do nước khác chiểm giữ, kí hiệu "o" là do A chiếm giữ, kí hiệu "." là biển. Cầu chỉ được bắc qua biển, không được qua các nước khác và không đi chéo.

    Bài toán: Xây dựng hệ thống cầu phao nối liền giứa các đảo sao cho số cầu phao là ít nhất.

    Bài này em nghĩ là cần xây dựng một đồ thị có đỉnh là các đảo cua A, sau đó tìm cây bao trùm nhỏ nhất của đồ thị đó. Tìm cây bao trùm nhỏ nhất thì đã có thuật toán prim rùi, nhưng bây giờ phải làm sao để xây dựng được cái đồ thị đó đây? Mong mọi người giúp em với. Thanks alot

  2. #2
    Ngày gia nhập
    11 2008
    Bài viết
    2

    Có thể biểu diễn bằng ma trận kề hoặc danh sách kề. trong đó mỗi đảo là 1 đỉnh của đồ thị.

Các đề tài tương tự

  1. Trao đổi liên kết, trao doi logo, Text Link với các webforumblog (free)
    Gửi bởi nguyenlam14990 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 31
    Bài viết cuối: 13-03-2012, 11:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn