10 数据结构第六章 图知识点.docx

"图结构知识点" 图结构是数据结构中的一种重要类型，广泛应用于计算机科学和信息技术领域。图结构可以用来表示复杂的关系和网络结构。在本节中，我们将详细介绍图结构的基本概念、术语和存储方法。 图的定义：图是顶点的有穷非空集合和顶点之间边的集合组成的，记为 G=(V,E)。其中，V 是顶点集合，E 是边集合。 图的基本术语： * 邻接：在无向图中，如果两个顶点之间存在边，则称这两个顶点是邻接的。 * 依附：在无向图中，如果一个顶点和边相连，则称该顶点依附于该边。 * 无向图：在图中，所有边都是无向的。 * 有向图：在图中，所有边都是有向的。 * 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。 * 有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。 * 稀疏图：称边数很少的图为稀疏图。 * 稠密图：称边数很多的图为稠密图。 度、入度、出度： * 顶点的度：在无向图中，顶点 v 的度是指依附于该顶点的边数，通常记为 TD(v)。 * 顶点的入度：在有向图中，顶点 v 的入度是指以该顶点为弧头的弧的数目，记为 ID(v)。 * 顶点的出度：在有向图中，顶点 v 的出度是指以该顶点为弧尾的弧的数目，记为 OD(v)。 权、网权： * 权：是指对边赋予的有意义的数值量。 * 网：边上带权的图，也称网图。 路径： * 路径：从顶点 vp 到顶点 vq 之间的路径是一个顶点序列(vp=vi0,vi1,vi2, …, vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。 * 路径长度：非带权图——路径上边的个数；带权图——路径上各边的权之和。 回路、简单路径、简单回路： * 回路：第一个顶点和最后一个顶点相同的路径。 * 简单路径：序列中顶点不重复出现的路径。 * 简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。 子图： * 子图：若图 G=（V，E），G'=（V'，E'），如果 V'￿V 且 E' ￿ E，则称图 G' 是 G 的子图。 连通图、连通分量： * 连通图：如果图中任意两个顶点有路径，则称该图是连通图。 * 连通分量：非连通图的极大连通子图称为连通分量。 强连通图、强连通分量： * 强连通图：在有向图中，任意两个顶点之间有路径。 * 强连通分量：非强连通图的极大强连通子图。 生成树： * 生成树：n 个顶点的连通图 G 的生成树是包含 G 中全部顶点的一个极小连通子图。 深度优先遍历和广度优先遍历： * 深度优先遍历：从某个顶点出发，沿着边访问图中的顶点，until 遍历完所有顶点。 * 广度优先遍历：从某个顶点出发，访问所有与其邻接的顶点，然后访问所有与这些顶点邻接的顶点，以此类推，until 遍历完所有顶点。 图的存储方法： * 邻接矩阵：Vertex[5] = ABCDE01110001100100101101101arc[5][5]=010101、主对角线为 0、对称矩阵 * 邻接表：0A1B2C3D4E1、占用空间 n+2e、O（n+e） 有向图的存储方法： * 邻接矩阵：Vertex[5] = ABCDE01110000110000000101arc[5][5]=000001、主对角线为 0、可能是对称矩阵 * 邻接表：0A1B2C3D4E1、占用空间 n+2e、O（n+e） * 逆邻接表：CDEAB12334、占用空间 n+2e、O（n+e）