数据结构笔记 - 存图方式之链式前向星

发表于 | 分类于 ，

哎呀！图片走丢了！

刚学了链式前向星存图，来记录一下，以便以后抄模板复习用。

链式前向星存图的核心思想是将读入的每一条边编号，记录下从每个点出发的第一条边的编号，并且记录下每条边的“下一条边”的编号。

这样一来，当我们需要遍历从一个点出发的所有边时，只需要从该点的第一条边开始，遍历完成后找到该边的“下一条边”继续遍历。

具体实现时要用到两个数组，first数组和next数组。

开始时我们将两个数组初始化为-1。

我们用$first[i]$表示第$i$个点的第一条边，用$next[i]$表示第$i$条边的下一条边。这样，我们在遍历时，只需从$first[i]$开始遍历，依次遍历$next[i]，next[next[i]]，······，$直到$next[i]=-1$。

（这个博主废话真多，还不给看代码）

$Talk\ is\ cheap!Show\ me\ the\ code!$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//n为点数，m为边数
//from[i]为第i条边的出发点，to[i]为第i条边的到达点，v[i]为边的权值
//读入边
memset(first,-1,sizeof(first));
memset(next,-1,sizeof(next));
for(i=1;i<=m;i++)
{
    cin>>from[i]>>to[i]>>v[i];
    next[i]=first[from[i]];
    first[from[i]]=i;
}

//遍历从点i出发的各个边
for(j=first[i];j!=-1;j=next[j])
{
    cout<<from[j]<<to[j]<<v[j]<<endl;
}

//遍历所有边
for(i=1;i<=n;i++)
{
    for(j=first[i];j!=-1;j=next[j])
    {
        cout<<from[j]<<to[j]<<v[j]<<endl;
    }
}
0%