设计网站建设公司,广西人才网,wordpress 全站404,延吉市建设厅网站图的基本介绍
为什么要有图这个基本数据结构?
我们还学习过线性表#xff08;数组、队列、链表和栈#xff09;和树#xff0c;但是我们可以发现#xff0c;线性表局限于一个直接前驱#xff08;就是只能有唯一一个前面的结点#xff09;和一个直接后继的#xff08;…图的基本介绍
为什么要有图这个基本数据结构?
我们还学习过线性表数组、队列、链表和栈和树但是我们可以发现线性表局限于一个直接前驱就是只能有唯一一个前面的结点和一个直接后继的唯一一个后面的结点关系。树也只能有一个直接前驱也就是父节点。但是当我们如果想要表示多对多的关系时前面所学习的数据结构就不能满足我们的需求了这时候我们就需要图这个数据结构
图的举例说明
图是一种数据结构其中结点可以具有零个或多个相邻的元素两个结点之间的链接称为边。结点也可以称为顶点。
图的常用概念
顶点图的每个结点就是顶点例如B
边(edge)图中两个顶点之间的线就叫做边例如A和B之间的连线
路径路径就是从某个顶点到另一个顶点索要经过的所有顶点例如从 D - C 的路径有①D-B-C ② D-A-B-C
无向图就是两个相邻顶点间没有指明方向例如可以从B到A也可以从A到B 有向图 带权图。例如下图中两顶点中的权就是两地的距离 图的表示方式
图的表示方式有两种二维数组表示邻接矩阵链表表示邻接表
邻接矩阵 二位数组中的0表示的是两节点之间不能直接连通1表示能直接连通
邻接表
邻接矩阵需要为每个顶点都分配n个边的空间其实有很多边都是不存在,会造成空间的一定损失.
邻接表的实现只关心存在的边不关心不存在的边。因此没有空间浪费邻接表由数组链表组成
