Tìm thành phần liên thông của đồ thị

29/10/2017

Xìn chào các bạn,

Như trên tiêu đề,ở bài này ta sẽ phân tích,đưa ra giải thuật cho bài tập này.Để dể hiểu hơn nếu các bạn chưa hiểu về DFS , BFS thì nên xem lại để bài này dễ dàng hiểu hơn nhé.

Mình xin nhắc lại một chút về thuật toán tìm kiếm theo chiều sâu (vì nó được dùng lại trong phần bài này).
Tìm kiếm ưu tiên chiều sâu hay tìm kiếm theo chiều sâu (tiếng Anh: Depth-first search - DFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị. Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh.

Như vậy,mình cần đặt ra một câu hỏi:khi mà nó không có nhánh để đi tiếp thì nó sẽ làm gì?Nếu theo hướng code thì nó dùng stack.pop() cái đỉnh vừa đi ra và kiểm tra tiếp. Nhưng giả sử rằng như hình đồ thị bên dưới:

Giả sử như hình trên,nếu nó duyệt một đỉnh trong hình vuông thì nó sẽ chẳng bao giờ đi đến được hết các đỉnh còn lại.Vậy một lần nó duyệt như thế thì đó là 1 thành phần liên thông.Tiếp tục như vậy ta nhảy đỉnh duyệt qua hình tam giác thì nó sẽ duyệt được hết các đỉnh trong hình tam giác đó,ta lại được thành phần thứ 2.Tiếp tục như thế thì ta sẽ đi đến được hết các thành phần còn lại.Vậy cái khó của mình là gì nè.Chúng ta cần phải xác định được khi nào chương trình nó dừng,khi nào nó nhảy qua đỉnh khác và nhảy như thế nào...

Thì những bước làm đó mình sẽ chú thích trong code.Các bạn tiếp tục theo dõi phần code để hiểu được quy trình nhé:

public void findComponentConnected() {
        //Khởi tạo biến đếm thành phần liên thông
		int dem = 1;
		//Phần này là thuật toán duyệt DFS nên các bạn hiểu rồi phải hông nè.
		int i = 0;
		int numVertex = topNum();
		ArrayList listVS = new ArrayList<>();
		int visit[] = new int[numVertex];
		Stack stack = new Stack<>();
		
		//Ở đây setTop của mình dùng để chứa các đỉnh chưa duyệt.Mục đích là để kiểm tra đỉnh nào chưa 
// duyệt thì nhảy qua đỉnh đó để duyệt ArrayList setTop = new ArrayList<>(); //Đầu tiên thì nó chưa tất cả các đỉnh for (int j = 0; j < topNum(); j++) { setTop.add(j); } listVS.add(i); visit[i] = 1; stack.push(i); //Cứ mỗi lần duyệt rồi thì xóa đỉnh đó trong setTop đi setTop.remove(i); while (!stack.empty()) { i = stack.peek(); int count = 0; for (int j = 0; j < visit.length; j++) { if ((this.arr[i][j] > 0) && visit[j] != 1) { visit[j] = 1; listVS.add(j); stack.push(j); //Đây,cứ thêm vô( duyệt rồi) thì xóa trong setTop đi,vì j là giá trị,nên mình cần
//tim index của giá trị này để xóa trong setTop. for (int j2 = 0; j2 < setTop.size(); j2++) { if (setTop.get(j2) == j) setTop.remove(j2); } //Nhớ dừng,giống bên DFS đó các bạn break; } else { count++; } } if (count == visit.length) { //Nếu đã không có cạnh để đi thì mình in ra thành phần liên thông thứ mấy,và đường đi System.out.println("Thanh phan lien thong thu: " + dem); print(listVS); //Sau đó,mình kiểm tra đỉnh nào chưa duyệt thì duyệt tiếp.Vì setTop chứa những đỉnh
//chưa duyệt,nên chỉ cần lấy đỉnh đầu tiên trong setTop là ok. //Nếu setTop rỗng nghĩa là đã đi qua hết rồi thì dừng chương trình nhé if (!setTop.isEmpty()) { i = setTop.get(0); //Khi lấy ra rồi thì nhớ tăng biến đếm thành phần liên thông lên dem++; //KHi bắt đầu quá trình mới thì nhớ xóa hết stack với cái list đỉnh đã đi qua đi nhé stack.removeAll(stack); //Nhớ phải push lại giá trị vừa lấy ra từ setTop,nếu không chương trình dừng vì stack rỗng đó. stack.push(i); listVS.removeAll(listVS); } else { //nè nếu setTop rỗng thì dừng nè break; } } } } //Cái này dùng để in thành phần liên thông nè public void print(ArrayList list) { for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " ==> "); } }

Nếu các bạn gặp khó khăn trong code thì đừng ngại comment problem nhé.Nhớ xem video để hiểu thêm nè.Ahihi.


Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :