When should we construct trees, graphs to analyse an algorithm?

Question

In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to put things analysed in them and use those structures to describe the property of the research object and prove some property of the structures to finally give an explanation why it works well...

When should we use trees, graphs to analyse an algorithm? Or equivalently, what property do trees or graphs do well in describing in theory?

Like, in sort algorithms, many algorithms are analysed with a binary tree, in 2SAT algorithms, the core of the problem is decribed as a graph.

Well, for the problems with fixed mode, the structures can be implied easily, like the problems in OI or leetcode, however, in research such situation is not so likely to happen.

If the best probably answer is: well, when you feel some structures are proper, you can try them, it is hard to say which must be used and which shouldn't. I accept it. I look forward to a more inspiring answer.

Answer 1

The answer could be like a promo for data structures course!

You probably studied data structures within the study of a programming language, not in an abstract manner.

You should know the main characteristics of a data structure and that of ur problem to choose the most suitable one for it(by suitable we usually mean efficient in time&space complexity of main operations, and hopefully meaningful too I mean easy to understand the representation)

For example u use BST if u want fast search/insert (O(log n)), then u may prefer AVL trees if worry about worst case and want to keep the tree balanced; prefer Hu-Tucker OAT if u think the difference of frequency between ur search items is considerable that it has an impact on the performance. Huffman trees for coding, hash tables if ur items r scattered in the range and u want fast search/insertion (const in av),.... B-trees, B+-trees,... The same goes for choosing bet arrays, linked lists, stacks,....

You may have a look at knuth The art of Computer Programming, Vol 3 Searching & Sorting

Then u may move on more practical problems and consider the nature & relations between ur elements. Choose trees if they have a Hierarchical nature, graph if the connection varies, and vertices or edges may have values to represent cost or profit; sometimes u might rethink about ur choice which data to put vertices and which as edges, in this case u think of the problem u r solving and the performance of the well known algorithms u r going to map it to in each case to make ur choice.

I hope this was helpful

Answer 2

There's no hard-and-fast rule. Use them if they are useful; don't if they are not. As a broad guideline:

Graphs are often useful when you have relationships between a pair of items.

Trees are often useful when you have a hierarchical relationship.