Thao tác với cạnh trong đồ thị

25/10/2017

Xin chào mọi người nè,

Như vậy là mình đã đến được bài thứ 3 rồi phải hông nè,ở 2 bài đầu chúng ta đã biết cách load dữ liệu lên nè,rồi thiết kế abstract class nữa.Rồi bây giờ thì ta sẽ đi sâu vào vấn đề một chút.Ở bài hôm nay ta sẽ hiện thực một phương thức đầu tiên,khá là quan trọng đó là phương thức thêm cạnh và xóa cạnh ở cả 2 loại đồ thị vô hướng và có hướng.

Link 2 bài học lần trước cho những bạn chưa xem kịp nè,ahihi:

Load data từ file lên mãng 2 chiều.
Thiết kế abstract class như thế nào là phù hợp?

Hii,không dài dòng nữa nè,ta vào vấn đề nhé.
Rồi ta có một số quy ước như thế này,trong quá trình làm việc với mãng ma trận kề của đồ thị thì ta quy ước tất cả phần tử trong mãng chỉ có giá trị 0 và 1 thôi nhé (đôi khi ở vô hướng có cả giá trị là 2 nữa). Như vậy khi giá trị là 0 thể hiện cho 2 đỉnh này không có cạnh.Và ngược lại 1 là thể hiện cho 2 đỉnh kề này có cạnh nối với nhau. Rồi.Như vậy thì giờ đặt tay lên tim và nói mọi chuyện đều ổn được rồi.ahihi.
Khi chúng ta nghĩ đến việc thêm một cạnh,chúng ta sẽ nghĩ làm thế nào đó để số 0 biến thành số 1 là ok.Có phải như vậy không nè?Và ngược lại xóa cạnh thì chỉ việc biến số 1 thành số 0 thôi.ahihi.Dễ hiểu mà.
Tiếp theo ta suy nghĩ đến cái mình vẫn hay làm là hỏi bản thân mình xem,cái phương thức đó nhận vào,trả về và nhiệm vụ là làm gì? Để từ đó ta viết phương thức cho dễ nhé.
Đầu tiên nói cái dễ trước.Ai cũng biết phương thức thêm cạnh để thêm cạnh và ngược lại là xóa cạnh để xóa cạnh.Tiếp theo,giá trị trả về là gì?Ở đây mình nghĩ kiểu trả về ok nhất có lẽ là boolean,đôi lúc ta cũng có thể trả về mãng ma trận kề mới.Tùy vào cách sử dụng.Ở bài này mình sẽ trả về boolean.
Rồi để thao tác với cạnh,có nghĩa là đụng chạm đến 2 cái đỉnh,vì vậy mà giá trị truyền vào chắc chắn là 2 cái đỉnh rồi,chứ còn gì nữa.hehe.

Như vậy,sau hồi phân tích,ta có thể viết được rồi:
Tuy nhiên các bạn xem video ở bài trước để biết thêm một vài cái mình chưa viết ra bloger nha.hii,mong mấy bạn thông cảm. Ở lớp abstract:

// them mot canh
	public abstract boolean addEdge(int x, int y);

	// xoa mot canh
	public abstract boolean removwEdge(int x, int y);

Ở lớp con vô hướng:

@Override
	public boolean addEdge(int x, int y) {
		int vertexCount = topNum();
		if (x >= 0 && x < vertexCount && y >= 0 && y < vertexCount) {
		//Đồ thị vô hướng có ma trận kề là đôi xứng mà,làm như bên dưới thì khỏi phải sợ sai luôn
			this.matrixA[x][y] = 1;
			this.matrixA[y][x] = 1;
			return true;
		} else {
			return false;
		}
	}

	@Override
	public boolean removwEdge(int x, int y) {
		int vertexCount = topNum();
		if (x >= 0 && x < vertexCount && y >= 0 && y < vertexCount) {
			this.matrixA[x][y] = 0;
			this.matrixA[y][x] = 0;
			return true;
		} else {
			return false;
		}
	}

Ở lớp con có hướng:

@Override
	public boolean addEdge(int x, int y) {
	//Phương thức topNum() dùng để lấy đỉnh của đồ thị ấy các bạn
		int vertexCount = topNum();
		//Kiểm tra điều kiện thôi
		if (x >= 0 && x < vertexCount && y >= 0 && y < vertexCount) {
		//Vì là có hướng nên nó chỉ có một chiều,khác với vô hướng
			this.matrixA[x][y] = 1;
			return true;
		} else {
			return false;
		}
	}

	@Override
	public boolean removwEdge(int x, int y) {
		int vertexCount = topNum();
		if (x >= 0 && x < vertexCount && y >= 0 && y < vertexCount) {
			this.matrixA[x][y] = 0;
			return true;
		} else {
			return false;
		}
	}

Hii,Làm theo như vậy là ổn rồi nè,nếu các bạn chưa hiểu chổ nào thì vui lòng để lại comment nhé.Các bạn có thể xem video để tiện lợi hơn bạn nhé.


Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :