Đạ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]

    LeVanDat

    avatar
    Chuyên viên
    Chuyên viên
    đ/c nào trình bày tường minh bài toán đếm số vùng không liên thông của đồ thị G, n đỉnh cho bởi ma trận kề (a(i,j))n.
    Cám ơn nhiều

    haihonglyk6

    haihonglyk6
    Chuyên viên
    Chuyên viên
    Đ/c có thể làm như sau:
    1. dem=0; for x=1 to n Đx(x)=false
    2. proc DCS (u: đỉnh XP)
              a. Đx(x) = true          Đx(u) = true;
              b. for x = 1 to n
                        if (a(u,x)=1 & !Đx(x)) then DCS(x)
    3. for i=1 to n
              if (!Đx(i)) then
                        DCS(i)
                        dem ++
    4. output dem.

    Tongmanhcuong

    avatar
    Quản trị viên
    Quản trị viên
    Anh Đạt có lời. Em giúp: Có gì anh cho ý kiến nha.
    1) For i := 1 To n Do Chưa_xét(i):= False;
    2) Đếm:= 0;
    3) For i:= 1 To n Do
              If not Chưa_xét(i) Then
                        Đếm:= Đếm + 1;
                        DS(i);
    4) Output Đếm;

    Thủ tục DS(i) anh biết rồi. Em không cần Post nha mất thời gian.

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Hôm trước thầy yêu cầu viết việc đếm phần không liên thông qua giải thuật Prim hoặc Kruscal. Ý tưởng của Phan Việt là cho mỗi đỉnh là một cây, rồi đưa dần các đỉnh ghép từng một cây khung, như vậy có n đỉnh thì sẽ có n vùng không liên thông ban đầu. Duyệt qua tất cả các cạnh, mỗi lần ghép 1 cạnh vào cây khung, vùng không liên thông sẽ giảm đi 1 (nghĩa là lấy n - 1). Cuối cùng sẽ có được n là số vùng không liên thông với nhau. Ở đây những lệnh không cần thiết sẽ bỏ đi, chỉ quan tâm đến những lệnh đánh dấu thôi, vì mình chỉ đếm thôi mà, ghép cây làm gì cho nó mệt vì chẳng giải quyết được gì.

    Từ bài viết của LĐS ta có thể viết lại như sau thuật toán này.
    Nháy vào chỗ hồng hồng này để xem hoặc ẩn chi tiết:
    Vùng_Liên_Thông = n;
    For i:=1 to n do VT(i):=i;
    Đánh dấu tất cả các đỉnh bằng số thứ tự đỉnh
    For j=1 to m do Kiểm tra lần lượt m cạnh hiện có của đồ thị G
    If VT(ds[j].d) != VT(ds[j].c) Then Nếu hai đầu của cạnh hiện tại đánh dấu không giống nhau: Thực hiện
    tgd:= VT(ds[j].d); Ghi lại giá trị đánh dấu của đỉnh đầu cạnh đang xét
    tgc:= VT(ds[j].c); Ghi lại giá trị đánh dấu của đỉnh cuối cạnh đang xét
    for i:= 1 to n do Kiểm tra lần lượt các đỉnh:
    If VT(i) := tgd Then VT(i):=tgc;
    Nêu đỉnh đầu nào mà có đánh dấu giống như giá trị lưu trong tgd thì thay giá trị đánh dấu bằng giá trị lưu trong tgc. Điều này nghĩa là sẽ đồng nhất các đỉnh đã nối sẽ cùng đánh dấu một giá trị. Khi đó những đỉnh đã nối vào với nhau sẽ không nối nội bộ được nữa, điều này sẽ khiến không thể tạo thành chu trình bởi dòng lệnh If VT(ds[j].d) != VT(ds[j].c) chỉ cho phép nối các đỉnh có đánh dấu khác nhau.
    Vùng_Liên_Thông--
    Output
    Vùng_Liên_Thông

    https://khmt.123.st

    LeVanDat

    avatar
    Chuyên viên
    Chuyên viên
    Cam on d/c Cuong va d/c Hai Hong nhe.
    Le Van Dat

    LeVanDat

    avatar
    Chuyên viên
    Chuyên viên
    Tôi thấy rằng ý tưởng của đ/c Việt Anh về giải quyết vấn đề số vùng liên thông trong đồ thị không liên thông là đúng và gọn gàng. Nên giải quyết theo hướng này. Có lẽ cũng nên trình bày với thày giáo, xem ý kiến thầy thế nào. Tất nhiên là thầy muốn ta rèn luyện để nhớ thuật toán Prim hoặc Kruskal. Nhưng rõ ràng đi theo 2 thuật toán này câu lệnh đều dài và khó nhớ.
    Cám ơn nhiều.

    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