关于图的一些定义
·图：由两个集合{V,E}所组成，记作G(V,E) • V是图中顶点(Vertex)的非空有限集合。 • E是图中边(Edge)的有限集合。 • 这里只考虑简单图：无自环、无重边（平行边） • 子图(subgraph)：边的子集，以及相关联的点集 
←无向图
←有向图，* {v2,v4}是一个子图
·顶点的度：
• 在无向图中，顶点的度就是其邻接点的数目； • 在有向图中，指向这个顶点的弧的数目，称为此顶点的入度。而此顶点指向其他 顶点的弧的数目，称为此顶点的出度。该顶点的度则是此顶点的入度与出度之和。
·带权图：在图的边/弧上加上一个相关联的权(weight)，为带权图.
·完全图：图中任意2个顶点之间都有边/弧相连 • 对于无向图/有向图，有(N(N-1))/2、 N(N-1)条边/弧 • 完全子图称为团(clique)
• 邻接(adjacent)：在无向图中，如果边(u,v)∈E，则u和v互为邻接点。 在有向
图中，如果弧<u,v>∈E，则v是u的邻接点。• 路径(path)：图中一个顶点序列称路径，路上相邻顶点都是邻接的。如v到v’的路径为(v=V0， V1， V2， …， Vn=v’)，
并且<V0,V1><V1,V2>…<Vn-1,Vn>∈集合E。 • 如果顶点和边都不重复出现，则称为简单路径。 • 除了起点和终点相同外没有重复顶点的路径，称为环(cycle)。
• 连通(connected)：如果无向图中任意两点都有路径，则称图是连通的，否 则是非连通的。非连通图有多个连通分量。 • 如果有向图中任意两点都有相互可达的路径，则称此图为强连通图。相互 可达则属于同一个强连通分量(SCC)。
树与生成树
• 连通无环图即为树(tree)• 树的集合称为森林(forest)• 生成树/森林: 包含图G所有点的树/森林• 一个图G是树当且仅当以下任意一个条件成立： • G有V-1条边, 无环 • G有V-1条边, 连通 • G连通, 但任意删除一条边后不连通 • G无环，但任意添加一条边后包含环 • 任意两点只有唯一的简单路径
• 满二叉树：除最后一层全是叶子结点之外，其他每层的结点都为2度结点。• 完全二叉树： 至多只有最下面的两层结点度可以小于2，其余各层都必须为2度结点，并且底层的结点都集中在该层最左边的若干位置上。• 高度：某个结点->叶子结点的最长路径边数；二叉树的高度为根的高度• 中间结点高度 = max{ 左孩子高度，右孩子高度}+1• 深度（层数） ：某个结点->根的路径边数；二叉树的深度为所有结点深度的最大值• 假设根为第0层， 在二叉树的i层上至多有2i个结点• ->推论：深度为k（第0…k层） 的二叉树最多有2k+1 - 1个结点• 对于任何一棵非空二叉树，如果叶结点个数为n0，度为2的结点个数为n2，则有： n0 = n2 + 1• ->推论： 在满二叉树中，叶结点的个数比其他结点个数总和多1
树的深度优先遍历(DFS)
• 先序遍历：若二叉树不空，则先访问根；然后先序遍历左子树；最后先序遍历右子树。• 中序遍历：若二叉树不空，则先中序遍历左子树；然后访问根；最后中序遍历右子树• 后序遍历：若二叉树不空，则先按后序遍历左子树；然后后序遍历右子树；最后访问根。PreOrder(T) = Root(根) + PreOrder(左子树) + PreOrder(右子树)MidOrder(T) = MidOrder(左子树) + Root (根) + MidOrder(右子树)PostOrder(T) = PostOrder(左子树) + PostOrder(右子树) + Root (根)
↑ ↑ ↑· 先序遍历： DBACEGF· 中序遍历： ABCDEFG· 后序遍历： ACBFGED
稀疏图/稠密图
• 边数E和V(V-1)/2相比非常少（E、 V同数量级）的称为稀疏图
• 时间复杂度为O(ElogE)的算法和O(V2)的算法对于稀疏图来说前者好, 稠密图来说后者好
• 一般来说, 即使对于稀疏图, V和E相比都很小, 可以用E来代替V+E, 因此O(V(V+E))可以简写为O(VE)
稀疏图/稠密图
欧拉路径
•遍历图G(V,E)，只通过每条边一次的路径叫做欧拉路径；如果这条路径的起点和终点是同一点，称做欧拉回路．
欧拉路径的判定
* 判定是否存在欧拉回路 无向图: 连通，所有点都是偶数度 有向图: 连通，所有点出度=入度
• 无向图• 图G有一条欧拉路径， 当且仅当G是连通的，且有0个或2个奇数度结点。当 所有点是偶数度时欧拉路起点可以是任意点；当有两个奇数度点时起点/ 终点必须是奇数度点。• 有向图• 图连通， 所有点出度=入度， 或者有1个终点的入度-出度=1， 有1个起点的 出度-入度=1。当所有点出度=入度时任意点可作为起点；而后者必须以出 度-入度=1的点做起点，入度-出度=1的点做终点。
图的输入方式
• 图一般以边的列表形式输入（给出点数N，边数M；然后给出每 条边的起点、终点、权值）
图的存储方法1 – 邻接矩阵
• 将顶点编号为1～N， 图可以用一个N×N的二维数组（矩阵） 表示： G[N][N]；
图的存储方法2 - 邻接表
• 邻接表是一种顺序（静 态）和链式（动态）相 结合的存储结构。
• 在邻接表中，对图中每 个顶点u建立一个关于边 的动态数组，包含了顶 点u的所有出边。
图的存储方法2 - 邻接表
• 邻接表是一种顺序（静态） 和链式（动态） 相结合的存储结构。• 开1个vector的数组Adj表示邻接表，每个顶点u对应其中一个vector（动 态） ，包含了顶点u的所有出边（Edge） 。 vector中的Edge由2个域组成： v(终点), w(边权)。
struct Edge
{
//将边定义成结构体Edge int v,w;//边的终点v和边权w Edge(int v1, int w1): v(v1),w(w1){};//构造函数};
vector<Edge> Adj[5005];//关于Edge的vector数组，数组中每个元素都是由Edge组成的vector， Adj[i]代表vi的所有出边Edge组成的vector
对一个图来说， 邻接表不是唯一的， 它取决
于建立邻接表时， 结点在每个单链表中的插 入策略。
1. 在邻接表上， 若要判定任意两
个顶点(vi和vj)之间是否有边/弧 相连， 则需搜索第i个或第j个链表 (O(V)时间)， 不及邻接矩阵(O(1) 时间)方便。2. 对于有向图， 其邻接表中第i 个单链表长度就是此结点的出度； 对于无向图， 其邻接表中第i个单 链表长度就是此结点的度。* 对于稀疏图，邻接表的空间大小
O(V+E)远小于邻接矩阵 *完全图： 邻接表 = 邻接矩阵
读入边的列表（M条边{u,v,w}），建立邻接表。
struct Edge
{ //将边定义成结构体Edge int v,w;//边的终点v和边权w Edge(int v1, int w1):v(v1),w(w1){};//构造函数};
vector<Edge> Adj[N+5];//N为点数
for(int i=1;i<=M;i++)//M为边数{ int u,v,w;//边<u,v>的权为w cin>>u>>v>>w; Adj[u].push_back(Edge(v,w)); Adj[v].push_back(Edge(u,w));//若为无向图， 建2条边}
二分图
• 可以把顶点分成两部分, 每部分之间没有边。 这样的图只 有包含偶数条边的环。• 许多困难问题在二分图上有有效算法。
如何判断一个图是否是二分图？
使用stl-vector
• #include <vector>• vector模拟动态数组， vector的元素可以是任意类型， 但必须具备赋值和 拷贝能力。• vector支持随机存取
BFS算法
• 广度优先搜索(BFS)是基础的图搜索算法之一， 也是许多重要的图论算法（例如Prim求MST， Dijkstra求最短路） 的原型。• BFS算法：给定有向/ 无向图G(V,E)和1个源点 s， 对图G中的边进行系统性地搜索来发现可以 从s到达的所有结点。 该算法生成一棵“BFS 树” ， 同时能够计算s到其他可达结点的最短 距离（最少边数） 。
BFS树
• BFS树并不唯一， 一般搜索顺序是按字 典序或者建图顺序；并不是所有边都在 BFS树中• BFS树中， 任意两点只有唯一的简单路 径• 在BFS树中， 以s为root， 包含所有从s 可达的结点。 对于结点v：在BFS树中 s->v 的唯一简单路径所对应的就是图G 中“ 包含最少边数的路径” 。
BFS算法
void bfs(s)
{ //s表示BFS的源点s 设置一个队列q; 访问源点s; q.push(s); while(!q.empty())
{ cur=q.front();q.pop(); for v ∈Adj[cur]//邻接表 or 邻接矩阵 i f ( v 没有被访问过) 访问v ; / / 可以顺带记录距离d[v]， 以及前驱p[v] q.push(v); }}
树的直径
• 一棵树T的“ 直径” 定义为结点两两间距离的最大值。• 找直径方法：两遍DFS（或BFS）• 1.从任意源点s出发DFS/ BFS， 找距离最远点d1；• 2.从d1出发DFS/ BFS， 找距离最远点d2；则d1<->d2为直径
• 反证：• 不妨设f>=e• 若f1<->f2才是直径，• 则有 1.b>c+d+f(BFS#2)• 2.f>c+d+b (f1<->f2是直径,矛盾)
EG：
BZOJ-3124 [SDOI2013]直径
如果你不开心，那我就把右边这个帅傻子分享给你吧， 你看，他这么好看，跟个zz一样看着你，你还伤心吗？ 真的！这照片盯上他五秒钟就想笑了。 一切都会过去的。 时间时间会给你答案2333