图论_链式前向星

 

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

 

---

 

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

       前向星的优化：一开始读入时，先数出每个点出去的边的条数，从而计算出排序后每个点为起点的第一条边位置应在哪里，最后把全部边扫一遍放到排序后应在的位置。

 

---

 

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

　　1、构建边结构体。

　　

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

 

　　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 }

 

　　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 }

 

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

 

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

 

 

---