yuzh的博客

❤ ECUST ❤

0%

链式前向星

发表于 Valine：

概念

链式前向星是一种图的存储方式，相比于邻接矩阵和邻接表，链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点。

数据结构详解见视频。

实现

链式前向星存储包括两种结构：

  • 边集数组edge[]：edge[i]表示第i条边;

  • 头结点数组head[]：head[i]存以i为起点的第一条边的下标(在edge[]中的下标)。

Edge结构如下：

1
2
3
4
5
6
struct Edge
{
	int to;
	int weight;
	int next;
}edge[maxn*maxn];

其中，to为当前边的终点，weight为边权，next为当前边终点的兄弟节点，即当前边起点的另外一个邻接点。

添加边需要通过addEdge(u,v,w);执行，完整数据结构维护代码见下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define maxn 10001

struct Edge
{
	int to;
	int weight;
	int next;
}edge[maxn*maxn];

int head[maxn], cnt=0;

void addEdge(int from, int to, int weight)
{
	edge[cnt].to=to;
	edge[cnt].weight=weight;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}

若需访问某个节点u的所有邻接点，使用for循环即可，如下所示：

1
2
3
4
5
for(int i=head[4];i!=-1;i=edge[i].next)
{
    //输出临界点的编号和到这个临界点的边权
    cout<<edge[i].to<<" "<<edge[i].weight<<endl;
}