图论1
目录
1.存储图、遍历图
存储图、遍历图
存储图（认识图）
先来认识什么是图，图是一种多对多的数据结构，比如说有1，2，3这三个点，且1与2，1与3，2与3之间都有一条没有方向的边联通，这就是一个无向图，连通图。如果1，2，3这三个点，1有一条通向2的单向边，2有一条通向3的有向边，这就是一个有向图，强连通图（有向图用强）。
在一张简单图中，也就是没有自环、重边的图。什么意思？自环就是自己到自己毫无意义，重边也是，1到2已经有一条无向边了，2到1又有一条无向边，这种就是重边。概念都知道了，那么接着说，在一张简单图中如果任意两点之间都有一条无向边或两条有向边，也就是任意两点之间都能直接到达的图，叫做完全图
一张空的图与一张完全图互为补图，什么是补图？对于一张图
怎么减？把两个图都有的边删去，剩下的那张图是G的补图，也可以说这两张图互为补图。
先说这么多，那么在c++中如何存储图？
1、邻接矩阵
假设有n个点那么就建一个n*n的数组
对于两个点u,v如果这两个点之间有连边（无向）那么
u,v如果这两个点之间有连边（有向，u可以去v，v不能去u）那么
好处是查询一条边是否存在时间复杂度仅为
但是所需的空间复杂度为
代码示例：
#include<bits/stdc++.h>
using namespace std;
const int N=1005; //点的个数
int g[N][N]; //图
int main()
{
int n,m;
cin>>n>>m; //n是点数，m是边数
while(m--) //请确保m在后面不会用到
{
int u,v,w; //u,v是点，w是边权看题目有些要有些不用，相当于过路费
cin>>u>>v; //cin>>u>>v>>w;
g[u][v]=1;
g[v][u]=1; //如果是有向图请删除这一行
}
return 0;
}
2、邻接表
一个新知识：vector
动态数组，根据你所需存储的元素数量开空间，具体原理是：先找一块大小为1的地方如果不够存，找一块大小为2的地方，并把之前的元素复制进去，还存不下找一块大小为4的地方，不断*2，所以在存
个元素时比较浪费。
邻接表的原理就是每一行是一个点，与他相连的点加入他这一行。
好处：大大减少空间复杂度
但是查询是否存在一条边要
的时间复杂度
代码示例
#include<bits/stdc++.h>
using namespace std;
const int N=1005; //点的个数上限
vector<int> g[N]; //图，你可以把两个维度都开成动态的
int main()
{
int n,m;
cin>>n>>m; //n是点数，m是边数
while(m--) //请确保m在后面不会用到
{
int u,v,w; //u,v是点，w是边权看题目有些要有些不用，相当于过路费
cin>>u>>v; //cin>>u>>v>>w;
g[u].push_back(v); //如果不知道这行是干嘛的可以查OI-wiki.org
g[v].push_back(u); //如果是有向图请删除这一行
}
return 0;
}
新手掌握这两种就够了
遍历图
事先声明:这里会分为BFS和DFS两种方法，如果有不懂的可以查询OI-wiki，在这个网站里点到图论相关里找。
在遍历图的时候BFS和DFS的时间复杂度近乎一致，不像平常BFS快很多。他们的时间复杂度都是
都是点数+边数，因为每条边、每个点都只会访问一遍。
dfs
深度优先搜索，原理是从一个点（如1）开始把他能到的所有点访问并标记，具体：
标记1，搜索下一个点比如说是3，那就标记3，再在3那里往下搜……
对于一张连通图只需要一次就能搜到所有的点。树是边数最少的连通图，关于最小生成树就是拓展的内容了
代码示例：
int vis[100005]; //标记数组，0是未访问，1是已访问
void dfs(int u)
{
for(auto it : g[u]) //迭代器，vector知识
{
int nu=it;
if(!vis[nu]) //没被访问过
{
vis[nu]=1; //标记
dfs(it); //访问
}
}
}
bfs
需要一个队列，里面存放的是等待访问的点，然后挨个访问。
打个比方：1，2，3，4这4个点，1到2有连边，1到3有连边，2到4有连边，3到4有连边。
从1开始，1入队，标记，访问1，删除1，2入队，3入队同时打上标记，访问2，删除2，4入队，打标记；访问3，删除3，因为4已经被标记了，所以不2次入队；最后访问4，删除4，因为2和3都被打上了标记所以不做任何操作；结束。
代码示例：
queue<int> q;
vector<int> g[5];
int vis[10005];
g[1].push_back(2); g[1].push_back(3);
g[2].push_back(4);
g[3].push_back(4);
bfs(1);
q.push(1);
void bfs()
{
while(q.size()) //while(!q.empty())
{
auto hd=q.front(); //访问
q.pop(); //删除
for(auto it:g[hd])
{
int nu=it;
if(!vis[nu]) //没被访问过
{
vis[nu]=1; //标记
q.push(nu); //入队
}
}
}
}
树
一种特殊的图，有
个点与
条边组成
是个连通图，也就是任意两点之间都能互相到达。一条链也是树，树是特殊的图，菊花图也是树，什么是菊花图？就是1通向2，1通向3，1通向4……
父亲节点与子节点
一棵树（从上往下看），它上面那个与它相连的点是他的父亲节点，同理也能知道什么是子节点。祖先节点是一种特殊的父节点，它不仅限于上面那一个，而是从根节点（没有父节点，最上面的）到他路径上的所有节点都是它的祖先节点。
兄弟节点：同1个父亲的若干个节点
根节点
一棵树一定有且仅有一个根节点。根节点是所有节点（自己除外）的祖先节点，根节点没有祖先。
叶子节点
叶子节点没有子节点，在一棵树的最下面，一棵树一定有叶子节点，数量不定。
树的深度
一棵树从根到每一个叶子节点所需的最多步数
树的直径宽度
树最宽的地方，同一层节点最多的地方，那一层有几个节点树的宽度就是几
树形图
树的样子，但是每条边是有向的，树与树形图就好像完全图与竞赛图的关系。
二叉树
每个节点最多有两个孩子，一般把左边那个孩子叫做左子，右边同理。
O
/ \
O O
/ \ / \
O O O O
左子树：以一个节点为例，他的左孩子为根的一棵树就是左子树，右边同理
本篇完，敬请期待第二篇。
满二叉树与完全二叉树
完全二叉树包含满二叉树，也就是说满二叉树是完全二叉树的一种特殊形态
理一下：树是特殊的图，二叉树是特殊的树，完全二叉树是特殊的二叉树，满二叉树是特殊的完全二叉树。
完全二叉树就是叶子节点只出现在最下面一层与次下层（倒数第二层），上面那颗就是。只有根结点的树是完全二叉树，空树也是完全二叉树（不确定，待指正）。同理这两个树也是二叉树。
满二叉树就是把一颗深度为
的二叉树放满，一共
个节点，上面那颗就是。
↑↑↑这里讲的只是最基础的内容
二叉树的遍历
不是c++中的遍历。
而是先序、中序、后序遍历
这个序怎么看呢？什么时候访问根就是什么序。
如：
根 左子树 右子树
就是先序
左子树 根 右子树
就是中序
后序一样。
怎么手写，不要求用代码实现。
最简单的方法（用先序举例）：
写上根，然后划线
1______ _______
12_ 3_
……
根据先序/后序和中序求另外一个序
一个重要的知识点。
以先序，中序举例
假设先序是1 2 4 3 5
假设中序是4 2 1 3 5
先序确定根是1，中序确定左子树是4 2，右子树是3 5，然后回到先序，左子树4 2中2是根，在确定2只有左子树可以直接画上4；右边回到先序3是根，只有右子树5，直接画上。
1
/ \
2 3
/ \
4 5
像这样画好以后，求后序方便许多
_ _1
_2_31
42351OK!