Duyệt đồ thị theo chiều sâu

26/10/2017

Phong xin chào các bạn nè,

Hii,đến đây thì qua mỗi bài đăng thì độ khó cũng dần tăng lên rồi phải không nè.Hehe.

Đùa thôi nè,đến giai đoạn này thì thuật toán chỉ tăng lên một chút à.Các bạn chỉ cần chịu khó suy ngẫm chút cùng với những gợi ý làm bài của Phong thì chắc chắn bạn sẽ làm được thôi nè.

Đầu tiên chúng ta cần phải hiểu duyệt theo chiều sâu nghĩa là gì nhé.Hii sau một hồi mình search wiki thì có kết quả như sao:

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. Thông thường, DFS là một dạng tìm kiếm thông tin không đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của nút đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước. Trong dạng không đệ quy, tất cả các đỉnh chờ được phát triển được bổ sung vào một ngăn xếp LIFO. Độ phức tạp không gian của DFS thấp hơn của BFS (tìm kiếm theo chiều rộng). Độ phức tạp thời gian của hai thuật toán là tương đương nhau và bằng O(|V| + |E|).

Đấy trên đấy là cái định nghĩa dài dòng,cơ mà từ nó là ta thấy ngay có hai cách hiện thực liền.Nếu để ý các bạn sẽ thấy một là hiện thực bằng đệ quy,hai là hiện thực bằng cách thông thường (dùng cấu trúc dữ liệu)

Trong bài hướng dẫn này,mình sẽ demo luôn 2 cách để các bạn dễ nhận xét luôn nhé.

Đầu tiên là với đệ quy.Nói tới đề quy điều ta nghĩ tới đầu tiên là code sẽ max gọn.Ở phương thức này,theo định nghĩa trên chắc chắn ta nhận biết được giá trị truyền vào chắc chắn là một đỉnh bất kỳ,và giá trị trả về có thể là boolean,String,void,hay là một list<<Đỉnh>> các đường đi,...Với tùy trường hợp sử dụng thì bạn chọn cho phù hợp.Ở bài này Phong chọn cái void cho nó gọn nhé.

Ý tưởng như thế này.Đầu tiên ta suy nghĩ ta cần gì trong phương thức này nhé.Trước hết là một cái list lưu những đỉnh đi qua.Tiếp theo là một cái mãng với độ dài bằng số đỉnh đồ thị.Để đánh đấu các đỉnh vừa thăm (mục đích để khi hết đường đi theo quy tắc cuộn,thì ta quay lại đỉnh viến thăm gần nhất đó mà).Rồi với đệ quy thì chỉ nhiêu đó thôi.

Mình sẽ show đoạn code ra và chú thích cho các bạn hiểu nhé.

public void DFS(int i) {
        //Các bạn nên nhớ 2 mãng dưới đây các bạn khi khởi tạo phải đặt ngoài phương thức nhé.vì nếu không khi gọi đệ quy sẽ bị sai đó.
        //Đánh dấu đỉnh i đã duyệt
		visit[i] = 1;
		//lưu đỉnh i là đỉnh đã đi qua
		listVisit.add(i);
		for (int j = 0; j < this.arr.length; j++) {
		//Kiểm tra xem có cạnh kề không,và đỉnh đó đã qua rồi hay chưa
			if ((this.arr[i][j] > 0) && this.visit[j] != 1) {
			//nếu thỏa điều kiện thì gọi lại đệ quy với đỉnh j (đỉnh kề).
				DFS(j);
			}
		}
	}

Các bạn không hiểu chổ nào thì mạnh dạng comment các bạn nha,Phong sẽ cố gắng giải đáp sớm nhất có thể nhé.Bên dưới là video Phong nói về DFS đệ quye nè.Nghe lại để rèn cách phân tích các bạn nhé.

Duyệt đồ thị theo chiều sâu không dùng đệ quy

Sau khi các bạn đọc phần phân tích ở trên rồi thì phần nào các bạn cũng mường tựa được cái mình sắp nói ở đây.Phương thức này cũng giống như trên nhưng dùng một cấu trúc dữ liệu có tính chất LIFO để thay thế cho đệ quy.Tương tự như trên thì Phong sẽ show code và chú thích cho các bạn dễ hiểu nhé.Ngoài ra bạn có thể xem thêm video bên dưới để nghe về cách phân tích bài nhé.Nhớ để lại comment nếu bạn gặp thắc mắc nhé.

@Override
	public void DFS(int i) {
		// Khong dung de quy
		int numberPoint = topNum();
		// stack de phong ngua truong hop quay lui
		Stack stack = new Stack();
		// list de luu danh sach duong di da qua
		ArrayList listVisit = new ArrayList<>();
		// arr danh dau da qua
		int[] visit = new int[numberPoint];
		// dau tien add dinh da cho vao
		visit[i] = 1;
		listVisit.add(i);
		stack.push(i);
		// chung nao stack con la ok
		while (!stack.empty()) {
			// bien count de kiem tra khi nao can lay phan tu ra khoi stack
			int count = 0;
			i = stack.peek();
			// duyet va kiem tra
			for (int j = 0; j < visit.length; j++) {
				if (this.matrixA[i][j] > 0 && visit[j] == 0) {
					// neu ok thi them vao list di qua
					listVisit.add(j);
					visit[j] = 1;
					stack.push(j);
					// nếu thêm rồi thì dừng lại theo quy tắc cuộn
					break;
				} else {
					count++;
				}
			}
			if (count == visit.length) {
				stack.pop();
			}
		}
		// in ra duong di
		toString(listVisit);
	}

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :