链式前向星笔记

**

链式前向星

**

一个简单实用的存图结构。 遍历一遍时间复杂度O（V+E） 空间复杂度O（E）
就好比一个静态的邻接表。链式前向星用数组代替了邻接表的链式存储方式。

简单来说就是两个数组，相当于包租婆和租户的关系和两栋房子。head里住着n个包租婆，edge里住着m户租户，edge属于head中所有包租婆共同的财产。某天租户a来租包租婆1房子，租在了一楼，然后包租婆1就记着a向我租1楼房子，又来了租户b，b看包租婆1不顺眼，不去向包租婆1租房，转去向包租婆2租房，包租婆2可开心了，因为1楼已经被租给了a，所以b只能租2楼，包租婆2就记着b向我租2楼房子，之后又来了租户c，向包租婆1租房子，1楼和2楼都租出去了，所以包租婆1把3楼租给了c，然后包租婆1就要记下c住在几楼，不然c的房租交错了怎么办。但是包租婆1因为年纪太大了记不住太多东西，于是她想出了一个办法。她对c说，你记着这个我给你房租便宜点，然后就把上一次来她这租房的人住在几楼告诉c，c就记住了a的地址（住在几楼）。
这个方法很快就在包租婆里被应用，所有的包租婆都这样做。这样只需要记住最后一个来向她们租房的人的地址（住在几楼），收租的时候就不怕记不住了。

（遍历）收租时包租婆记着最后一个来找她租房的租户地址，去找他收房租并且从他那里知道了上上个在她那租房的租户地址…，然后就可以收完所有的房租了。

建图：

void addEdge(int start ,int end ,int distance)
{
edge[cnt].to=end;
edge[cnt].dis=distance;
edge[cnt].next=head[start];
head[start]=cnt++;
}

遍历：

for(int i=0;i<n;i++){
for(int j=head[i];j!=-1;j=edge[j].next){
printf("%d ->%d
%dn",j,edge[j].next,edge[j].dis); ;
}
}

最后

以上就是土豪棉花糖为你收集整理的链式前向星笔记的全部内容，希望文章能够帮你解决链式前向星笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。