↵
# 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:↵
↵
1. tree edges:edges from father nodes to its son;↵
2. back edges:edges from a node to its ancesters;↵
3. forward edges:edges from a node to its subtrees but not a tree edge;↵
4. bridges:edges from a node to another node,neither its ancesters or in its subtrees,but visite
↵
# 1.Theory↵
↵
We define that $\operatorname{f}(n,a,b,c) = \lfloor \frac{A\cdot i + B}{C}\rfloor$, we found that:↵
↵
$$↵
\begin{aligned}↵
↵
\operatorname{f}(n,a,b,c) &= \lfloor \frac{A\cdot i + B}{C}\rfloor\\↵
&= \sum_{i = 1}^n \sum_{j = 1}^{\infty} [\lfloor \frac{A\cdot i + B}{C}\rfloor \ge j]\\↵
&= \sum_{j = 1}^{\infty} \sum_{i = 1}^n [\lfloor \frac{A\cdot i + B}{C}\rfloor \ge j]↵
\end{aligned}↵
$$
↵
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:↵
↵
1. 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.↵
2. 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: [user:OtterZ,2025-09-10]
