邻接矩阵直接使用二维数组graph[N][N]来存它虽然代码简单查询较快但是有时候很浪费空间而且数据范围有较大的限制并不常用。2.邻接表顾名思义邻接表就是每个节点值储存它直接可以到的其他节点。它的空间浪费比邻接矩阵小得多但是在找邻居的时候要遍历它的整个邻接表速度比邻接矩阵慢。3.链式前向星它其实就是用链表实现的邻接表。主体一个head[u]数组指向u的邻居存的地址。和一个struct Edge{int to,nxt};其中to指邻居编号nxt指下一个邻居的地址。具体代码如下点击查看代码4.Vector 直接存边这个方法是最常用的一个。直接用vectorEdge e[N]存边就可以了。struct Edge{int to,w;}; vectorEdge e[N]; ...遍历这里只介绍后两种常见方法的遍历方法前两种请读者自行探讨。链式前向星for(int ihead[u];~i;ie[i].nxt){ ... }Vector 直接存边for(auto it:e[u]){ ... }那么学会存图和遍历后来做一下几道模板题来练一练吧图的存储与出边的排序图的遍历二、拓扑排序首先你要了解拓扑在干什么给一个有向无环图(DAG)的所有节点排序————OI_WIKI那么拓扑排序之后就一定有每个顶点仅出现一次对于有向边A-B在序列中都必有A在B前。操作还是比较简单的1.找到入度为 的点并输出2.将所有与该点连接的边删除邻居入度减 3.重复步骤 1~2 ,直到没有任何点入度为 为止。注意有环图是不能进行拓扑排序的学了拓扑还是做一道模板题吧【模板】拓扑排序/家谱树三、欧拉路欧拉路其实就是一个简单的一笔画问题。它的定义是从图中某一个点出发遍历整个图图中每一条边通过且仅通过一次。欧拉回路就是起点和终点一样的欧拉路。一般关于欧拉路的问题基本上就是是否有欧拉路。打印欧拉路。通常是通过处理度来解决问题的。其中度数为奇数的为奇点度数为偶数的为偶点。1.存在性判断无向图若全是偶点存在欧拉回路显然。若有 个奇点存在欧拉路一个是起点另一个是终点。有向图和无向图差不多我们将一个点的度数记作入度减去出度。若所有点度数为零才会存在欧拉回路。若仅有一个点度数为 一个点度数为 其余点的度数为零才存在欧拉路 的为起点 的为终点。2.输出欧拉回路dfs 即可。习题Luogu:P7771 【模板】欧拉路径UVa:10054 The NecklacePOJ:1780 Code四、连通性问题关于连通性连通对于无向图的两点 若存在途径使得 且 则称连通。连通图任意两点连通的无向图称为连通图。1.无向图一些定义割点对于 ,若删去 以及关联的边后图分裂为两个及以上不相连的子图则称 为 的割点。割边桥同上。首先我们要会求割点和割边很明显考虑 Tarjan 算法。求割点 【模板】割点割顶依赖一下两个主要的数组追溯值 定义为以 为根的搜索树上的点以及通过一条不在搜索树上的边能达到的结点中的最小编号。时间戳 定义为 按访问顺序的编号。void Tarjan(int u){ dfn[u]low[u]Time; int son0; for(auto v:e[u]){ if(dfn[v]){ low[u]min(low[u],dfn[v]); continue; } son; Tarjan(v); low[u]min(low[u],low[v]); if(low[v]dfn[u]u!root)cnt!is_cut[u],is_cut[u]1; } if(son2uroot)cnt!is_cut[u],is_cut[u]1; }求割边 【模板】割边桥和割点很像void tarjan(int u,int fa){ dfn[u]low[u]idx; for(int v:g[u]){ if(!dfn[v]){ tarjan(v,u); low[u]min(low[u], low[v]); if(dfn[u]low[v])add_bridge(u,v); } else if(v!fa)low[u]min(low[u],dfn[v]); } }习题Luogu:P3469 [POI 2008] BLO-BlockadeHDU:2460 NetworkLuogu:P1173 [NOI2016] 网格(hehe)割点和割边可以引出以下这些更为重要的定义点双连通图不存在割点的无向连通图称为点双连通图。边双连通图不存在割边的无向连通图称为边双连通图。点双连通分量一张图的极大点双连通子图称为点双连通分量v-DCC简称点双。边双连通分量一张图的极大边双连通子图称为边双连通分量e-DCC简称边双。但是实际上点双的定义是有歧义的而笔者采用的是接下来的这一个 OI_WIKI 版本的定义笔者以后的代码书写也参考接下来的版本。在一张连通的无向图中对于两个点 和 如果无论删去哪一个点不能删 和 自己都不能使它们不连通我们就说 和点双连通。——OI_WIKI求边双 【模板】边双连通分量边双连通分量的求法很简单。并不比求割边的代码长太多依旧依赖一下两个主要的数组追溯值时间戳在求割边的时候我们已经对所有割边进行了标记。所以我们只要再次 DFS 不访问割边对每一各连通块进行标记则可以得到边双。求点双 【模板】点双连通分量点双联通分量的求法就没有边双那么简单了。虽然割边不隶属于任何边双但是割点是有可能隶属于多个点双的。所以此时我们就应该在跑 Tarjan 的过程中维护一个栈。当一个节点第一次被访问时入栈。当dfn[x]low[y]成立时不断弹栈直至 被弹出。而且刚刚弹掉的节点和 构成一个 v-DCC 。习题边双POJ:3352 Road ConstructionLuogu P2860 [USACO06JAN] Redundant Paths G点双Luogu:P3225 [HNOI2012] 矿场搭建POJ:2942 Knights of the Round TableLuogu:P5058 [ZJOI2004] 嗅探器2.有向图一些定义强连通若一张有向图的节点两两互相可达则称这张图是强连通的。强连通分量即极大的强连通子图称为SCC。首先我们要了解DFS 生成树。我们在一个有向图上选一点 从 开始遍历每一个点只遍历一次这样就会构成一棵树即 DFS 生成树。这棵树上会有这么几种边树边每次由⼀个已遍历的点到达未遍历的点就形成了⼀条树边。返祖边也叫做回边指向该节点的祖先。横叉边搜索时遇到⼀个已访问的节点但这个节点并不是该节点的祖先。前向边访问时遇到⼦树中的节点时形成的。举个栗子如图图中的红边即为返祖边紫边为横插边黄边为前向边其余为树边。求强连通分量有很多方法由于作者很菜本文只介绍 种。Tarjan 算法 【模板】强连通分量这个算法依旧是用栈来处理。DFS 流程很简单我们把当前节点 入栈。若 则开始弹栈直到 被弹出去。弹出去的点构成一个 SCC。代码void dfs(int u){ dfn[u]low[u]Dfn; in_stack[u]1; s[num]u; for(int ihead[u];i;ie[i].nxt){