出处：信息科学卷 • 计算机科学技术 • 软件与系统
| 词条 | 邻接表 |
| 释义 | 邻接表 邻接表 图最常用的存储方式。分两部分存储一个图，即存储顶点和存储边。顶点集用一个数组存储。从某个顶点出发的所有边组织成一个单链表。存储顶点的数组的每个元素由两部分组成，即顶点值和指向该顶点对应的单链表的指针。如果是非加权图，单链表的结点由两部分组成：边的终止顶点编号（存储终止顶点的数组元素的下标）和后继指针。如果是加权图，单链表的结点由三部分组成：边的终止顶点编号、边的权值和后继指针。如果图中有N个顶点E条边，最坏情况下，插入一条边、删除一条边以及判断两个顶点之间是否有边的时间复杂度是O（N），但查找进入某个顶点的边的时间复杂度是O（E）。空间性能良好。 出处：信息科学卷 • 计算机科学技术 • 软件与系统 |
| 随便看 |
百科全书收录258893条中英文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。