树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(1) 邻接矩阵：g[a][b] 存储边a->b
(2) 邻接表：
//对于每个点k，开一个单链表，存储k所有可以走到的点。
//h[k]存储这个单链表的头结点
int h[N],e[N],ne[N],idx;
void add(int a, int b){ // 添加一条边a->b
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
// 初始化
idx=0;
memset(h,-1,sizeof(h));树与图的遍历
时间复杂度 O(n+m)，n表示点数，m表示边数
(1) 深度优先遍历
int dfs(int u){
st[u]=true; // st[u] 表示点u已经被遍历过
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) dfs(j);
}
}(2) 宽度优先遍历
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size()){
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]=true; // 表示点j已经被遍历过
q.push(j);
}
}
}拓扑排序 时间复杂度 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;
}朴素dijkstra算法 时间复杂度 O(n2+m)，n表示点数，m表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;//到起点1距离为0
for(int i=0;i<n-1;i++){
int t=-1; // 在还未确定最短路的点中，寻找距离最小的点
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
// 用t更新其他点的距离
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
st[t]=true; //确定点t
}
if(dist[n]==0x3f3f3f3f) return -1; //不连通
return dist[n];
}堆优化版dijkstra 时间复杂度 O(m*logn)，n表示点数，m表示边数
typedef pair<int,int> PII;
int n; // 点的数量
int h[N],w[N],e[N],ne[N],idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII> > heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver]) continue;
st[ver]=true;
// 用ver更新其他点的距离
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}Bellman-Ford算法 时间复杂度O(nm)，n表示点数，m表示边数
int n, m; // n表示点数，m表示边数
int dist[N];// dist[x]存储1到x的最短路距离
struct Edge{// 边，a表示出点，b表示入点，w表示边的权重
int a,b,w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1
int bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
if(dist[b]>dist[a]+w) dist[b]=dist[a]+w;
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];
}spfa 算法（队列优化的Bellman-Ford算法） 时间复杂度 平均情况下O(m) 最坏情况下O(nm)，n表示点数，m表示边数
int n; // 总点数
int h[N],w[N],e[N],ne[N],idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]=true;
while(q.size()){
auto t=q.front();
q.pop();
st[t]=false; //出队后，标记为false，可反复入队
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){ // 如果队列中已存在j，则不要将j重复插入
q.push(j);
st[j]=true;
}
}
}
}
if (dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}spfa判断图中是否存在负环 时间复杂度 O(nm)，n表示点数，m表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false
bool spfa(){
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
for(int i=1;i<=n;i++){
q.push(i);
st[i]=true;
}
while(q.size()){
auto t=q.front();
q.pop();
st[t]=false;//出队后，标记为false，可反复入队
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
return false;
}floyd算法 时间复杂度 O(n3)，n表示点数，m表示边数
//初始化：
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) d[i][j]=0;
else d[i][j]=INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}