Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Cây khung đồ thị là gì?
    Định nghĩa của nó rất đơn giản: Cho đồ thị G = (V, E) cây khung của đồ thị T=(V, E') trong đó E' [You must be registered and logged in to see this image.] E. T liên thông và không có chu trình. Nếu /V/ = n (Đồ thị G có n đỉnh) → /E'/ = n - 1. T có n - 1 cạnh.

    Tìm cây khung của đồ thị theo phép duyệt theo chiều rộng.

    1. T = Ø ;
    For all x Э V           ĐX(x) : = False;

    2. Chọn đỉnh xuất phát u.
    ĐX(u) : = true;
    Hàng_đợi: = {u};

    3. while Hàng_đợi ≠ Ø do
                        a. Lấy a từ hàng đợi
                        b. For all x Э ke+ (a) do
                                            if not ĐX(x) then
                                                      b1. T : = T U {(a, x)}
                                                      b2. ĐX(x) : = true
                                                      b3. Đưa x vào hàng đợi

    Lưu ý:
    Bài toán tìm cây kung của đồ thị thực chất là tìm tập cạnh. Trước khi trình bày thuật toán, bao giờ cũng phải đưa ra cấu trúc dữ liệu để lưu trữ cây khung. Thường cây khung được lưu dưới dạng mảng các cạnh (n - 1) cạnh.

    T: array [1.. n-1] of Edge
              Edge = record
                        đ, c: tên đỉnh //đầu cuối
              end;

    Bây giờ thử làm bài tập theo phần lý thuyết trên nha.
    Một đề thi có câu sau:
    Đồ thị G( V, t) liên thông có n đỉnh đánh số từ 1 đến n cho bởi ma trận kề A = (aij)mxn. Viết thủ tục xây dựng cây khung của đồ thị dựa trên phép duyệt theo chiều rộng.

    Bài làm
    - Cấu trúc cây khung cần lưu trữ vào dạng dữ liệu sau:
    T: array [1.. n-1] of Edge
              Edge = record
                        đ, c: tên đỉnh //đầu cuối
              end;

    - Thủ tục tạo cây khung
    proc Tìm_Cây_khung;
    1. for i:=1 to n do ĐX(i):= False;
    2. u:= Đỉnh_xuất_phát;
              ĐX(u) : = true;
              MakeNull (Q); EnQueue(u, Q) {Đưa u vào hàng đợi}
              k:=0;
    3. while Empty (Q) = false do
                        a. a:= Front(Q); DeQueue(Q);
                        b. for x : =1 to n do
                                            if A[a, x] = 1 and ĐX(x) = false then
                                                                k:=k+1
                                                                T[k].đ = a; T[k].c = x;
                                                                ĐX(x) : = true;
                                                                EnQueue (x, Q);
    4. Output (T).

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Các đề cần phải làm hết sức thành thạo theo cách thức tương tự trên:
    1. Đồ thị G( V, t) liên thông có n đỉnh đánh số từ 1 đến n và có m cạnh cho bởi danh sách cạnh:
              D: array [1..n] of Edge
                        Edge = record;
                                  đ, c: Tên đỉnh;
                                  End;
    Viết thủ tục xây dựng cây khung.

    3. Đơn đồ thị G = {V, E} vô hướng liên thông, có n đỉnh đánh số 1 .. n cho bởi danh sách kề.
    DSK = Record
                        m: Số cạnh liên thuộc;
                        A: array [1..m] of Integer;
                        End;

    DS: array [1..n] of DSK

    Viết thủ tục chi tiết xây dựng cây khung của đồ thị G dựa trên phép duyệt ưu tiên chiều rộng. Cây khung phải lưu vào danh sách:
    List [1..n] of Edge
              Edge = Record
                        đ, c: Tên đỉnh;
              End;

    https://khmt.123.st

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Còn Tìm cây khung của đồ thị theo phép duyệt theo chiều sâu thì sao vậy Admin :D
    Admin có thể trình bày theo đúng cách thày Tĩnh được không?

    vipbn90a3

    vipbn90a3
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    dacminhm đã viết:Còn Tìm cây khung của đồ thị theo phép duyệt theo chiều sâu thì sao vậy Admin :D
    Admin có thể trình bày theo đúng cách thày Tĩnh được không?
    Chắc là thay hàng đợi bằng ngăn xếp là được thì phải?

    http://sharecodeweb.net

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất