Data Structures Algorithms 简明教程
Graph Data Structure
What is a Graph?
图是一种抽象数据类型 (ADT)，它包含一组通过链接彼此连接的对象。相互连接的对象由称为 vertices 的点表示，连接顶点的链接称为 edges 。
正式来说，图是一对集合 (V, E) ，其中 V 是顶点集合，而 E 是连接顶点对的边缘集合。看看下图 −
在上图中，
V = {a、b、c、d、e}
E = {ab, ac, bd, cd, de}
Graph Data Structure
数学图形可以用数据结构表示。我们可以使用一个顶点阵列和一个二维边缘阵列表示图形。在进行下一步之前，让我们熟悉一些重要术语 −
-
Vertex − 图形的每个节点表示为一个顶点。在下例中，有标签的圆表示顶点。因此，A 到 G 是顶点。我们可以使用一个数组表示它们，如下面的图像所示。这里可以通过索引 0 识别 A。可以通过索引 1 识别 B，依此类推。
-
Edge − 边表示两个顶点之间的路径或两条顶点之间的线。在以下示例中，从 A 到 B，从 B 到 C 的线等表示边。我们可以使用一个二维数组来表示一个数组，如下面的图像所示。这里 AB 可以在第 0 行，第 1 列中表示为 1，BC 在第 1 行，第 2 列中表示为 1，依此类推，而其他组合保持为 0。
-
Adjacency − 如果两个节点或顶点通过一条边相互连接，则它们是相邻的。在以下示例中，B 邻接到 A，C 邻接到 B，依此类推。
-
Path − 路径表示两个顶点之间的边缘序列。在以下示例中，ABCD 表示从 A 到 D 的路径。
Operations of Graphs
图的主要操作包括使用顶点和边创建图，并显示所述图。但是，使用图执行的最常见和最流行的操作之一是遍历，即按特定顺序访问图的每个顶点。
图中有两种类型的遍历 −
Depth First Search Traversal
深度优先搜索是一种遍历算法，它以递减的深度顺序访问图的所有顶点。在此算法中，选择一个任意节点作为起点，并通过标记未访问的相邻节点来遍历该图，直到标记所有顶点为止。
DFS 遍历使用堆栈数据结构来跟踪未访问的节点。
Representation of Graphs
在表示图表时，我们必须仔细描绘图表中存在的元素（顶点和边）以及它们之间的关系。在图片上，用一组有限的节点和它们之间的连接链接来表示一个图表。但是，我们也可以用其他最常用的方式来表示图表，例如 −
-
Adjacency Matrix
-
Adjacency List
Types of graph
有两种基本类型的图——
-
Directed Graph
-
Undirected Graph
有向图，顾名思义，由具有从顶点指向外部或指向顶点的方向的边线组成。无向图有完全无方向的边线。
Directed Graph
Undirected Graph
Spanning Tree
spanning tree 是无向图的子集，其中包含通过图形中最小数量的边缘连接的图形的所有顶点。确切地说，生成树的边是原图中边的一个子集。
如果图中的所有顶点是连接的，那么至少存在一棵生成树。在一个图中，可能存在多棵生成树。
Minimum Spanning Tree
Minimum Spanning Tree (MST) 是连通的加权无向图的边线的子集，它用最小的总边线权重将所有顶点连接在一起。为了推导 MST，可以使用 Prim 算法或 Kruskal 算法。因此，我们将在本章讨论 Prim 算法。
如我们已经讨论过的，一个图形可能有多个生成树。如果顶点的数量为 n，则生成树应该有 n - l1 数量的边。在此上下文中，如果图形的每条边都与一个权重相关联并且存在多个生成树，我们需要找到图形的最小生成树。
此外，如果存在任何重复的加权边线，图可能有多个最小生成树。
在上述图中，我们展示了一棵生成树，尽管它不是最小生成树。这棵生成树的成本是 (5+7+3+3+5+8+3+4)=38 。