图论_链式前向星

 

　　参考自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

 

---

 

原文链接:https://www.cnblogs.com/konoba/p/11351025.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有