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

Đề tài: Hỏi cách biểu diễn cây tổng quát

  1. #1
    Ngày gia nhập
    03 2009
    Bài viết
    9

    Mặc định Hỏi cách biểu diễn cây tổng quát

    Hiện giờ em phải làm bài tập lớn về tìm cây khung nhỏ nhất, đầu vào là cây tổng quát và quá trình tính toán có liên quan đến đường kính và tâm của cây, thế nên em muốn hỏi cách biểu diễn cây tổng quát trong C++ để có thể xử lý được quan hệ nút cha-con và tính toán được khoảng cách giữa 2 nút bất kỳ của cây

    Em xin chân thành cảm ơn mọi sự giúp đỡ của các bác

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

    có phải ý bạn là tìm trọng số của cây khung nhỏ nhất sau đó xuất ra cây khung đó phải không?
    mình đọc mà không hiểu cho lắm bạn có thể nói cụ thể hơn một chút không?

  3. #3
    Ngày gia nhập
    03 2009
    Bài viết
    9

    Đầu vào là 1 cây tổng quát, với trọng số trên mỗi cạnh, đầu ra là cây khung nhỏ nhất. Thuật toán sử dụng có yêu cầu xác định đường kính(khoảng cách lớn nhất giữa 2 nút của cây) và tâm(v là tâm cây nếu tổng khoảng cách từ v đến các nút còn lại là nhỏ nhất).

    Nếu (u,v) là 1 cạnh thì khoảng cách từ u -> v chính bằng trọng số trên (u,v), ngược lại khoảng cách là tổng trọng số trên đường đi ngắn nhất từ u đến v.

    Vấn đề của em là đầu vào, em chưa tìm ra cách biểu diễn cây tổng quát nào phù hợp cho các tính toán của bài:(

  4. #4
    Ngày gia nhập
    10 2008
    Bài viết
    178

    đầu vào là một cây tổng quát nghĩa là sao?
    cây khung là con của một đồ thị mà.đầu vào là một cây thì tìm cây khung làm j nữa

  5. #5
    Ngày gia nhập
    03 2009
    Bài viết
    9

    Trích dẫn Nguyên bản được gửi bởi rua_con Xem bài viết
    đầu vào là một cây tổng quát nghĩa là sao?
    cây khung là con của một đồ thị mà.đầu vào là một cây thì tìm cây khung làm j nữa
    Bởi vì bài toán là tìm cây khung nhỏ nhất dựa trên khái niệm "tâm" của cây, cho nên đầu vào chỉ có thể là cây, chứ sao là đồ thị được?

  6. #6
    Ngày gia nhập
    10 2008
    Bài viết
    178

    Mặc định Hỏi cách biểu diễn cây tổng quát

    cây khung là một tập con của đồ thị "nó có đủ số đỉnh và số cạnh = số đỉnh -1":
    nếu cho đầu vào là một cây => nó có n dỉnh và n-1 cạnh => nó đã là một cây khung rùi

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