链式前向星

✍ dations ◷ 2024-12-23 01:09:51 #软件,数据结构,存储软件

链式前向星是一种用于存储图的数据结构，一般认为是由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++代码实现：

相关

语言地理学语言地理学（英文：linguistic geography）是人文地理学或是语言学下的一个分支，主要研究语言的地理变异和语言变体的空间分布。广义的语言地理学包括了地理语言学。当研究的目标为
调频电台调频广播（英语：Frequency Modulation Broadcast，常缩写为FM广播）是一种以频率调制技术来传送高保真声音的无线电广播技术，由爱德温·霍华·阿姆斯壮（Edwin Howard Armstrong）发明。
艾萨克·布洛克艾萨克·布洛克爵士（Sir Isaac Brock，1769年10月6日－1812年10月13日），英国陆军少将。1812年战争初期，他在上加拿大地区击退美军的进攻，并发动反击攻入美领五大湖地区，在8月中旬的底
华金·巴拉格尔华金·安东尼奥·巴拉格尔·里卡尔多（ Joaquín Antonio Balaguer Ricardo，1906年9月1日—2002年7月14日），多米尼加共和国总统(1960-1962、1966-1978、1986-1996)。巴拉格尔生于
亚铁氰化钠亚铁氰化钠，一般为十水合物形式，化学式Na4Fe(CN)6·10H2O。亚铁氰化钠是一种柠檬黄色单斜晶系的棱形或针状结晶，溶于水，不溶于醇。在空气中易风化，在50～60 °C的条件下晶体会很快
史都华镇 (宾夕法尼亚州)史都华镇是位于美国宾夕法尼亚州费耶特县的一个镇。在2000年的人口普查，该镇有 743 位居民。根据美国人口调查局的调查，史都华镇总面积 132.4 平方公里。其中 131.2 平方公里
Weekender/向明天的YELL“Weekender / 向明天的YELL”(ウィークエンダー/明日へのYELL) 是Hey!Say!JUMP的第13张单曲。于2014年9月3日由J Storm发售。与前作“AinoArika/尽情去爱的HAPPY LIFE”相
山崳基三甲基氯化铵二十二烷基三甲基氯化铵，或山崳基三甲基氯化铵，是一种刺激性、对水生生物有毒、轻度易燃的黄色蜡状有机化合物，分子式为CH3(CH2)21N(Cl)(CH3)3，一般常用作防静电剂及杀虫剂。它
同庆帝同庆帝（越南语：Vua Đồng Khánh／.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-H",
劳伦士劳伦士（Lorinser) 创立于1935年，工厂位在德国斯图加特，是为专业于戴姆勒旗下厂牌梅赛德斯-奔驰及司麦特改装厂。在维持梅赛德斯-奔驰原创精神和品牌形象的前提下，对于车款升级及