图

基础定义

图由顶点 \((vertex, node)\) 和边 \((edge)\) 组成。顶点代表对象。在示意图中，我们使用点或圆来表示。边表示的是两个对象的连接关系。在示意图中，我们使用连接两顶点之间的线段来表示。顶点的集合是 \(V\)，边的集合是 \(E\) 的图记为 \(G =(V, E)\) ,连接两点 \(u\) 和 \(v\) 的边用 \(e=(u, v)\) 表示。

下图是一个简单图例子：

图的分类

图大体上分为 \(2\) 种。边没有指向性的图叫做无向图，边具有指向性的图叫做有向图。例如，好朋友的关系是互相的，那么就是有向图，学习新知是需要层层递进的，这就是有向图。

我们可以给边赋子各种各样的属性。比较具有代表性的权值。边上带有权值的图叫做带权图。在不同问题中，权值可以代表距离、时间以及价格等不同的属性。

无向图

两个顶点之间如果有边连接，那么就视为两个顶点相邻。相邻顶点的序列称为路径。起点和终点重合的路径叫做圈。任意两点之间都有路径连接的图叫做连通图。顶点连接的边数叫做这个顶点的度。

没有圈的连通图叫做树，没有圈的非连通图叫做森林。一棵树的边数恰好是顶点数 \(-1\)。反之，边数等于顶点数 \(-1\) 的连通图就是一棵树。
如果在树上选择一个顶点作为根，就可以把根提到最上面，而离根越远的顶点越往下安排其位置。这样的树叫做有根树。不过,对于无根树，有时选择适当的顶点作为根使之变成有根树，可以使问题得到简化。如果把有根树看作家谱图，则可以在顶点之间建立父子关系。也可以认为这是给边加上了方向。

有向图

以有向图的顶点 \(v\) 为起点的边的集合记作 \(E+(v)\)， 以顶点 \(v\) 为终点的边的集合记作 \(E_{(v)}\) 。\(E+(v)\) 叫做 \(v\) 的出度，\(E_{(v)}\)叫做边的入度。

图的储存

图的存储结构要存储图中的各个顶点本身的信息，以及存储顶点与顶点之间的关系，比较复杂。图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表等。

二叉树的遍历

遍历顺序

对于一棵树，它拥有自己的前序/中序/后序遍历。

假设有这样一颗树：

那么这棵树的遍历分别为：

前序遍历：\(L \to I \to N \to G \to A \to O \to B\)。（根节点 \(\to\) 左子树 \(\to\) 右子树）

void PreOrder(BtNode* ptr)
{
	if (ptr != nullptr)
	{
		cout << ptr->data << "  ";
		PreOrder(ptr->leftchild);
		PreOrder(ptr->rightchild);
	}
}

中序遍历：\(G \to N \to I \to A \to O \to L \to B\)。（左子树 \(\to\) 根节点 \(\to\) 右子树）

void InOrder(BtNode* ptr)
{
	if (ptr != nullptr)
	{
		InOrder(ptr->leftchild);
		cout << ptr->data << "  ";
		InOrder(ptr->rightchild);
	}
}

后序遍历：\(G \to O \to N \to A \to I \to B \to L\)。（左子树 \(\to\) 右子树 \(\to\) 根节点）

void PassOrder(BtNode* ptr) 
{
	if (ptr != nullptr)
	{
		PassOrder(ptr->leftchild);
		PassOrder(ptr->rightchild);
		cout << ptr->data << "   ";
	}
}

图的遍历

图的遍历思想是从指定一个顶点出发，开始访问其他顶点，不能重复访问（每个顶点只能访问 \(1\) 次），直至所有点被访问。

深度优先遍历

思想：从指定的第 \(1\) 个点开始，沿着向下的定点不重复的一直遍历下去，若走到尽头，退到上一个顶点，寻找附近有没有顶点，有而且不重复的话，接着遍历，否则退到上一个顶点。

inline void dfs(int now,int id){
	if(ans[now]) return;
	else ans[now]=id;
	for(auto i:v[now]) dfs(i,id);
}

广度优先遍历

思想：从指定的第 \(1\) 点开始，先寻找跟它直接相连的所有顶点，然后继续这几个顶点再次深入，每次搜寻的都是同一级别的。

图的储存

思想：用二维 vector 存入每一条有向/无向边的信息。

无向图：

int l,r;
cin>>l>>r;
b[l].push_back(r);
b[r].push_back(l);

有向图：

