邻接表与链式前向星更正： 使用
vector存图的叫做邻接表使用数组模拟的叫做链式前向星
邻接表（使用 vector）
使用邻接表的优劣： 优势：
- 码量少，易操作
- 不用担心空间，不易写错
劣势：
- cpp11 之前不能使用
auto v : i形式遍历 vector- 在不能开启
O2的题目中较慢（POJ 全占）
存图方式
struct line // 自定义结构体{ int ver; // 指向的结点 int edge; // 边的权值 line(int v, int e) // 构造函数 { ver = v; edge = e; }};
vector<line> g[MAX]; // 新建邻接表遍历方式
对于 C++11 后的 OJ，使用如下方式遍历：
// line是结构体的名字// from是父节点的下标for(line son : g[crd]){ // 示例代码，含义为不经过父节点 if(son.ver == from) continue;}对于 C++11 前的 OJ，使用如下方式遍历
其实这里建议使用链式前向星，因为不支持 C++11 的 OJ 很可能没有 O2
// line是结构体名字for (line son = g.begin(); son != g.end(); son++)// 下略……添加方式
// N为边的数量for(int i = 1; i < N; i++){ int u, v, w; scanf("%d%d%d", &u, &v, &w); g[u].push_back(line(v, w)); g[v].push_back(line(u, w));}链式前向星
使用链式前向星的优劣： 优势：
- 速度快，无需
O2- 不受 C++版本限制，适用于所有题目
劣势：
- 数组模拟链表，初学者不易理解
- 码量多，不理解容易打错，不易 Debug
存图方式
struct line{ int ver; // 指向的结点 int next; // 下一条边 // int edge; // 边的权值}node[MAX * 2]; // 新建链式前向星int head[MAX]; // 表头数组遍历方式
for(int son = head[crd]; son; son = node[son].next)// 下略……添加方式
// 前向星添加边（使用函数）// tot为所有边的数量，初始值为0void add(int u, int v/*, int edge*/){ node[++tot].next = head[u]; node[tot].ver = v; //node[tot].edge = edge; head[u] = tot;}觉得这篇文章怎么样？
点个赞，让更多人看到！
评论区