C++

图论_链式前向星


 

  参考自https://blog.csdn.net/ACdreamers/article/details/16902023(深度理解链式前向星-acdreams)

 


 

  对于前向星,我的理解就是将边集按照起点顺序进行排序后存储(而并没有将终点也进行排序的必要)。同时head[u]记录以u为起点的边集在数组中的第一个(读入时首次出现)存储位置

       前向星的优化:一开始读入时,先数出以每个点为起点的边的条数,从而计算出排序后每个点为起点的第一条边位置并存入head[u],最后把原数据边扫一遍放到排序后应在的位置。

 


 

  重点描述链式前向星,链式前向星可避免使用前向星所进行的排序步骤,下面是链式前向星的相关操作:

 

  1、构建边结构体。

  

1 struct Edge{
2     int v;    //边的终点
3     int w;    //边权
4     int next;    //与此条边同起点的下一条边的存储位置
5 }edge[maxn];
View Code

 

  2、边集的存储(加边时同一起点最后加入的边的位置由head[u]存储)

 

1 void add_edge( int u, int v, int w){
2     edge[cnt].v=v;
3     edge[cnt].w=w;
4     edge[cnt].next=head[u];
5     head[u]=cnt;
6     cnt++;
7 }
View Code

 

  3、遍历边集

 

1 void found( int u ){
2     if( head[u]<0 )
3         return ;
4     for( int i=head[u]; ~i; i=edge[i].next){
5         
6     }
7 }
View Code

 

  4、数据的初始化(head[u]初始化为-1做结束判断)

 

1 void init()
2 {
3      cnt = 0;
4      memset( head, -1, sizeof(head));
5 }
View Code

 


 


作者:Konoba,发布于:2019/08/14
原文:https://www.cnblogs.com/konoba/p/11351025.html