Tìm chu trình và đường đi euler

30/10/2017

Chào mừng bạn đã đến với phần 2 tìm đường đi và chu trình nếu đồ thị đó tồn tại đường đi hoặc chu trình.Ở bài này thì chủ yếu ta phân tích thuật toán để tìm,chứ không kiểm tra mấy cái điều kiện rối rối như ở phần 1 nữa.Chúng ta vào bài thôi nào,hehe.

Đầu tiên ta lại phải đi search wiki cho chuẩn nhé,xem xem nó có nói gì về thuật toán không nhé!

Sau một hồi nguyên cứu thì wiki cho ra một giải thuật như thế này:
Giải thuật:Gọi chu trình cần tìm là C
1.Khởi tạo: Chọn một đỉnh bất kỳ cho vào C.
2.Nếu G không còn cạnh nào thì dừng.
3.Bổ sung: Chọn một cạnh nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cạnh cầu nếu không còn cạnh nào khác để chọn. Bổ sung cạnh vừa chọn và đỉnh cuối của nó vào C, xóa cạnh ấy khỏi G. Quay về bước 2.
Với: Một cạnh của đồ thị G được gọi là cầu, nếu khi xóa cạnh đó khỏi đồ thị thì làm tăng số thành phần liên thông của G.

Hii,rồi xong,xác định,đọc xong hông hiểu gì luôn.Không sao,Phong có cái này dể dể tưởng tượng hơn.Các bạn nhớ cái định nghĩa không?Nó nói là chu trình thì đi qua các cạnh (không lập lại cạnh) và đỉnh (được lập lại đỉnh),đồng thời đỉnh đầu phải trùng với đỉnh cuối.Các này có vẽ ok hơn nè.
Các bạn suy nghĩ cùng Phong nhé,nếu như mình duyệt đồ thị theo DFS,mà cứ đi qua cạnh nào thì mình xóa cạnh đó đi.Có phải nếu làm như vậy thì không bao giờ nó bị lập cạnh không.Vậy nếu chúng ta kết hợp một chút DFS và xóa cạnh khi nó đi qua thì ok rồi.

Nói dài dòng vậy thôi chứ đọc code thử xem nè,y chang DFS luôn ý:

public boolean eulerCycle(int start) {
      //Đoạn này giống DFS thì thôi luôn,hehe
		Stack stack = new Stack<>();
		stack.push(start);
		ArrayList listVisit = new ArrayList<>();
		while (!stack.empty()) {
		    //Lấy đỉnh đầu tiên ra xét
			int current_vertex = stack.peek();
			// Biến này dùng để kiểm tra xem cái đỉnh kế có cạnh đi qua hay không ý
			boolean has_edge = false;
			for (int i = 0; i < topNum(); i++) {
			    //DUyệt nó thôi,nếu nó có cạnh thì vào trong if đánh dấu liền
				if (this.matrixA[current_vertex][i] != 0) {
					// đánh dấu nó có cạnh liền
					has_edge = true;
					//Đây đây cái này quan trọng nè,đi qua là xóa cạnh nhé,vì vô hướng nên xóa 2 
//chiều,có hướng thì nhớ là một chiều thôi nha. this.matrixA[current_vertex][i] = this.matrixA[i][current_vertex] = 0; //Nhớ push vô stack để nó chạy vòng lập nha. stack.push(i); //Khi đã có thằng có cạnh rồi thì mình dừng cái for đi (theo nguyên tắc cuộc của DFS ý) break; } } //Còn đây là trường hợp không có cạnh nè if (!has_edge) { //Buộc phải lấy đỉnh khác ra test đường đi thôi int vertex = stack.pop(); //Khi lấy ra thì mình add vào list các đỉnh đi qua nhé listVisit.add(vertex); } } //Thông thường thì nó sẽ in ra chiều ngược nên các bạn nhớ viết đoạn code
//để nó in ra theo chiều ngược lại // in ra duong di theo chieu nguoc lai String string = ""; String temp = " ==> "; for (int k = listVisit.size() - 1; k >= 0; k--) { string += listVisit.get(k); if (k > 0) { string += temp; } } System.out.println(string); return true; }

Còn một điểm lưu ý là các bạn nhớ bao bọc đoạn code trên bởi các điều kiện ở phần 1 nhé.DÙng một câu if(dieu-kiên) rồi bao bọc hết phương thức trên lại.

Đó là với chu trình,còn đường đi thì sao?Đường đi thì ta bắt buộc phải tìm được 2 đỉnh có bậc lẽ ý,và cho nó bắt đầu từ đỉnh đó là xong ngay.
Mà công việc tìm 2 đỉnh bậc lẽ thì lại khá simple.Nó như thế này nè:

if (isHasEulerPath()) {
            //KHởi tạp biến đếm ngay thôi,hehe
			int k = 0;
			for (int i = 0; i < matrixA.length; i++)
			//nếu nó lẽ thì thực hiện gán,và dừng ngay và luôn
				if (topDegree(i) % 2 != 0) {
					k = i;
					break;
				}
//đến đây rồi thì chỉ việc gọi phương thưc hoy,hehe
			eulerCycle(k);
		}

Yeah,xong rồi nè,các bạn có hiểu bài hông,có thắc mắc nhiều hông nè,chúc các bạn làm bài tốt nhé.hehe.Thân!


Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :