【图论C++】链式前向星（图(树)的存储）

/**
 * @file            
 * @author          jUicE_g2R(qq:3406291309)————彬(bin-必应)
 *						一个某双流一大学通信与信息专业大二在读	
 * 
 * @brief           一直在竞赛算法学习的路上
 * 
 * @copyright       2023.9
 * @COPYRIGHT			 原创技术笔记：转载需获得博主本人同意，且需标明转载源
 * @language        C++
 * @Version         1.0还在学习中  
 */
1
2
3
4
5
6
7
8
9
10
11
12

• UpData Log👆 2023.9.25 更新进行中
• Statement0🥇 一起进步
• Statement1💯 有些描述是个人理解，可能不够标准，但能达其意

技术提升站点

链式前向星

• 链式前向星 建立在 邻接表 的基础上，从 2结点 开始记录（只画了部分部分）：

• 根据 邻接表 建立 链式前向星存图

$head[u]$ ：记录 u节点 的 第一个邻居节点 的存储编号

$i$ ：存储编号

$edge[i].to$ ：u节点 的邻居节点（编号）

$edge[i].next$ ：记录 u节点 下一个邻居节点 的存储编号

（上图与下面的测试无关）

模拟存储过程

//test：手动模拟数据存储过程，假设： 存入边 2-1 2-3 2-4 2-5
//存入2-1
edge[0].to=1, edge[0].next=head[2]=-1, head[2]=0;
i		0
to		1
next	-1
//存入2-3
edge[1].to=3, edge[1].next=head[2]=0, head[2]=1;
i		0	1
to		1	3
next	-1	0
//存入2-4
edge[2].to=4, edge[2].next=head[2]=1, head[2]=2;
i		0	1	2
to		1	3	4
next	-1	0	1
//存入2-5
edge[2].to=5, edge[3].next=head[2]=2, head[2]=3;
i		0	1	2	3
to		1	3	4	5
next	-1	0	1	2
//2结点的边存储完成，head[2]=3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码实现

const int N=1e5;
vector<int> head(N,-1);
int cot=0;
struct Edge{
    int to,next;
    //int weight;
    Edge():to(-1), next(-1){}				    //初始化为无邻居节点
    //Edge(int to, int w):to(to), weight(w);	//对 结构体的成员 进行赋值 的构造函数
} edge[N];
void Add_Edge(int u, int to, int w){
    edge[cot].to=to;
    //edge[cot].weight=w;
    edge[cot].next=head[u];                     //记录 上一个邻居节点 的 存储编号
    head[u]=cot++;                              //当前 邻居节点 的 存储编号，以便下一个邻居节点的访问
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15