When I was trying to solve ABC419G in the contest,I found myself wrongly use BFS tree instead of DFS tree and failed,that day I found it might be important to write a tutorial about different spanning trees to make it easier to know how to choose right spanning trees while we're managing to solve graphs problems especailly the creative problems nowadays.I'll write down what I know and might extend the blog due to comments.
DFS tree
The reason I write about DFS trees first is that DFS trees arethe most common for simple graphs problem.When The code tries to run dfs algorithm on a graph starting with a node,the edges that was used to visit new nodes appears to be a tree.
On undirected graphs,the edges is garenteed to connect from a node to its ancesters(back edges) or its sons(tree edges),making it easier to study undirected graphs problems.
And on directed paths,the edges turns to four kinds:
- tree edges:edges from father nodes to its son;
- back edges:edges from a node to its ancesters;
- forward edges:edges from a node to its subtrees but not a tree edge;
- bridges:edges from a node to another node,neither its ancesters or in its subtrees,but visited before the nodes.
it appears that dfs trees divides edges to at most four types,making it easier to study graphs.
Mininum/Maxinum Spanning Trees
Such spanning tree is another useful one, and there are multiple problems just let you to find out the tree.
On undirected graphs with weights on edges,Mininum Spanning trees are constructed using greedy algorithms,with two core features:
- Mininum spanning trees leads to adding smaller edges first,and for all edges with weight smaller than a number $$$k$$$,such tree get most edges than other spanning trees.
- Any edges out of mininum spanning trees can make a circle with the edges on trees,and the edge is the maxinum in the cycle.
Contractions and Block Forests
In an undirected graph,if you contract edge biconnected components,you will get a tree,if you found some useful features on edge bitconnected components,just think of what to do on trees and then it's easy for you to get the algorithms for all undircted graphs.
And for Block forest,while nodes connect with the virtual nodes that stands to verticle bitconnected components, makes a tree,that is also used to study catcus when all verticle bitconnected components are garenteed to be an edge or a cycle.
Center trees
Some problem might be easy if we do divide and conquer on a tree.But sometimes we have to make it an online algorithm.But when we make a center trees,things turns to be similar as divide and conquer on a tree.Just find a center and divides the tree into parts to build trees,then you will find the max depth on a center tree is $$$\operatorname{O}(\log n)$$$.
virtual trees
Virtual trees is a spanning tree on trees,which just contain significant nodes for some problems,making yourself focus on a similar tree with less nodes.
shortest paths tree
Merging shortest paths from one node to others can make a tree.The edges out of the tree is garenteed not to make the path shorter.
write at last
Main author: OtterZ
