建图基础¶
一、前言¶
1.1配套视频¶
https://www.bilibili.com/video/BV1RD4y1F7Fq
1.2 基础说明¶
图一般定义为 二元集 ；
由 顶点集 与 边集 构成。
或者更抽象的说，由一个集合(顶点)，和集合上的关系（边）构成
二、图的基本概念名词¶
邻接矩阵
邻接表
度，出度，入度
- 在有向图中，箭头是具有方向的，从一个顶点指向另一个顶点，这样一来，每个顶点 被指向 的箭头个数，就是它的入度。从这个顶点指出去的箭头个数，就是它的出度
有向边，无向边，重边。
环，自环。
闭包等
2.1有向图和无向图¶
有向图就是边在表示的时候有一个 单向性 ，无向图就是在边表示的时候有一个 双向性 ，这一点在我们建图的时候也能提现到
三、邻接矩阵（稠密图）¶
我们用一个二维矩阵来表示这个图，二维矩阵的两个维度就分别对应着起点，和终点，我们习惯把第二维度的作为起点，第一维度的作为终点
那么对于有向图来说我们只用不断地维护顶点地关系即可，举个栗子
\(mp[i][j]\)表示地是\(i\)这个点指向j这个点的时候地边的权值
四、邻接表（稀疏图）¶
对于邻接表而言，我们建图的方式就很多了，我这里举两个常用的方式
4.1使用容器vector¶
大家都知道，vector是一个变长数组的容器，它会根据你的需求来分配对应的空间，所以我们就可以根据这个来建图
我们先定义一个结构体，这个结构体要包含哪些信息呢：终点信息、边权值
那么我们就能写出来了：
struct Edge{
int v,w;//v表示的是终点、w表示的是起点到重点的权值
};
vector<Edge>E[N];//这个N是根据你的顶点的大小来决定的
这样一来我们发现，我们也能维护这个图push_back(node)
4.2使用原生数组¶
由于数组不能是变长的，有些时候又因为点不多，但是都挺大，造成了数组空间不够，我们因此就能想到链表的结构来维护这个图，于是你就得到了下面这个结构体
struct Edge{
int v,w;
struct Edge* next;
};
Edge E[N];
这样每一个点就是一条链表，这样我们也能很好的维护这个图
五、链式前向星¶
5.1前向星¶
前向星是一种 特殊的边集数组 ,我们把边集数组中的每一条边 按照起点从小到大排序 ,如果 起点相同就按照终点从小到大排序 ,并记录下 以某个点为起点 的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.
我们用\(len[i]\)来记录所有以\(i\)为起点的边在数组中的存储长度.
我们用用\(head[i]\)记录以\(i\)为边集在数组中的第一个存储位置.
举个栗子：
假设我们有这样一个图：
这个边的输入情况如下：
1 2
2 3
3 4
1 3
4 1
1 5
4 5
排完序后可以得到如下边顺序：
| 编号： | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 起点： | 1 | 1 | 1 | 2 | 3 | 4 | 4 |
| 终点： | 2 | 3 | 5 | 3 | 4 | 1 | 5 |
然后我们就能获得head数组和len数组的信息了
head |
len |
|---|---|
| head[1] = 1 | len[1] = 3 |
| head[2] = 4 | len[2] = 1 |
| head[3] = 5 | len[3] = 1 |
| head[4] = 6 | len[4] = 2 |
这个建图的方法能帮我们优化后面要学的DFS和BFS，但是仅仅是这样就足够了吗？答案显然是不够，我们可以学到一种更优的建图方法： 链式前向星
5.2链式前向星¶
我们根据前面所学的启发可以想到建立一种新的边的结构体
struct Edge{
int last;
int to;
int w;
};
其中edge[i].to表示第\(i\)条边的终点,edge[i].last表示与第\(i\)条边同起点的上一条边的存储位置,edge[i].w为边权值.
另外受到前向星的启发，我们还有一个head数组，它是用来表示以\(i\)为起点的 第一条边存储 的位置,实际上你会发现这里的第一条边存储的位置其实在以\(i\)为起点的所有边的 最后输入的那个编号 .
我们将head数组初始化为-1或者0，cnt初始化为0，cnt表示的是当前加的边数，然后对它不断地更新操作，很显然我们能得到这样地一个加边地操作
void add(int u,int v,int w)
{
edge[cnt].w = w;//更改边权
edge[cnt].to = v;//更改下一个点的位置
edge[cnt].last = head[u];//记录上一个以u为终点的边的位置
head[u] = cnt++;//更新一下head数组
}
还是用上面的图，我们就能得到如下的边权关系
| edge[i].to | edge[i].last | head[i] |
|---|---|---|
| edge[0].to = 2 | edge[0].last = -1 | head[1] = 0; |
| edge[1].to = 3 | edge[1].last= -1 | head[2] = 1 |
| edge[2].to = 4 | edge[2],last = -1 | head[3] = 2 |
| edge[3].to = 3 | edge[3].last = 0 | head[1] = 3 |
| edge[4].to = 1 | edge[4].last = -1 | head[4] = 4 |
| edge[5].to = 5 | edge[5].last= 3 | head[1] = 5 |
| edge[6].to = 5 | edge[6].last = 4 | head[4] = 6 |
head[i]就是保存的最后的那条边的编号、这个链式前向星在遍历图的时候是倒着遍历的，所以我们用其中一个成员last表示上一个节点的位置，这样对图也不会有什么影响
所以我们就能得到一个遍历的方式：
for(int i=head[u];i!=-1;i=edge[i].last)
//中间那个循环判断也可以写成~i，不懂得同学可以去了解一下负数补码