int l,r;
cin>>l>>r;
b[l].push_back(r);//l -> r

特殊的树

堆

是一种基础数据结构，主要应用于求出一组数据中的最大最小值

堆的性质

1. 堆是一颗完全二叉树

2. 堆的顶端一定是“最大”，最小”的，但是要注意一个点，这里的大和小并不是传统意义下的大和小，它是相对于优先级而言的，当然你也可以把优先级定为传统意义下的大小，但一定要牢记这一点，初学者容易把堆的“大小”直接定义为传统意义下的大小，某些题就不是按数字的大小为优先级来进行堆的操作的

3. 堆一般有两种样子，小根堆和大根堆，分别对应第二个性质中的“堆顶最大”“堆顶最小”，对于大根堆而言，任何一个非根节点，它的优先级都小于堆顶，对于小根堆而言，任何一个非根节点，它的优先级都大于堆顶。

4. 关于 STL

   对不起堆堆，其实那天我用的是 priority_queue

堆的常见操作：

插入

假设你已经有一个堆了，这个时候你如果想要给它加入一个节点怎么办，比如说 \(0\)？先插到堆底，然后你会发现它比它的父亲小啊，那怎么办？不符合小根堆的性质了啊，那就交换一下他们的位置。知道符合为止。

事实上堆的插入就是把新的元素放到堆底，然后检查它是否符合堆的性质，如果符合就丢在那里了，如果不符合，那就和它的父亲交换一下，一直交换交换交换，直到符合堆的性质，那么就插入完成了。

参考代码(STL)：

p.push(x);

正解：

void swap(int &x,int &y){int t=x;x=y;y=t;}//交换函数 
int heap[N];//定义一个数组来存堆
int siz;//堆的大小 
void push(int x){//要插入的数 
	heap[++siz]=x;
	now=siz;
	//插入到堆底 
	while(now){//还没到根节点，还能交换 
		ll nxt=now>>1;//找到它的父亲 
		if(heap[nxt]>heap[now])swap(heap[nxt],heap[now]);//父亲比它大，那就交换 
		else break;//如果比它父亲小，那就代表着插入完成了 
		now=nxt;//交换 
	}
	return; 
}

删除

怎么删除？在删除的过程中还是要维护小根堆的性质，如果你直接删掉了，那就没有堆顶了，这个堆就直接乱了，所以我们要保证删除后这一整个堆还是个完好的小根堆。首先在它的两个儿子里面，找一个比较小的，和它交换一下，但是还是没法删除，因为下方还有节点，那就继续交换，直到符合性质为止。

STL：

p.pop();//不能删除任意位置

正解：

void pop(){
	swap(heap[siz],heap[1]);siz--;//交换堆顶和堆底，然后直接弹掉堆底 
	int now=1;
	while((now<<1)<=siz){//对该节点进行向下交换的操作 
    	int nxt=now<<1;//找出当前节点的左儿子 
        if(nxt+1<=siz&&heap[nxt+1]<heap[nxt])nxt++;//看看是要左儿子还是右儿子跟它换 
        if(heap[nxt]<heap[now])swap(heap[now],heap[nxt]);//如果不符合堆性质就换 
        else break;//否则就完成了 
        now=nxt;//往下一层继续向下交换 
	}
}

并查集

定义

对于一个集合 \(S=\{a_1, a_2, …, a_{n-1}, a_n\}\) ，我们还可以对集合 \(S\) 进一步划分: \(S_1,S_2,\cdots,S_{m-1},S_m\) 我们希望能够快速确定 \(S\) 中的两两元素是否属于 \(S\) 的同一子集。

若 \(S=\{0,1, 2, 3, 4, 5, 6\}\)，如果我们按照一定的规则对集合 \(S\) 进行划分,假设划分后为 \(S_1=\{1, 2, 4\}, S_2=\{3, 6\}，S_3=\{0, 5\}\)，任意给定两个元素，我们如何确定它们是否属于同一子集？某些合并子集后，又如何确定两两关系？基于此类问题便出现了并查集这种数据结构。
并查集有两个基本操作：

Find: 查祖宗。
Union：合并祖宗。

Find

对于 Find 操作，我们只需要返回该元素所在树的根节点。所以，如果我们想要比较判断 \(1\) 和 \(2\) 是否在一个集合，只需要通过 \(Find(1)\) 和 \(Find(2)\) 返回各自的根节点比较是否相等便可。已知树中的一个节点，找到其根节点的时间复杂度为 \(O(D)\)，\(D\) 为节点的深度。

