# Graph theory knowledge point all-star

Save rp before the NOIP exam.
Graph theory is a branch of mathematics, and graphs are the main research object of graph theory. A graph is a graph composed of a number of given vertices and edges connecting two vertices. This graph is usually used to describe a specific relationship between certain things. Vertices are used to represent things, and edges connecting two vertices are used to represent the relationship between two things. (This passage is excerpted)

### DFS(Depth First Search)

Depth-first search is a method that needs to be used to deal with many problems, and sometimes it is also used to obtain partial points. One of its major features is that it recursively calls itself, that is, it is implemented using a stack.

```typename dfs(int u,...)
{
if(conditions) return ...;
give Tag;
for(v to u)
{
if(visited) continue;
dfs(v);
details;
}
return ...;
}
```

The tree formed by DFS traversal is called a DFS tree, and the DFS tree has no horizontal inserts.

### BFS(Breadth First Search)

Breadth-first search, which prioritizes access to nodes in the current layer, is generally implemented using queues.

```typename bfs(int start_point,...)
{
queue<typename> Q;
Q.push_back(strat_point);
details;
while(!Q.empty)
{
u=Q.front();
details;
for(v to u)
{
if(visited) continue;
details;
Q.push_back(v);
}
}
return ...;
}
```

## tree problem

### tree diameter

The diameter of a tree is the longest simple path between any two points on the tree.

#### Twice DFS

Select a point randomly for the first time, find the node farthest from it; then start from this node, go to the deepest point. A simple path ending at these two nodes is the diameter of the tree.
Advantage: easy to implement

#### Tree DP

First assume that a point is the root, and for each node, maintain the longest path through the root and the longest path from the leaf to the root in the subtree rooted at it, and then transfer.
Advantages: Can be modified to achieve richer.

### LCA of nearest common ancestor

#### doubling jump

for each node. maintains all its \(2^i\) level ancestors \(i=0,1\dots \log n\) . When looking for the ancestors of two points, first jump the node with a larger depth to the same depth as the node with a smaller depth, and let the latter two nodes jump up to find lca at the same time.
Algorithm time complexity \(O(n\log n+Q\log n)\) , space complexity \(O(n\log n)\) .

#### tree profile

Firstly, the whole tree is divided into heavy chains. When the two nodes inquired are not in the same chain, select the node with a deeper depth at the top of the chain, jump to the parent at the top of the chain, and repeat this process until it is in the same chain. Returns the point with less depth.
Algorithm time complexity \(O(n+Q\log n)\) , space complexity \(O(n)\) .

#### ST table writing

Perform \(dfs\) on the entire tree once, and change it into a sequence of length \(2n\) with the depth as the first key and the node as the second key according to the access order, and preprocess the ST table for this sequence. The second keyword that is the minimum value of the query interval is queried each time.
Algorithm time complexity \(O(n\log n+Q)\) , space complexity \(O(n\log n)\) .

#### LCT writing method (basically there is no such thing)

Each node stores a two-tuple whose depth is the first key and number is the second key, and the second key with the minimum value on a chain is queried each time.
Algorithm time complexity \(O(n+Q\log n)\) , space complexity \(O(n)\) .

### center of gravity of the tree

For a node, if the size of each of its subtrees does not exceed the size of the tree, this point is the center of gravity of the tree.

#### dfs for center of gravity

DFS is to maintain the size of each subtree, you can get the size of all subtrees with each node as the root, and then judge.
Algorithm time complexity \(O(n)\) .

### minimum spanning tree

An undirected graph with edge weights and a minimum spanning tree becomes a minimum spanning tree.

#### Kruskal algorithm

Sort all the edges, add the smallest edges in turn, and maintain the connectivity of the graph with union search.
Algorithmic complexity \(O(m\log m+m \log n)\) .

#### Prim algorithm

First select a point, and then sequentially add to the connected block the point with the shortest distance to the connected block.
With heap maintenance, the complexity is \(O(n\log n+m\log n)\) .

### shortest path

#### Floyd's Algorithm

```memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=0;
for(int i=1;i<=m;i++) f[l[i].u][l[i].v]=f[l[i].v][l[i].u]=l[i].len;
for(int k=1;k<=n;k++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
f[u][v]=min(f[u][v],f[u][k]+f[k][v]);
```

#### SPFA

```struct edge{
int poi,len;
};
vector<edge> e[MAXN];
queue<int> Q;
int dis[MAXN],cnt[MAXN],vis[MAXN];
bool SPFA(int s)
{
memset(dis,0x3f,sizeof(dis));
int u=0;
dis[s]=0,vis[s]=true;
Q.push(s);
while(!Q.empty())
{
u=Q.front();
Q.pop(),vis[u]=false;
for(int k=0,lim=e[u].size(),v,w;k<lim;k++)
{
v=e[u].poi,w=e[u].len;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n) return false;
if(!vis[v]) Q.push(v),vis[v]=true;
}
}
}
return true;
}
```

#### Dijkstra's Algorithm

```typedef pair<int,int> pr;
vector<pr> e[MAXN];
long long dis[MAXN];
bool vis[MAXN];
priority_queue<pr,vector<pr>,greater<pr> > Q;
void Dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
Q.push(make_pair(0,s));
while(!Q.empty())
{
int u=Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u]=true;
for(auto ed:e[u])
{
int v=ed.first,len=ed.second;
if(dis[v]>dis[u]+len)
{
dis[v]=dis[u]+len;
Q.push(make_pair(dis[v],v));
}
}
}
return;
}
```

Tags: Algorithm

Posted by kaimason1 on Fri, 25 Nov 2022 06:07:16 +0300