Thuật toán duyệt theo chiều sâu (Depth-First Search - DFS) là phương pháp khám phá hoặc tìm kiếm trên cây hoặc đồ thị. Thuật toán này sẽ đi sâu nhất có thể theo nhánh của cây. Khi tất cả các cạnh liên quan đến nút v đã được kiểm tra, quá trình sẽ quay lại nút gốc tạo ra cạnh đó. Quy trình này tiếp tục cho đến khi tất cả các nút có thể truy cập từ nút nguồn được khám phá. Nếu vẫn còn nút chưa được kiểm tra, thuật toán sẽ chọn một nút khác làm nguồn và lặp lại quy trình cho đến khi tất cả các nút đều được xử lý.

Bài viết này sẽ giới thiệu ứng dụng cơ bản của thuật toán DFS trong thực tiễn phát triển.

const dataList = [
    {
        "name": "Ngành sản xuất và cung cấp khí đốt",
        "children": [
            {
                "name": "Ngành sản xuất và cung cấp khí đốt",
                "children": [
                    {
                        "name": "Ngành sản xuất và cung cấp khí thiên nhiên"
                    },
                    {
                        "name": "Ngành sản xuất và cung cấp khí hóa lỏng"
                    },
                    {
                        "name": "Ngành sản xuất và cung cấp khí ga"
                    }
                ]
            },
            {
                "name": "Ngành sản xuất và cung cấp khí sinh học",
                "children": [
                    {
                        "name": "Ngành sản xuất và cung cấp khí sinh học"
                    }
                ]
            }
        ]
    },
    {
        "name": "Tổ chức quốc tế",
        "children": [
            {
                "name": "Tổ chức quốc tế",
                "children": [
                    {
                        "name": "Tổ chức quốc tế",
                        "children": [
                            {
                                "name": "Tổ chức quốc tế"
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

Dựa trên dữ liệu trên, chúng ta cần xóa các đối tượng có thuộc tính name trùng lặp, với điều kiện: nếu đối tượng bị xóa có dữ liệu con thì vẫn giữ nguyên dữ liệu con.

Cách triển khai rất đơn giản, như sau:

function loaiBoGiaTriTrung(data) {
    const daTruyCap = new Set()

    function duyetCay(cay) {
        for (let i = 0; i < cay.length; i++) {
            const nutCay = cay[i]

            // Nếu giá trị đã từng xử lý, đánh dấu là nút trùng lặp
            if (daTruyCap.has(nutCay.name)) {

                // Nếu nút có dữ liệu con, chuyển toàn bộ dữ liệu con vào danh sách
                if (nutCay?.children?.length) {
                    cay.push(...nutCay.children)
                }

                // Xóa nút trùng lặp khỏi cấu trúc
                cay.splice(i, 1) && i--
            } else {
                // Ghi nhận giá trị đã xử lý
                daTruyCap.add(nutCay.name)

                // Duyệt đệ quy các nút con
                if (nutCay?.children?.length) {
                    duyetCay(nutCay.children)
                }
            }
        }
    }

    duyetCay(data)

    return data
}

Kiểm tra kết quả:

const ketQua = loaiBoGiaTriTrung(dataList)

console.log('ketQua: ', JSON.stringify(ketQua, null, '\t'));

ketQua:  [
	{
		"name": "Ngành sản xuất và cung cấp khí đốt",
		"children": [
			{
				"name": "Ngành sản xuất và cung cấp khí sinh học",
				"children": []
			},
			{
				"name": "Ngành sản xuất và cung cấp khí thiên nhiên"
			},
			{
				"name": "Ngành sản xuất và cung cấp khí hóa lỏng"
			},
			{
				"name": "Ngành sản xuất và cung cấp khí ga"
			}
		]
	},
	{
		"name": "Tổ chức quốc tế",
		"children": []
	}
]

Yếu tố then chốt là sử dụng Set để ghi nhận các giá trị đã xử lý, và thực hiện thao tác tương ứng dựa trên điều kiện. Xong rồi!