额尔古纳网站建设价格淘宝客seo推广教程
前置知识
上一节我们介绍了三种基本的存图结构：
「图」邻接矩阵|边集数组|邻接表（C++）
概述
他们各有优劣，为了综合他们的性能，
这一节我们来介绍两种以这三种结构为基础实现的高级存储结构：链式邻接表|链式前向星。
1.链式邻接表
结构
链式邻接表由一个二维表头数组head和一个边集数组e构成，
*注意*：edges边集数组的结构详见：「图」邻接矩阵|边集数组|邻接表（C++）
表头数组head的功能类似邻接表，但它储存的并不是出边结构而是出边的编号。
一维head数组存储某个点的一系列出边编号，他们构成的二维head数组储存所有点的出边编号。
边集数组e以编号作为索引提供出边的全部信息{u,v,w}
将这两个数据结构封装成一个整体，称为chained_adjacency_list：
struct chained_adjacency_list {edges e;vector<vector<int>>head;
};对于head[u][i]=idx;表示从u节点出发的第i条边在所有边中编号为idx。
对于edges[idx]={u,v,w};编号为idx的边从u节点出发抵达v节点，边权为w。
（边的序号通常时建图时读入数据时编排的。）
形象理解：
边集数组作为数据库存储全部边信息，
点集数组head悬挂了一排出边数组head[i]，head[i]是第i个点的所有出边，每个head[i][j]存储第i个点的某一出边j的索引，用于对边集数组进行访问。
复杂度
空间复杂度: O(n+m)
n：节点数量
m：边数量
特点：
1.能用于各种图。
2.支持按节点访问。
3.能存储两点之间的多条边。
4.能存储边的编号。
5.先存入的先访问。
实际上链式邻接表综合了邻接表和边集数组的优点，它对邻接表的功能做了分离，使得邻接表不再存储出边的信息，而是存储边集数组的编号，以此作为索引对存储了出边信息的边集数组进行访问。
Code
struct chained_adjacency_list {edges e;vector<vector<int>>head;
};
void add(chained_adjacency_list& l) {int n; cin >> n;while (n--) {int u, v, w; cin >> u >> v >> w;l.e.push_back({ u,v,w });if(u>=l.head.size())l.head.resize(u+1);l.head[u].push_back(l.e.size() - 1);}
}
void get(const chained_adjacency_list& l) {for (const vector<int>& i : l.head)for(const int&idx:i)cout << " " << l.e[idx].w << endl << l.e[idx].u << "------------->" << l.e[idx].v << endl;
}2.链式前向星
结构
链式邻接表由一个一维表头数组head和一个边集数组e构成，
表头数组head只存储一个点的一个出边编号。
edge_with_next这个结构具有成员变量v,w,next；意为：这条边抵达v，边权为w，与其出发点相同的下一条边编号为next。你会发现它模拟了链表结构，即一个边单元存储着下一个边单元的next索引，依靠这个索引访问e中的下一条边。（这里的下一条是指出发点同为v的下一边）
边集数组e由edge_with_next构成数组，存储了全部出边信息。
将这两个数据结构封装成一个整体，称为chained_foward_star：
struct edge_with_next {int v;int w;int next;
};
using edges_with_next = vector<edge_with_next>;
struct chained_foward_star {edges_with_next e;vector<int>head;
};对于head[u]=idx;表示从u节点出发的首条边在所有边中编号为idx。
对于edges[idx]={v,w,next};编号为idx的边抵达v节点，边权为w，与其出发点相同的下一条边编号为next。
（边的序号通常时建图时读入数据时编排的。）
形象理解：
边集数组作为数据库存储全部出边信息{v,w,next}，
点集链表head悬挂一排链表，head[i]为一张链表的链表头，同时也是第i个点的首条出边，head[i].next储存i的下一条出边。
另外，在添加i点的新边时，链式前向星会将链表头head[i]更新为该边，同时该边的next会指向曾经的head[i]，也就是说存边时会翻转先后顺序，即先存入的后访问。
复杂度
空间复杂度: O(n+m)
n：节点数量
m：边数量
特点：
1.能用于各种图。
2.支持按节点访问。
3.能存储两点之间的多条边。
4.能存储边的编号。
5.边能存储下一条边。（这里的下一条是指出发点同为v的下一边）
5.先存入的后访问。
实际上链式前向星的策略与链式邻接表有所不同，它的对一系列出边的悬挂并不是依靠出边数组实现，而是依靠类似链表的next指针结构相连的。
简单来说，链式邻接表依靠数组结构储存一个点的一系列出边；链式前向星依靠链表结构储存同一个点的一系列出边。
Code
struct edge_with_next {int v;int w;int next;
};
using edges_with_next = vector<edge_with_next>;
struct chained_foward_star {edges_with_next e;vector<int>head;
};
void add(chained_foward_star& star) {int n; cin >> n;while (n--) {int u, v, w; cin >> u >> v >> w;if (u >= star.head.size())star.head.resize(u + 1, -1);star.e.push_back({ v,w,star.head[u] });star.head[u] = star.e.size() - 1;}
}
void get(const chained_foward_star& star) {for (int i = 1; i < star.head.size();i++) {int idx = star.head[i];while (idx != -1) {cout << " " << star.e[idx].w << endl << i << "------------->" << star.e[idx].v << endl;idx = star.e[idx].next;}}
}测试Code
/*
11
1 2 20
2 1 30
2 0 30
4 3 100
8 9 60
9 7 40
3 6 50
5 6 20
7 8 15
2 4 30
1 3 5
以上为测试用例
*/
int main() {int test; cin >> test;switch (test) {case 4: {chained_adjacency_list cl;cout << "------------input------------" << endl;add(cl);cout << "------------output-----------" << endl;get(cl);break;}case 5: {chained_foward_star star;cout << "------------input------------" << endl;add(star);cout << "------------output-----------" << endl;get(star);break;}}return 0;
}