图(一):图的定义、分类及存储结构 |
您所在的位置:网站首页 › 图的平行边定义 › 图(一):图的定义、分类及存储结构 |
一、图的定义
在数据结构中,图的定义为:由一组顶点和一组能够将两个顶点相连的边组成的。 注意,特殊的图由下面几种: 自环:即一条连接一个顶点和其自身的边。 平行边:连接同一对顶点的两条边。在后面的数据结构学习中,我们并不对上面的 自环 和 平行边 进行讲述。 二、图的分类及相关术语 1. 图的分类按照连接两个顶点的边的类型不同,可以把图分为一下两种: 无向图:边仅仅连接两个顶点,没有其他含义。 有向图:边不仅连接两个顶点,且具有方向。 2. 无向图相关术语相邻顶点:当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点。 度:某个顶点的度就是依附于该顶点的边的个数。 子图:子图是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。 路径:是由边顺序连接的一系列的顶点组成。 环:是由至少至少含有一条边且终点和起点相同的路径。 连通图:如果图中任意一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为连通图。 连通子图:一个非连通图由若干连通的部分组成,每一个连通的部分都可以称之为连通子图。 下面是连通图和连通子图的示意图: 有向图:一幅有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连着一对有序的顶点。 出度:由某个顶点指出的边的个数称为该顶点的出度。 入度:指向某个顶点的边的个数称为该顶点的入度。 有向路径:由一系列顶点组成,对于其中的每个顶点都存在一条有向边,从它指向序列中的下一个顶点。 有向环:一条至少含有一条边,且起点和终点相同的有向路径。 在有向图中,两个顶点v和w之间可能存在以下四种关系: 1. 没有边相连. 2. 存在从v到w的边:v --> w. 3. 存在从w到v的边:w --> v. 4. 既存在w到v的边,也存在v到w的边,即双向连接. 三、图的存储结构想要标识一副图,只需要表示清楚以下两部分内容即可: 1.图中所有的顶点。 2.所有连接顶点的边。 常见的图的存储结构有两种:邻接矩阵和邻接表。 1. 邻接矩阵使用一个V*V的二维数组int[V][V]adj,把索引的值看做是顶点。 如果顶点v和顶点w相连,我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。
很明显,邻接矩阵的空间复杂度为V^2,如果数据量很大的时候,内存空间极有可能是不够用的。 2.邻接表使用一个大小为V的数组Queue[v] adj,把索引看做是顶点。 每个索引处adj[v]存储了一个队列,该队列中存储的是所有与该顶点相邻的其它顶点。 显然,邻接表的空间复杂度是相对不错的,后面开发的过程中,我们会一直采用这种存储方式来表示图。
|
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |