涸辙之鲋造句,6535s,渔亦鱼
参考自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 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论