存储表示
图的邻接表（稀疏图，一般$\left| E \right|<\ \left| V \right|\log \left| V \right|$时视为稀疏图）数组实现、初始化与插入函数（y 总版本的）：
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace std;
const int maxn = 10001;
int h[maxn], ne[maxn], e[maxn], w[maxn];
void get(int a, int b, int q){
ne[idx] = h[a];
e[idx] = b;
w[idx] = q;
h[a] = idx++;
}
int idx = 0;
mem(h, -1);
遍历
//DFS
int st[maxn];
mem(st, 0);
int dfs(int u){
st[u] = 1; // st[u] 表示点 u 已经被遍历过
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]){
dfs(j);
}
}
}
//BFS
int st[maxn];
mem(st, 0);
queue<int> q;
st[1] = 1; // 表示 1 号点已经被遍历过
q.push(1);
while (!q.empty()){
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]){
st[j] = 1; // 表示点 j 已经被遍历过
q.push(j);
}
}
}
前面两种遍历在功能上的差异，主要体现为每一步迭代中对新顶点的选取策略不同。比如，BFS 搜索会优先考查更早被发现的顶点，而 DFS 搜索则恰好相反，会优先考查最后被发现的顶点。每一种选取策略都等效于，给所有顶点赋予不同的优先级，而且随着算法的推进不断调整；而每一步迭代所选取的顶点，都是当时的优先级最高者。按照这种理解，包括 BFS 和 DFS 在内的几乎所有图搜索，都可纳入统一的框架。鉴于优先级在其中所扮演的关键角色，故亦称作优先级搜索（$priority$-$first$ $search$, $PFS$），或最佳优先搜索（$best$-$first$ $search$, $BFS$）。
$PFS$搜索的基本过程和功能与常规的图搜索算法一样，也是以迭代方式逐步引入顶点和边，最终构造出一棵遍历树（或者遍历森林）。如前所述，每次都是引入当前优先级最高（优先级数最小）的顶点$s$，然后按照不同的策略更新其邻接顶点的优先级数。
在无向连通图$G$中，当且仅当删去$G$中的顶点$v$及所有依附于$v$的所有边后，可将图分割成两个或两个以上的连通分量，则称顶点$v$为关节点。没有关节点的连通图叫做重连通图。在重连通图上, 任何一对顶点之间至少存在有两条路径, 在删去某个顶点及与该顶点相关联的边时, 也不破坏图的连通性。一个连通图$G$如果不是重连通图，那么它可以包括几个重连通分量。在一个无向连通图$G$中, 重连通分量可以利用深度优先生成树找到。
从某点出发，深度优先遍历图，各节点的访问次序记为深度优先数$dfn$。其中，深度优先树的祖先节点的$dfn$一定小于子孙节点。原图中未被深度优先搜索访问的边叫做回边。为求解关节点，再定义一个最小深度优先数$low$值，计算方式为：
$$
low\left[ u \right] =\min \left( dfn\left[ u \right] ,\min \left( low\left[ w \right] ,\min \left( dfn\left[ x \right] \right) \right) \right)
$$
其中$w$为$u$的子女，$(u,x)$为点$u$的回边。那么$u$为关节点的充要条件是要么$u$为树根有两个子女；要么$u$不为树根但有一子女$w$使得$low\left[ w \right] \ge dfn\left[ u \right] $成立。
拓扑排序
拓扑排序的前提是有向无环图，同一有向图的拓扑排序未必唯一，拓扑排序也未必存在。有向无环图的拓扑排序必然存在；反之亦然。这是因为，有向无环图对应于偏序关系，而拓扑排序则对应于全序关系。在顶点数目有限时，与任一偏序相容的全序必然存在。
时间复杂度$O(n+m)$，$n$表示点数，$m$表示边数：
//拓扑排序
bool topsort(){
int hh = 0, tt = -1;
// d[i] 存储点 i 的入度
for (int i = 1; i <= n; i ++ ){
if (!d[i]){
q[++tt] = i;
}
}
while (hh <= tt){
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (--d[j] == 0)
q[++tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
最小生成树
连通图$G$的某一无环连通子图$T$若覆盖$G$中所有的顶点，则称作$G$的一棵支撑树或生成树。就保留原图中边的数目而言，支撑树既是“禁止环路”前提下的极大子图，也是“保持连通”前提下的最小子图。
时间复杂度是$O(n^2+m)$，$n$表示点数，$m$表示边数。
//prim 算法
int n; // n 表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回 INF(值是 0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i++ ){
int t = -1;
for(int j = 1; j <= n; j ++ ){
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
//t 是不在已有生成树中的距离最小点
if(i && dist[t] == INF){
return INF;
}
if(i){
res += dist[t]
}
st[t] = 1;
for(int j = 1; j <= n; j ++ ){
dist[j] = min(dist[j], g[t][j]);
}
}
return res;
}
时间复杂度是$O(mlogm)$，$m$表示边数。
//kruskal 算法
int n, m; // n 是点数，m 是边数
int p[N]; // 并查集的父节点数组
struct Edge{ // 存储边
int a, b, w;
bool operator< (const Edge &W)const{
return w < W.w;
}
}edges[M];
int find(int x){ // 并查集核心操作
if(p[x] != x){
p[x] = find(p[x])
}
return p[x];
}
int kruskal(){
sort(edges, edges + m);
for(int i = 1; i <= n; i ++ ){ // 初始化并查集
p[i] = i;
}
int res = 0, cnt = 0;
for(int i = 0; i < m; i ++ ){
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a);
b = find(b);
if(a != b){ // 如果两个连通块不连通，则将这两个连通块合并
p[a] = b;
res += w;
cnt++ ;
}
}
if (cnt < n - 1){
return INF;
}
return res;
}
