| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1657 人关注过本帖
标题:想问一个关于邻接表的问题
只看楼主 加入收藏
我叫赫卡忒
Rank: 1
来 自:北京
等 级:新手上路
帖 子:19
专家分:0
注 册:2016-9-22
结帖率:50%
收藏
 问题点数:0 回复次数:2 
想问一个关于邻接表的问题
没怎么听懂老师讲的东西,所以不太会写某个图的邻接表,能讲讲吗?比如下面这个例子
  V1→V4
  ↓ ↙↓
  V2→V5
  ↓↖↓
  V3→V6
2016-12-02 18:03
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
数组[V1]  [V2]  [V3]  [V4]  [V5]  [V6]
   |    |   |    |   |    |
 {V4.V2} {V5.V3} {V6}  {V2}  {V6}   {}

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


φ(゜▽゜*)♪
2016-12-03 22:11
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
刚刚恶补了下相关知识,有了些理解,希望对题主有帮助。
首先要更正下对链表的理解:大多数情况下我们理解链表总理解为上下级的关系,即下个节点率属于上个节点,在二叉树里更直观地认为是父节点、子节点,这种先入为主的概念很容易禁锢我们的观点,导致对链表使用局限。其实链表也可以表示为动态数组,数组的元素并无上下级关系,是平等的,连起来仅仅是为了好搜索数组内元素。因此,你完全可以不用链表来表示邻接表,而用一个足够大的数组来表示顶点相邻的关系,只不过用链表更灵活。
有了这个认识,就可以来表述邻接表了:邻接表首先由一个表头,用于存储顶点信息,因为定点数不固定,所以表头也可以用一个链表存储,表头定义为{顶点名称,邻接表指针,下个顶点指针},题主实例有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}

大致如此吧,期待大神指正!
2016-12-04 11:16
快速回复:想问一个关于邻接表的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.013079 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved