链式前向星

✍ dations ◷ 2025-08-22 07:39:45 #软件,数据结构,存储软件

链式前向星是一种用于存储图的数据结构，一般认为是由Jason911发明的。链式前向星采用了邻接表的思想，本质上就是用链表实现的邻接表。可以使用数组模拟链表，定义head,to,nxt,edge数组，其中长度为n的head数组表示从每个节点出发的第一条边在to和edge数组中的位置，长度为m的to和edge是一一对应的，分别记录每条边的终点与边权（对于无权图，edge数组可省略），长度也为m的nxt数组模拟了链表指针，表示从相同节点出发的下一条边在to和edge数组中的位置。因此，链式前向星的空间复杂度为 $O(n+m)$ $O(n+m)$ 。

邻接矩阵比链式前向星好写，链式前向星比邻接表好写。

邻接矩阵比邻接表效率高，邻接表比链式前向星效率高。

邻接矩阵空间复杂度为 $O(nm)$ $O(nm)$ ，过于高；邻接表的空间复杂度与链式前向星差不多。

邻接矩阵扩展性极差，应用范围不广，邻接表和链式前向星扩展性较好。

相较而言，链式前向星是一个比较中庸的数据结构。虽说链式前向星还未普及开来，但它绝对是一种优秀的数据结构。

C++代码实现：

相关

蒙古入侵欧洲长子西征，又称蒙古第二次西征、蒙古侵略欧洲（英语：Mongol invasion of Europe），是蒙古帝国继成吉思汗西征花剌子模后的第二次大规模的西征。1235年开始至约1242年，历时约8年，因由各
卵菌纲见内文卵菌门（学名：Oomycota）或卵菌纲（学名：Oomycetes），俗称水霉 (water mold)，是一种与真菌很相似的真核微生物，不具叶绿素，不进行光合作用，需将养分在体外分解后，再进行吸收。但根据亲
1号染色体上1号染色体是人类染色体中最大的一条。如同其他的体染色体，一般人类身体内的细胞中，会有两条1号染色体。在1号染色体，缠绕了大约245,522,847个核苷酸碱基对（DNA的基本讯息单位），大
箕模族箕模族（chi mo，Tjimur），箕模族是排湾族神话中的族群。他们可能是由平地迁入山区的一个族群，目前已融入排湾族群内部。学者李亦园认为排湾族的“太阳卵生”型神话，是被箕模人的起源
痒病羊搔痒症（英语：Scrapie），是一种退化性疾病，发生在绵羊及山羊上，造成它们的神经系统异常。它跟牛海绵状脑病与鹿的慢性消耗病相同，都是传染性海绵状脑病的一种，由异常的朊蛋白（英语：PRN
爪鲵爪鲵（学名：Onychodactylus fischeri）为小鲵科爪鲵属的两栖动物，俗名水蛇子。在中国大陆，分布于辽宁、吉林等地，常栖息于石块较多的山间溪流。其生存的海拔下限为 1000米。该物种的
磷酸钾磷酸钾是钾的磷酸盐，化学式为K3PO4，常见无水物和一水合物。磷酸钾可由磷酸铵（(NH4)3PO4）和氯化钾（KCl）的复分解反应制得，溶解度较小的一者将沉淀：氢氧化钾和磷酸或磷酸二氢钾的反应
加布里埃尔·皮尔纳亨利·康斯坦特·加布里埃尔·皮尔纳（法语：Henri Constant Gabriel Pierné，1863年8月16日－1937年7月17日），法国作曲家，指挥家，管风琴家。1870年入巴黎音乐学院学习，1890-1898年继弗
松下Lumix系列Lumix（徕美）是Panasonic（松下电器）的数码相机系列品牌，于2001年推出。此系列的数码相机特别之处为业内较早引入等效28mm广角镜头（部分机种），使用独有的MEGA O.I.S.镜头防抖功能、高
陶顿战役坐标：53°50′10″N 01°16′25″W / 53.83611°N 1.27361°W / 53.83611; -1.27361陶顿战役爆发于1461年3月29日(棕枝主日)，在约克郡的陶顿（英语：Towton, North Yorkshire）附近，