详解--前向量【转载】

淡淡的烟草味﹌ 2022-06-11 05:10 200阅读 0赞

**我们首先来看一下什么是前向星.**

**前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,**

**并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.**

**用len\[i\]来记录所有以i为起点的边在数组中的存储长度.**

**用head\[i\]记录以i为边集在数组中的第一个存储位置.**

**那么对于下图:**

**![20131123160056593][]**

**我们输入边的顺序为:**

**1 2**

**2 3**

**3 4**

**1 3**

**4 1**

**1 5**

**4 5**

**那么排完序后就得到:**

**编号:     1      2      3      4      5      6      7**

**起点u:    1      1      1      2      3      4      4**

**终点v:    2      3      5      3      4      1      5**

**得到:**

**head\[1\] = 1    len\[1\] = 3**

**head\[2\] = 4    len\[2\] = 1**

**head\[3\] = 5    len\[3\] = 1**

**head\[4\] = 6    len\[4\] = 2**

**但是利用前向星会有排序操作,如果用快排时间至少为O(nlog(n))**

**如果用链式前向星,就可以避免排序.**

**我们建立边结构体为:**

**struct Edge**

**\{**

**     int next;**

**     int to;**

**     int w;**

**\};**

**其中edge\[i\].to表示第i条边的终点,edge\[i\].next表示与第i条边同起点的下一条边的存储位置,edge\[i\].w为边权值.**

**另外还有一个数组head\[\],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实**

**在以i为起点的所有边的最后输入的那个编号.**

**head\[\]数组一般初始化为-1,对于加边的add函数是这样的:**

void add(int u,int v,int w)
    {
        edge[cnt].w = w;
        edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }

**初始化cnt = 0,这样,现在我们还是按照上面的图和输入来模拟一下:**

**edge\[0\].to = 2;     edge\[0\].next = -1;      head\[1\] = 0;**

**edge\[1\].to = 3;     edge\[1\].next = -1;      head\[2\] = 1;**

**edge\[2\].to = 4;     edge\[2\],next = -1;      head\[3\] = 2;**

**edge\[3\].to = 3;     edge\[3\].next = 0;       head\[1\] = 3;**

**edge\[4\].to = 1;     edge\[4\].next = -1;      head\[4\] = 4;**

**edge\[5\].to = 5;     edge\[5\].next = 3;       head\[1\] = 5;**

**edge\[6\].to = 5;     edge\[6\].next = 4;       head\[4\] = 6;**

**很明显,head\[i\]保存的是以i为起点的所有边中编号最大的那个,而把这个当作顶点i的第一条起始边的位置.**

**这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性.**

**比如以上图为例,以节点1为起点的边有3条,它们的编号分别是0,3,5   而head\[1\] = 5**

**我们在遍历以u节点为起始位置的所有边的时候是这样的:**

**for(int i=head\[u\];~i;i=edge\[i\].next)**

**那么就是说先遍历编号为5的边,也就是head\[1\],然后就是edge\[5\].next,也就是编号3的边,然后继续edge\[3\].next,也**

**就是编号0的边,可以看出是逆序的.**

** **

[20131123160056593]: /images/20220611/d0a2d79fc0c740b191b0f3144419acd3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python计算向量夹角：向量夹角计算方法详解

Python计算向量夹角：向量夹角计算方法详解在数值分析和几何学中，我们经常需要计算两个向量之间的夹角。在Python中，我们可以使用numpy库中的函数来计算向量之间的夹

快来打我*/ 2024年03月25日 21:52/ 0 赞/ 96 阅读

相关支持向量机详解

支持向量机详解　　SVM（Support Vector Machine）是数据挖掘中常用的分类算法。事实上，在2012年深度学习算法提出之前，SVM一直被认为是机

偏执的太偏执、/ 2023年08月17日 17:48/ 0 赞/ 78 阅读

相关前端面试的总结（转载）

1.Doctype作用? 严格模式与混杂模式-如何触发这两种模式，区分它们有何意义? （1）、<!DOCTYPE> 声明位于文档中的最前面，处于 <html> 标签之

偏执的太偏执、/ 2022年09月21日 13:10/ 0 赞/ 231 阅读

相关 UIApplication详解（转载）

UIApplication详解（转载）原文地址：[http://blog.sina.com.cn/s/blog\_bf9843bf0101fatt.html][http

我就是我/ 2022年09月18日 12:48/ 0 赞/ 195 阅读

相关详解--bellmanford【转载】

转自：http://www.wutianqi.com/?p=1912 [Dijkstra算法][Dijkstra]是处理单源最短路径的有效算法，但它局限于边的权值非负

左手的ㄟ右手/ 2022年06月11日 05:54/ 0 赞/ 211 阅读

相关详解--前向量【转载】

我们首先来看一下什么是前向星. 前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序, 并记录下以某个点

淡淡的烟草味﹌/ 2022年06月11日 05:10/ 0 赞/ 201 阅读

相关转载--线段树详解

目录：一：综述二：原理三：递归实现四：非递归原理五：非递归实现六：线段树解题模型七：扫描线八：可持久化 (主席树) 九：练习题

男娘i/ 2022年06月10日 02:59/ 0 赞/ 190 阅读

相关 HTTP协议详解[转载]

来源: [HTTP协议详解\[转载\]][HTTP] [HTTP协议详解][HTTP] 当今web程序的开发技术真是百家争鸣，ASP.NET, PHP, J

约定不等于承诺〃/ 2022年01月22日 01:07/ 0 赞/ 262 阅读

相关 PetShop 4 详解（转载）

最近一段时间在研究petShop，希望能通过了解petShop的设计理念，整理出一套重用性强，适合自己在小项目中使用的架构。以作日后使用。 petshop4.0

骑猪看日落/ 2022年01月07日 09:43/ 0 赞/ 284 阅读

相关使用genism训练词向量【转载】

转自：[https://blog.csdn.net/qq\_16912257/article/details/79099581][https_blog.csdn.net_qq_

系统管理员/ 2021年11月26日 11:50/ 0 赞/ 387 阅读