*************************************Đồ thị liên thông******************************************* 1.khái niệm Cho đồ thị G=(V,E), đồ thị G liên thông ó giữa mọi cặp đỉnh u,v bất kì luôn tồn tại đường từ u->v 2.thuật toán kiểm tra tính liên thông của đồ thị B1: khởi tạo các đỉnh đều chưa thăm fr[]=true B2: dùng bfs(1) hoặc dfs(1) (đỉnh nguồn bất kì) B3: + nếu có 1 đỉnh chưa được thăm => đồ thị ko liên thông +nếu tất cả các đỉnh đều được thăm => đồ thị liên thông 3.thành phần liên thông của đồ thị cho đồ thị vô hướng G=(V,E) , mot thành phần liên thông của đồ thị G là tập đỉnh V' G' F' thỏa mãn - với mọi cặp đỉnh u,v thuộc V' tồn tại đường đii từ u -> v => V' liên thông - nếu thêm bất kì một đỉnh x thuộc V\V' vào V' thì V' ko còn tính chất 1 THUẬT TOÁN ĐẾM SỐ THÀNH PHẦN LIÊN THÔNG CỦA ĐỒ THỊ - khởi tạo các đỉnh chwua được thăm ff[]=true; -duyệt các đỉnh u = 1 -> n nếu ff[u]=true //u chưa đc thăm { k++; // đếm số thành phần liên kết bfs[u] hoặc dfs[u]; } -khởi tạo b[]=0;
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter