Data Structures Algorithms 简明教程
Graph Data Structure
What is a Graph?
图是一种抽象数据类型 (ADT)，它包含一组通过链接彼此连接的对象。相互连接的对象由称为 vertices 的点表示，连接顶点的链接称为 edges 。
A graph is an abstract data type (ADT) which consists of a set of objects that are connected to each other via links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
正式来说，图是一对集合 (V, E) ，其中 V 是顶点集合，而 E 是连接顶点对的边缘集合。看看下图 −
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices. Take a look at the following graph −
在上图中，
In the above graph,
V = {a、b、c、d、e}
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Graph Data Structure
数学图形可以用数据结构表示。我们可以使用一个顶点阵列和一个二维边缘阵列表示图形。在进行下一步之前，让我们熟悉一些重要术语 −
Mathematical graphs can be represented in data structure. We can represent a graph using an array of vertices and a two-dimensional array of edges. Before we proceed further, let’s familiarize ourselves with some important terms −
-
Vertex − Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
-
Edge − Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represents edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
-
Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
-
Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.
Operations of Graphs
图的主要操作包括使用顶点和边创建图，并显示所述图。但是，使用图执行的最常见和最流行的操作之一是遍历，即按特定顺序访问图的每个顶点。
The primary operations of a graph include creating a graph with vertices and edges, and displaying the said graph. However, one of the most common and popular operation performed using graphs are Traversal, i.e. visiting every vertex of the graph in a specific order.
图中有两种类型的遍历 −
There are two types of traversals in Graphs −
Depth First Search Traversal
深度优先搜索是一种遍历算法，它以递减的深度顺序访问图的所有顶点。在此算法中，选择一个任意节点作为起点，并通过标记未访问的相邻节点来遍历该图，直到标记所有顶点为止。
Depth First Search is a traversal algorithm that visits all the vertices of a graph in the decreasing order of its depth. In this algorithm, an arbitrary node is chosen as the starting point and the graph is traversed back and forth by marking unvisited adjacent nodes until all the vertices are marked.
DFS 遍历使用堆栈数据结构来跟踪未访问的节点。
The DFS traversal uses the stack data structure to keep track of the unvisited nodes.
Click and check Depth First Search Traversal
Breadth First Search Traversal
广度优先搜索是一种遍历算法，它在移动到下一个深度级别之前，先访问深度一个级别的图的所有顶点。在此算法中，选择一个任意节点作为起点，并通过访问同一深度级别的相邻顶点并标记它们来遍历图，直到没有剩余顶点为止。
Breadth First Search is a traversal algorithm that visits all the vertices of a graph present at one level of the depth before moving to the next level of depth. In this algorithm, an arbitrary node is chosen as the starting point and the graph is traversed by visiting the adjacent vertices on the same depth level and marking them until there is no vertex left.
DFS 遍历使用队列数据结构来跟踪未访问的节点。
The DFS traversal uses the queue data structure to keep track of the unvisited nodes.
Click and check Breadth First Search Traversal
Representation of Graphs
在表示图表时，我们必须仔细描绘图表中存在的元素（顶点和边）以及它们之间的关系。在图片上，用一组有限的节点和它们之间的连接链接来表示一个图表。但是，我们也可以用其他最常用的方式来表示图表，例如 −
While representing graphs, we must carefully depict the elements (vertices and edges) present in the graph and the relationship between them. Pictorially, a graph is represented with a finite set of nodes and connecting links between them. However, we can also represent the graph in other most commonly used ways, like −
-
Adjacency Matrix
-
Adjacency List
Adjacency Matrix
邻接矩阵是一个 V x V 矩阵，其值填充有 0 或 1。如果 Vi 和 Vj 之间存在链接，则记录为 1；否则，记录为 0。
The Adjacency Matrix is a V x V matrix where the values are filled with either 0 or 1. If the link exists between Vi and Vj, it is recorded 1; otherwise, 0.
对于下面给出的图表，让我们构建一个邻接矩阵 −
For the given graph below, let us construct an adjacency matrix −
邻接矩阵为 −
The adjacency matrix is −
Types of graph
有两种基本类型的图——
There are two basic types of graph −
-
Directed Graph
-
Undirected Graph
有向图，顾名思义，由具有从顶点指向外部或指向顶点的方向的边线组成。无向图有完全无方向的边线。
Directed graph, as the name suggests, consists of edges that possess a direction that goes either away from a vertex or towards the vertex. Undirected graphs have edges that are not directed at all.
Directed Graph
Directed Graph
Undirected Graph
Undirected Graph
Spanning Tree
spanning tree 是无向图的子集，其中包含通过图形中最小数量的边缘连接的图形的所有顶点。确切地说，生成树的边是原图中边的一个子集。
A spanning tree is a subset of an undirected graph that contains all the vertices of the graph connected with the minimum number of edges in the graph. Precisely, the edges of the spanning tree is a subset of the edges in the original graph.
如果图中的所有顶点是连接的，那么至少存在一棵生成树。在一个图中，可能存在多棵生成树。
If all the vertices are connected in a graph, then there exists at least one spanning tree. In a graph, there may exist more than one spanning tree.
Minimum Spanning Tree
Minimum Spanning Tree (MST) 是连通的加权无向图的边线的子集，它用最小的总边线权重将所有顶点连接在一起。为了推导 MST，可以使用 Prim 算法或 Kruskal 算法。因此，我们将在本章讨论 Prim 算法。
A Minimum Spanning Tree (MST) is a subset of edges of a connected weighted undirected graph that connects all the vertices together with the minimum possible total edge weight. To derive an MST, Prim’s algorithm or Kruskal’s algorithm can be used. Hence, we will discuss Prim’s algorithm in this chapter.
如我们已经讨论过的，一个图形可能有多个生成树。如果顶点的数量为 n，则生成树应该有 n - l1 数量的边。在此上下文中，如果图形的每条边都与一个权重相关联并且存在多个生成树，我们需要找到图形的最小生成树。
As we have discussed, one graph may have more than one spanning tree. If there are n number of vertices, the spanning tree should have n − l1 number of edges. In this context, if each edge of the graph is associated with a weight and there exists more than one spanning tree, we need to find the minimum spanning tree of the graph.
此外，如果存在任何重复的加权边线，图可能有多个最小生成树。
Moreover, if there exist any duplicate weighted edges, the graph may have multiple minimum spanning tree.
在上述图中，我们展示了一棵生成树，尽管它不是最小生成树。这棵生成树的成本是 (5+7+3+3+5+8+3+4)=38 。
In the above graph, we have shown a spanning tree though it’s not the minimum spanning tree. The cost of this spanning tree is (5+7+3+3+5+8+3+4)=38.
Shortest Path
图中最短的路径被定义为从一个顶点到另一个顶点的最小成本路线。这在加权有向图中最常见，但也可以应用于无向图。
The shortest path in a graph is defined as the minimum cost route from one vertex to another. This is most commonly seen in weighted directed graphs but are also applicable to undirected graphs.
在图形中找到最短路径的一个流行的现实世界应用程序是一张地图。导航变得更容易和更简单，其中各种最短路径算法将目的地视为图形的顶点，而路线是边。两种常见的最短路径算法是 −
A popular real−world application of finding the shortest path in a graph is a map. Navigation is made easier and simpler with the various shortest path algorithms where destinations are considered vertices of the graph and routes are the edges. The two common shortest path algorithms are −
-
Dijkstra’s Shortest Path Algorithm
-
Bellman Ford’s Shortest Path Algorithm