对于树的根节点，我们规定其元素值为其本身（即父节点为自己）。

小优化：每次查找记忆化储存一个节点的根，大大降低时间复杂度。

参考代码：

inline int find(int x){
	if(tree[x].father!=x)
		tree[x].father=find(tree[x].father);
	return tree[x].father;
}

Union

把一个节点的祖宗改为合并它的那个点的祖宗即可。

参考代码：

if(find(x)!=find(y)){
	tree[find(y)].father=x;
}

最短路算法

Floyd

dp 思想，时间复杂度 \(O(n^3)\)。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int f[MAXN][MAXN],m,n;

int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	memset(f,0x3f3f3f,sizeof(f));
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int i=1;i<=m;i++){
		int l,r,w;
		cin>>l>>r>>w;
		f[l][r]=f[r][l]=w;
	}
	for(int i=1;i<=n;i++){
		for(int l=1;l<=n;l++){
			for(int r=1;r<=n;r++){
				f[l][r]=min({f[l][r],f[l][i]+f[i][r]});
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<f[i][j]<<' ';
		}
		cout<<endl;
	}
	return 0;
} 

dijkstra

本质是贪心，时间复杂度 \(O(n^2)\)，优先队列优化后降为 \(O(m \log m)\)。

#include<bits/stdc++.h>
using namespace std;
const int MAXM=5e5+10;
int n,m,s,u,v,w,ans[MAXM],head[MAXM],tot;
bool vis[MAXM];
struct edge{
	int next;
	int to;
	int dis;
}d[MAXM];
inline void add(int l,int r,int w){
	d[++tot].next=head[l];
	d[tot].to=r;
	d[tot].dis=w;
	head[l]=tot;
}
priority_queue<pair<int,int> >q;
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;i++) ans[i]=INT_MAX;
	ans[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=true;
		for(int i=head[x];i!=0;i=d[i].next){
			int t1=d[i].to;
			if(ans[d[i].to]>ans[x]+d[i].dis){
				ans[d[i].to]=ans[x]+d[i].dis;
				q.push(make_pair(-ans[d[i].to],d[i].to));
			}
		} 
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}

SPFA

这里有一句名言：

关于SPFA，它____________？

类广搜的写法，好处在于能够判断负权。

但有时候会直接被卡趋势。

bool spfa(){
    queue<int > q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i] = true;
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        st[u] = false;
        for(int i=0;i<g[u].size();i++){
            auto j = g[u][i];
            if(dist[j.first] > dist[u] + j.second){
                dist[j.first] = dist[u] + j.second;
                cnt[j.first] = cnt[u] + 1;
                if(cnt[j.first] >= n)return true;
                if(!st[j.first]){
                    st[j.first] = true;
                    q.push({j.first});
                }
            }
        }
    }
    return false;
}

最小/大生成树

我们定义无向连通图的最小生成树为边权和最小的生成树。

这里有两种算法，Kruskal 和 Prim，由于 Prim 复杂，详细介绍 Kruskal。

Kruskal

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

算法虽简单，但需要相应的数据结构来支持……具体来说，维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。

抽象一点地说，维护一堆 集合，查询两个元素是否属于同一集合，合并两个集合。

其中，查询两点是否连通和连接两点可以使用并查集维护。

如果使用 \(O(m \log m)\) 的排序算法，并且使用 \(O(m\alpha(m,n))\) 或 \(O(m \log n)\) 的并查集，就可以得到时间复杂度为 \(O(m \log m)\) 的 Kruskal 算法。

参考代码（并查集）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e3+10,MAXM=2e5+10;
struct edge{
	int u;
	int v;
	int w;
}t[MAXM];
int f[MAXN],n,m,x,y,z,ans,tot;
bool flag=0;
bool cmp(edge a,edge b){
	return a.w<b.w;
}
inline int find(int x){
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
inline bool smalltree(){
	for(int i=1;i<=m;i++){
		int fu=find(t[i].u);
		int fv=find(t[i].v);
		if(fu==fv) continue;
		ans+=t[i].w;
		f[fu]=fv;
		tot++;
		if(tot==n-1) return cout<<ans,0;
	}
	return cout<<"orz",0;
}
signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		t[i].u=x;
		t[i].v=y;
		t[i].w=z;
	}
	sort(t+1,t+m+1,cmp);
	smalltree();
	return 0;
}

完结。