图形数据结构
图是一组对象的图形表示,其中一些对象对通过链接连接。互连的对象由称为
vertices的点表示,连接顶点的链接称为
edges。
形式上,图是一对集合
(V, E),其中
V是顶点的集合,
E是一组边,连接顶点对。看看下图-
在上图中,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
图形数据结构
数学图可以用数据结构来表示。我们可以使用一个顶点数组和一个二维边数组来表示一个图。在我们继续之前,让我们熟悉一些重要的术语-
Vertex-图中的每个节点都表示为一个顶点。在以下示例中,标记的圆圈表示顶点。因此,A 到 G 是顶点。我们可以使用数组来表示它们,如下图所示。这里 A 可以通过索引 0 来识别。B 可以通过索引 1 来识别,依此类推。
Edge-边表示两个顶点之间的路径或两个顶点之间的线。在以下示例中,从 A 到 B、B 到 C 等的线表示边。我们可以使用二维数组来表示数组,如下图所示。这里 AB 可以在第 0 行第 1 列表示为 1,BC 在第 1 行第 2 列表示为 1,依此类推,其他组合保持为 0。
Adjacency-如果两个节点或顶点通过边相互连接,则它们是相邻的。在以下示例中,B 与 A 相邻,C 与 B 相邻,依此类推。
Path-路径表示两个顶点之间的一系列边。在以下示例中,ABCD 表示从 A 到 D 的路径。
基本操作
以下是 Graph 的基本主要操作-
Add Vertex-向图中添加一个顶点。
Add Edge-在图的两个顶点之间添加一条边。
Display Vertex-显示图形的一个顶点。
要了解更多关于图的知识,请阅读图论教程。我们将在接下来的章节中学习如何遍历图。