终于摆脱$O(n^2)$的空间复杂度啦

前言

本周三(2019.3.13)，Payphone-X学完了Dijkstra，他要继续向SPFA前进。但是，他不会邻接表……于是便有了这篇Blog

初始约定

在下文的邻接表讲解以及代码实现中，很多时候会出现(from , to , number)

这表示一条边，从from到to ，编号为number。

就像下图，为(1 , 2 , 0)：

AV0bxs.png

何为邻接表？

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
——百度百科

emm……

算了……

以后不能再用百度百科了……

还是听听通俗的解释吧。

顾名思义，邻接表是一种特殊的链表，用来表示一条边。

无权图上，每一张链表存储了两个信息：

这条边的到达的节点 与 从出发点出发的上一条边。

而有权图上，则存储了三个：

这条边的到达的节点 与 从出发点出发的上一条边 以及 边权

也就是说，邻接表是用边来存图，而邻接矩阵使用点来存图。

邻接表的实现

看到这，有的同学可能要问了：既然邻接表使用来存图的，那怎么实现它呐？

别急……

继续向下看就知道啦……

邻接表存储的信息有两到三个（不知道是哪几个的自觉面壁），并且每一条边都需要一张链表。

所以说……

开结构体模拟啊

但一个结构体还不够，我们还需要开一个一维数组记录当前边的上一条边的编号，开一个int变量记录边数。

代码实现是这样的(ps.无权图)：

struct Edge{
	int to;
	int last;
}edge[10001];

int end[10001];
int edge_number;

add_edge

现在，我们已经会建立邻接表了。

那……

我们如何加边呐？

想想看，我们输入的是不是这条边的from与to？

所以结构体的to就已经解决了啊。

如果有变权的话就把输入的边权赋值给结构体中的边权就好啦

所以边权也解决啦

而上一条边，就是end数组中以from为下标的点啊

所以last也解决了。

最后别忘了更新一下end数组，使上一条边的编号变成刚刚加入的这条边。

代码实现是这样的(ps.有向无权图)：

void add_edge(int from , int to){
	edge[++edge_number].to = to;
	edge[edge_number].last = end[from];
	end[from] = edge_number;
}

附件（邻接表模板，有向有权图）

#include<iostream>

using namespace std;

struct Edge{
	int to;
	int last;
	int longg;
}edge[10001];

int end[10001];
int edge_number;

void add_edge(int from , int to , int longg){
	edge[++edge_number].to = to;
	edge[edge_number].last = end[from];
	edge[edge_number].longg = longg;
	end[from] = edge_number;
}

int main(){
	
	return 0;
}
// Written By Payphone-X