想问一个关于邻接表的问题 - 编程论坛

书生牛犊2016-12-03 22:11

数组[V1]  [V2]  [V3]  [V4]  [V5]  [V6]
   |    |   |    |   |    |
{V4.V2} {V5.V3} {V6}  {V2}  {V6}   {}

邻接表就是这样子建一个数组用于存放图中所有结点，数组中的每一个元素是一个链表，表示该节点链接向哪些其他节点。
如上就是你给的“有向图”例子的邻接矩阵表达方法。

xzlxzlxzl2016-12-04 11:16

刚刚恶补了下相关知识，有了些理解，希望对题主有帮助。
首先要更正下对链表的理解：大多数情况下我们理解链表总理解为上下级的关系，即下个节点率属于上个节点，在二叉树里更直观地认为是父节点、子节点，这种先入为主的概念很容易禁锢我们的观点，导致对链表使用局限。其实链表也可以表示为动态数组，数组的元素并无上下级关系，是平等的，连起来仅仅是为了好搜索数组内元素。因此，你完全可以不用链表来表示邻接表，而用一个足够大的数组来表示顶点相邻的关系，只不过用链表更灵活。
有了这个认识，就可以来表述邻接表了：邻接表首先由一个表头，用于存储顶点信息，因为定点数不固定，所以表头也可以用一个链表存储，表头定义为{顶点名称，邻接表指针，下个顶点指针},题主实例有6个顶点，则表头链表有6个元素，邻接表定义为{权值,顶点名称,下个元素指针}，有了这些数据结构定义，则题主实例邻接表可表述如下：
表头：{V1,V1邻接表,指向V2}{V2,V2邻接表,指向V3}{V3,V3邻接表,指向V4}{V4,V4邻接表,指向V5}{V5,V5邻接表,指向V6}{V6,V6邻接表,NULL}
V1邻接表:{1,V4,指向下个元素}{1,V2,NULL}
V2邻接表:{1,V5,指向下个元素}{1,V3,NULL}
.
.
.
V6邻接表:{0,0，NULL}

大致如此吧，期待大神指正！