One, foreword

Today, a friend of mine made me a screenshot of the company’s disgusting need to expand (tiled) a large nested list into a level list, and then, after a bit of writing, show it to me. Don’t give me a look it doesn’t matter, a look to me, I immediately small anger, this is dry for many years to write the code? Without further ado, first on the picture:

Depth First Search (DFS)

If you have studied “Data Structure” in your freshman year, I remember it was published by Tsinghua University (originally with a purple cover), now it may have changed the N edition. In this book, after learning binary trees, we learned stack, heap, then DFS/BFS, and then Graph.

Because graphs are difficult (divided into undirected graphs and directed graphs), I first learn DFS/BFS. Graphs are widely used (small to community convenience building, large to urban road planning, high-speed railway stations, etc.). Therefore, mastering DFS is very useful for understanding graphs at least.

So with all that said, what is DFS? Let’s start with a picture:

If we want to traverse the structure completely (all paths, each node can only be accessed once), we do this:

  • A -> B -> E (depth preference);
  • A -> B -> C -> D;

Two priority ideas:

  • Depth first is simple: follow a path until there are no more.
  • Breadth-first means that all children of the current node are traversed first (children of A are B, C and D); Then, the child nodes of the child node are traversed in turn.

Obviously, the above diagram is easier and faster for us to use DFS:

  1. A -> B -> E;
  2. C -> F -> G -> H -> D;

End when A is encountered;

3. Optimize code logic based on DFS

Let’s take a screenshot of the code to understand the data structure:

  • Projects is a list, and each element is sites;
  • Sites is also a list. Each element is countries;
  • Countries are also lists, with each element containing locals and currencies;

Expand the list to form a list, with each object containing:

[
    {
        project: project.name,
        siteId: site.siteId,
        countryCode: country.countryCode,
        localCode: local.localCode,
        currencyCode: currency.currencyCode,
        host: site.host
    },
    ......
]
Copy the code

The idea is to start from scratch and iterate all the way to the leaf node, country, which is as simple as that. I gave a DFS demo and didn’t help him write this logic.

<! DOCTYPE html><html>
<head>
	<title>test</title>
</head>
<body>

	<script type="text/javascript">
                 // DFS
		function combines (obj, kvs = [], list, comb = {}) {
                        // If KVS is 0, the leaf node has been reached
                        // Add to the list, return to the previous level, continue DFS
			if (kvs.length === 0) {
				list.push(Object.assign({}, comb));
				return;
			}

                        // Remove the first element from KVS (KV)
			const keyAndValue = kvs.shift();
			let k = Object.keys(keyAndValue)[0], v = keyAndValue[k];

			const data = obj[k];
			if (Array.isArray(data)) {
                                // Depth traversal
				for (let i = 0; i < data.length; i ++) { comb[v] = data[i][v]; combines(data[i], kvs, list, comb); }}// To return to the upper level, we need to put the kv back at the top of the array
                        // If the next element is traversed, KVS will be empty (because KVS is index pass, not value copy pass)
			kvs.unshift(keyAndValue);
		}

		// Construct test data
		var ks = ['project'.'site'.'city'];
		function genData (index) {
			let list = [];
			for (let i = 0; i < 10; i ++) {
				var obj = {};
				obj[ks[index] + 'Id'] = Math.random();
				if (index+1 < ks.length) {
					obj[ks[index+1] + 's'] = genData(index+1);
				}
				list[i] = obj;
			}
			return list;
		}

                // construct large objects, respectively nested ks
		var o = {projects: genData(0)};

		// Tiled into a list list
		var list = []
                // Convert o to list
		combines(o, [{projects: 'projectId'}, {sites: 'siteId'}, {citys: 'cityId'}], list)
		console.log(list);
	</script>
</body>
</html>
Copy the code

Of course, the algorithm was just for my friend to look at, but actually she had to modify a bit of KVS to suit her own needs.

Here DFS is the most simple, the most basic, and does not consider the data duplication, to “prune” the situation, because the actual project does not exist friends constructed data is repeated.

In order to really learn DFS and master it, there is still a certain difficulty, look at the algorithm questions, want to practice more to gradually master!