Tree Traversal — Graph Theory in Action Pt.1
Graph theory is taught in most computer science courses. But have you ever used it in the real world? Graph theory is one of the most beautiful things I have ever seen, so I want to prove that it’s is not only exist in university or leetcode. In this series, I will give some common problems in the real world, and try to solve them using graph theory.
One day I was asked to implement a photo upload system, which is pretty simple until my boss told me one thing: Please support ZIP. This requirement completely changed my thought implementation. How to handle sub-directory? How to handle sub-sub-directory?
I then intermediately search any existing ZIP extraction library in the market and found that most of the libraries support these functions:
.getNextEntity() — get the node of the file/directory
.read() — read the file content of the entity
.isDirectory() —determine whether an entity is file or directory
This kind of structure let me think of the graph. A directory can have a list of entities(file/directory). And a file is just a file, no other entities belong to it. Therefore, directory is intermediate node, while file is the leaf node. Once we see the problem in this framework, we can immediately realize that this is nothing but a tree traversal problem — To get all the photos in a zip file, we only need to visit all the leaf nodes.
Commonly used algorithms for tree traversal would be DFS and BFS. In our case, both DFS and BFS would have no difference. It is because we need to visit all the leaves and no early stop can be applied, the number of iteration would be the same in DFS and BFS.
As a result, I just randomly pick an algorithm(DFS) to demonstrate the idea. Below is a pseudo code for retrieving all the images:
stack <- { root of the zip entity }
result_set <- empty setwhile(Stack is not empty) {
curr_entity <- stack.pop()
if (curr_entity.isDirectory()) {
stack.push(curr_entity.getAllChildren())
} else {
if (curr_entity is image) result_set.add(curr_entity)
}
}
If you find this article helpful, please click the clap button and share it to your friends. If you have any topic or idea on how to utilize graph theory in daily life, feel free to leave the comment on the comment section below. Thanks :-)
