图论其实不难入门

图论其实不难入门-51CTO.COM

对于有多年的编程经验的开发者来说，图的概念并不陌生。许多顶级公司在技术面试中测试对图论的理解。 其实，开发者无需处理高级问题即可利用这些概念。要想明白这一点，我们可以先回顾一下为什么图是流行的数据结构以及如何在代码中实现它们。

无论编码经验如何，开发者都应该对数组和字典的数据类型有所了解。 这些集合是大多数语言中使用的标准概念，在呈现基于列表的内容时效果很好：

 

大多数情况下，列表是从数据库或基于 REST 的查询中显示信息的完美解决方案。 然而，有时列表需要提供存在相互关联的上下文的记录。此时，将数据组织为图表变得方便。

对于图表，主要目标不是列出信息（尽管这一点可以做到），而是定义对象之间的关系。为什么定义对象之间的关系会有用？不妨看看以下几个例子。

 

一个有两个顶点和一个边的无向图

（1）地图应用程序：

如果在技术面试中被问到，你将如何组织数据，以便重新创建地图服务（如 Apple 或 Google Maps）？除了在数据库中提供所有已知道路的列表外，你创建的模型还需要根据一天中的时间、交通和单行道等因素确定到达目的地的最佳方式。要使这大量的数据有效，您需要知道一条道路与模型中的所有其他街道之间的关系。

（2）社交媒体：

一个社交媒体的价值，通常由用户关注或关注用户的人数来衡量。像Twitter这样的网络平台可以让用户与任何人联系，并接收他们的最新动态，从而吸引了大量用户。

 LinkedIn模型更为详细，因为除非接收者接受用户的连接请求，否则用户无法将某人添加到该用户的网络中。在这种情况下，LinkedIn连接代表双向关系。顺着这个思路，用户也可以搜索其人际网络中是否有人与其想要的工作机会相关联。在这种情况下，“网络”可能意味着直接或间接的联系。这样一个强大的模型不仅仅是基于一个简单的列表，它还包含了确定所有配置文件如何关联的智慧。

现在我们已经了解了图在日常应用程序中的使用方式，下面我们来介绍图的组成部分。

图中的节点称为顶点。虽然可以将图构建为单个顶点，但包含多个顶点的模型可以更好地代表现实世界的应用。

图中的对象通过称为边的连接相互关联。

根据您的需求，顶点可以通过边连接到一个或多个物体上，也可以创建一个没有边的顶点。

最后，与堆栈或队列等其他标准结构不同，图通常没有指定的起点或终点。 以下是一些示例图形配置：

 

一个有两个顶点和一个边的无向图

 

一个有两个顶点和一个边的无向图

 

一个有两个顶点和一个边的无向图

有向与无向

在无向图中，源顶点和目标之间的连接是相等的。这些模型代表双向连接——类似于地图应用程序中的双向街道。

要定义单向连接，我们可以使用线和箭头将模型更新为有向图：

 

三个顶点和三个边的有向图

连通性水平

有时，我们必须表示图中顶点之间的连接程度。这种技术在量化节点之间的距离、时间或严重性时效果很好。权值通常与一条边相关，是一个用于跟踪的比较变量。 。

 

三个顶点和三个边的有向图，其中边加权

有了对图论的基本了解后，让我们看看如何在代码中复制这些模型。下面我们创建了一个支持自定义通用对象 (T) 的顶点。 tvalue变量表示该类型保存的数据，包括单个字符串、int或自定义类型（例如，街道名称或社交媒体资料）。

另外，注意要让我们的类型符合流行的Equatable协议 (Swift)。这可以让我们在需要时比较特定顶点实例是否相等。

public class Vertex <T> : Equatable {

​var tvalue: T?

​var neighbors = Array<Edge<T>>()

​let uuid = UUID()

​public init(with name: T) {

    self.tvalue = name

​//equatable conformance

​public static func == (lhs: Vertex, rhs: Vertex) -> Bool {

     return lhs.uuid == rhs.uuid

邻接表表示与其他顶点的连接。如前面所述，每个顶点可以连接到一个或多个邻接的点。 这种关系列表有时称为“邻接表”，可以用来解决许多高级问题。

var neighbors = Array<Edge<T>>()

在创建顶点时，我们添加了一个邻接属性来存储自定义边类型的数组。 下面一条边为后续的相邻顶点及其潜在的边的权值提供参考。

public class Edge <T> {

​var neighbor: Vertex<T>

​var weight: Int

​init() {

     weight = 0

     self.neighbor = Vertex<T>()

有了顶点和边对象，我们现在可以将它们添加到中央存储结构中，我们称之为图形画布。尽管我们的画布在技术上是一个数组，但我们的目标是将集合可视化为一组关系。 借助addVertex 函数，我们可以向画布添加单个通用顶点，同时addEdge方法可提供边所需的参考信息。

最后，我们的代码假设图是有向的，因为边（仅）被添加到源顶点邻接表中。

public class Graph <T> {

​var canvas: Array<Vertex<T>>

   public init() {

     canvas = Array<Vertex>()

​//add vertex to graph canvas

​public func addVertex(element: Vertex<T>) {

     canvas.append(element)

      /add edge

​public func addEdge(source: Vertex<T>, neighbor: Vertex<T>, weight: Int) {

     //create a new edge

     let newEdge = Edge<T>()

       //connect source vertex to neighboring edge

     newEdge.neighbor = neighbor

     newEdge.weight = weight

     source.neighbors.append(newEdge)

总之，我们介绍了图的有关知识，并了解了如何使用它们来表示对象之间的关系，还回顾了配置图的几种方法以及用于描述不同模型的组件。

定义了模型后，我们就为更高级的功能奠定了基础，包括图形导航和遍历算法，如广度优先搜索。

康少京，51CTO社区编辑，目前从事通讯类行业，底层驱动开发岗位，研究过数据结构，Python，现对操作系统和数据库等相关领域感兴趣。

 原文标题：The complete beginner’s guide to graph theory，作者：Wayne Bishop

https://stackoverflow.blog/2022/05/26/the-complete-beginners-guide-to-graph-theory/