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

26/10/2017

Thêm và xóa đỉnh trong đồ thị

Xin chào các bạn nè:

Đến với bài viết ngày hôm nay,Phong sẽ giới thiệu các bạn phương thức cần hiện thực tiếp theo là phương thức thêm đỉnh và xóa đỉnh.

Ý tưởng:

Đối với phương thức xóa đỉnh,chúng ta quy ước trong ví dụ này là thêm một đỉnh cô lập.Nếu các bạn muốn thêm đỉnh bình thường,thì sao khi thêm đỉnh,các bạn gọi phương thức thêm cạnh.Hay trường hợp các bạn muốn thêm đỉnh ở giữa cũng vậy,nếu làm như vậy chúng ta phải thực hiện nhiều thao tác để chỉnh sửa lại mãng ma trận kề,thay đổi vị trí các đỉnh.Như vậy thì khá phức tạp.Ở mức độ đơn giản ta sẽ viết phương thức thêm đỉnh cô lập.

Khi ta xác định chức năng của phương thức là thêm đỉnh cô lập rồi bước tiếp theo là xác định giá trị truyền vào.Ở phương thức này khi ta thêm một đỉnh cô lập mặc định nó sẽ thêm vào cuối mãng ma trận kề.Như vậy ta không cần phải truyền giá trị vào.Tiếp theo nữa là giá trị trả về.Trong trường hợp này,tương tự như phương thức thêm và xóa cạnh thì giá trị trả về có thể là boolean hoặc là mãng giá trị mới.

Sau khi bàn về cách phân tích suy nghĩ rồi ta đến giai đoạn code thôi nào:

Thêm một lưu ý nữa là vì ở vô hướng và có hướng thì 2 thao tác này giống nhau.Nên phương thức này sẽ được viết vào lớp Graph các bạn nhé!

// them mot dinh
	public boolean addTop() {
	//Lấy ra số đỉnh của đồ thị
		int newTopNum = topNum() + 1;
		// dinh co lap
		try {
		//Khởi tạo mãng có số đỉnh mới
			int[][] a = new int[newTopNum][newTopNum];
			//coppy mãng cũ và trong mãng mới vừa tạo
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a.length; j++) {
					a[i][j] = this.matrixA[i][j];
				}
			}
			//Sau đó gán mãng mới này lại cho ma trận kề của đồ thị là xong
			this.matrixA = a;
			//Như vậy hàng và cột cuối cùng của mãng này sẽ có giá trị là 0 các bạn nhé
		} catch (Exception e) {
			return false;
		}
		return true;
	}
    //Tương tự như trên thì công việc xóa một đỉnh cô lập cũng khá dễ.Các bạn có thể tham khảo.
	public boolean removeTop() {
		int newTopNum = topNum();
		// dinh co lap
		try {
			int[][] a = new int[newTopNum - 1][newTopNum - 1];
			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a[i].length; j++) {
					a[i][j] = this.matrixA[i][j];
				}
			}
			this.matrixA = a;

		} catch (Exception e) {
			return false;
		}
		return true;
	}

Đến đay thì bài viết của mình cũng hết rồi.Mình chúc các bạn sớm làm được bài nhé. Bên dưới là link video.Nếu các bạn còn mơ hồ thì có thể xem để hiểu hơn.


Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :