图与树入门 | 图论

图

树是一种特殊（简化）的图

算法中的图是指一些点和连接这些点的边组成的集合。

将这张图上点的集合记作 $V$ ，边的集合记作 $E$ ，然后图集合记作 $G = (V, E)$ 。

根据边是单向可通的还是双向可通的，将边分为有向边和无向边，并以此区分图为有向图和无向图。

图的存储和遍历

vector

不妨设点的集合是 $1 \sim n$ ，简单的方式是将一条边存在 vector 中

如果存在一条从 x 到 y 的边，那么将节点 y 插入以 x 为下标的 vector 中。

cpp

vector<vector<int> > eg(n+1);
for(int i=1;i<=m;++i)
{
	int x,y;cin>>x>>y;//存在从 x 到 y 的边
	eg[x].emplace_back(y);
    eg[y].emplace_back(x);//如果是无向边
}

如果这条边还有其他信息，比如边的长度，那么将 vector 中的数据类型从 int 变成结构体或者是多元组。

cpp

typedef array<int,2> pr;//二元组
vector<vector<pr> > eg(n+1);
for(int i=1;i<=m;++i)
{
	int x,y,v;
    cin>>x>>y>>v;//存在从 x 到 y 的边，长度为 v
	eg[x].emplace_back(pr{y,v});
    eg[y].emplace_back(pr{x,v});//如果是无向边
}

当遍历整张图时，从一个点出发，假设采用 $d f s$ 方式：

cpp

void dfs(int now)//从 now 点出发
{
	vis[now]=1; //该点已经访问过
    for(int t:eg[now])//访问从 now 出发能到大的点
    {
        if(vis[t]) continue;
        dfs(t);
    }
}

vector 是最常用的存边方式。

该遍历时间复杂度是 $O (n + m)$

邻接矩阵

第二种方式是邻接矩阵，直接开一个 $n * n$ 的矩阵，其中 $e g [x] [y]$ 里面存的就是从 $x$ 到 $y$ 的边的距离

cpp

for(int i=1;i<=m;++i)
{
	int x,y,v;
	cin>>x>>y>>v;
	eg[x][y]=v;
}

遍历时类似

cpp

void dfs(int now)//从 now 点出发
{
	vis[now]=1; //该点已经访问过
    for(int t=1;t<=n;++t)
    {
        if(vis[t]||eg[now][t]==0) continue;
        dfs(t);
	}
}

邻接矩阵的好处是写法简单，但是遍历起来是 $O (n^{2})$

树

树是一种特殊的图，满足 $| E | = | V | - 1$ ，即边刚好比点少一个且整张图连通。

根据鸽巢原理也可以发现，任意两个点之间有且仅有一条路径。

树分为有根树和无根树，区别在与是否钦定一个节点为树的根节点。

以下一些概念基于有根树的前提下：

深度：某个节点和根节点之间的节点数量。

儿子：与该节点相连的，远离根节点方向的点。

父亲：与该节点相连的，靠近根节点方向的点。

祖先：该节点与根节点路径上的点（不包括自己）

子树：儿子以及儿子的儿子们的集合

最近公共祖先：任意两个点的共同祖先中深度最深的节点

P5908 猫猫和企鹅

特殊的树

二叉树：每个节点最多有两个子节点

二叉树本身只是一种普通的树，但是当赋予树一些特殊意义时，二叉的性质很契合二分的性质，所以它很常用。

二叉树还有一些更细节的定义，不罗列了。

链：所有点连成一条链

特点是树的深度很大，每个节点的子节点数量是 $0, 1, \dots, n - 1$ ，累加是 $O (n^{2})$ 级别的

如果算法与子节点数量相关要考虑这种图

菊花图：所有节点都直接与根节点相连

特点是节点儿子数量特别多，如果算法是与儿子节点的数量的平方相关要特别考虑

树的遍历

普通树

cpp

void dfs(int now,int fa)
{
	for(int t:eg[now])
    {
        if(t==fa) continue;//父亲
        dfs(t,now);
	}
}

使用深度优先搜索时，优先按照一条链的向下遍历

使用广度优先搜索时，按深度逐层遍历

二叉树：

可以用 son[now][0/1] 分别表示二叉树和左和右两个儿子

对于二叉树有几种特别的遍历方式：

先序遍历：在遍历二叉树时，将遇到的节点以：先写自己，再写左儿子，再写右儿子的方式记录下来

中序遍历：在遍历二叉树时，将遇到的节点以：先写左儿子，再写自己，再写右儿子的方式记录下来

后序遍历：在遍历二叉树时，将遇到的节点以：先写左儿子，再写右儿子，再写自己的方式记录下来

cpp

void dfs(int now)
{
    //先序
    cout<<now<<' ';
	if(son[now][0]!=0) dfs(son[now][0]);
    if(son[now][1]!=0) dfs(son[now][1]);
    //不同的遍历序只是这三行语句顺序的区别
}