欢迎大家来到IT世界,在知识的湖畔探索吧!
有向图,顾名思义,就是有方向的图,这点就是和无向图最大的区别,那么今天我们来讨论一下有向图的邻接矩阵和邻接表究竟有什么区别。
首先是无向图
如图所示,这张图就是一张无向图,画得有点不好看,先容忍一下了,我们要写出这张无向图的邻接矩阵和邻接表,那么我们首先来看看邻接矩阵和邻接表的概念。
邻接矩阵:邻接矩阵是表示顶点之间相邻关系的矩阵,分为两部分V和E,用一堆数组来存放图中的所有数据。
如图所示,就是无向图的邻接矩阵,A到A的距离是0,然后像A到E的距离没法计算,我就用无穷∞这个符号来表示了。
接下来是邻接表。
邻接表:是顺序分配和链式分配相结合的存储结构,对于无向图来说,容易出现数据冗余。
如图所示,这就是无向图的邻接表,容易出现数据冗余,因为可以发现,表头结点A所指链表中存在一个指向B的表结点时,表头节点B所指链表也会存在一个指向A的表结点。
接下来我们来看看有向图的邻接矩阵和邻接表。
如图所示,这是一张有向图,我们来看看这张有向图的邻接矩阵和邻接表应该怎么画。
首先我们要确定一点,B到A的距离为2,但是A是到不了B的,那显然就走0即可。
所以可以得到:
如图所示,给出该有向图的邻接矩阵。
接下来我们来看该有向图的邻接表。
如图所示,这就是该有向图的邻接表。
最后做个总结,邻接矩阵和邻接表并不是很难,关键在于我们要认真分析,仔细一点,就不大容易做错了,而且要考虑周全。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/22951.html