复试机试算法总结#10:图论
1. 图的存储1.1 邻接矩阵用一个二维矩阵表示图的信息,其中每一个单元都表示一对顶点间的邻接关系。对于无权图,单元的值用1或0表示两点间有无边;对于带权图,单元的值表示权值。不存在的边,单元值取无穷大;有向图的表示同理。适用于:稠密图、频繁判断特定顶点对是否相邻1.2 邻接表用动态分配的链表来替代静态分配的空间,依次提升效率。为每个结点建立一个单链表,保存与该结点相邻的所有结...