by Michael Olorunnisola

通过Michael Olorunnisola

数据结构的简要介绍：图形如何工作 (A Gentle Introduction to Data Structures: How Graphs Work)

So who wants to work at Google, Facebook, or maybe LinkedIn? Beyond their grueling interview process, one thing all these companies have in common is their heavy reliance on the graph data structure.

那么，谁想在Google，Facebook或LinkedIn工作？ 除了艰苦的采访过程外，所有这些公司的共同点是，他们严重依赖图形数据结构。

After learning a bit about graphs, you’ll understand why. By the end of this post, you’ll feel more comfortable jumping into Cracking the Coding Interview — or a similar interview prep book — and knocking out some network traversal algorithms practice problems.

在学习了一些关于图形的知识之后，您将了解原因。 到本文结束时，您会更轻松地进入“ 破解编码面试”或类似的面试准备书，并剔除一些网络遍历算法的实践问题。

图如何工作 (How Graphs Work)

Graphs are a powerful and versatile data structure that easily allow you to represent real life relationships between different types of data (nodes). There are two main parts of a graph:

图形是功能强大且用途广泛的数据结构，可以轻松地表示不同类型的数据(节点)之间的现实关系。 图有两个主要部分：

• The vertices (nodes) where the data is stored i.e. the numbers in the image on the left

  存储数据的顶点(节点)， 即左侧图像中的数字

• The edges (connections) which connect the nodes i.e. the lines between the numbers in the image

  连接节点的边缘(连接)， 即图像中数字之间的线

Graphs can be undirected or directed. Using the graph above as an example — and treating the edges as every day relationships — here’s the difference:

图可以是无向或有向的 。 以上面的图表为例-将边缘视为每天的关系-区别在于：

Undirected graph: If 6 was a friend of 4, 4 would likewise be a friend of 6. The relationship exists in both directions.

无向图：如果6是4的朋友，则4也会是6的朋友。这种关系在两个方向上都存在。

Directed graph: if 6 had a crush on 4, that doesn’t necessarily mean 4 has to have a crush on 6. Love’s tough ?. The relationships are based on the direction of the edges. It can be a one way relationship or a two-way relationship, but it must be explicitly stated.

有向图：如果6对4暗恋，那并不一定意味着4必须对6暗恋。 关系基于边缘的方向。 它可以Bé单向关系Ø 为r的双向关系，但必须明确说明。

Here are some common operations you can perform on graphs:

以下是您可以在图表上执行的一些常见操作：

Additions

加法

• addNode: adds vertices to your graph

  addNode ：将顶点添加到图形中

• addEdge: creates edges between two given vertices in your graph

  addEdge ：在图形中的两个给定顶点之间创建边

Removals

清除

• removeNode: removes vertices from your graph

  removeNode ：从图形中删除顶点

• removeEdge: removes edges between two given vertices in your graph

  removeEdge ：删除图形中两个给定顶点之间的边

Search

搜索

• contains: checks if your graph contains a given value

  contains ：检查图形是否包含给定值

• hasEdge: checks if a connection exists between two given nodes in your graph

  hasEdge ：检查图形中两个给定节点之间是否存在连接

In addition to this, graphs can be weighted or unweighted. All this means is that there is some value or cost associated with the edges between the vertices. The best example of this would be google maps.

除此之外，图形可以加权或不加权。 所有这些意味着与顶点之间的边相关联的有一些价值或成本。 最好的例子就是谷歌地图。

As you can see, there are two suggested routes between Mumbai and Delhi. But how would a Google graph algorithm know that one in blue is the best option? Simple. You give the different routes (edges) weights equivalent to their distances. Knowing that, the algorithm can deduce that one path is 50km shorter than the other, and probably faster.

如您所见，孟买和德里之间有两条建议的路线。 但是Google图形算法如何知道蓝色为最佳选择？ 简单。 您给不同的路线(边)权重等于它们的距离。 知道这一点，该算法可以推断出一条路径比另一条路径短50km，并且可能更快。

Of course, there are other factors given weight like delays and speed limits. But the concept remains the same. Weighted graphs allow you to choose the quickest path, or the path of least resistance (see Dijkstra’s Algorithm).

当然，还有其他一些因素会给人以重量，例如延迟和速度限制。 但是概念保持不变。 加权图使您可以选择最快的路径或阻力最小的路径(请参见Dijkstra的算法 )。

As you can see from these examples, graphs can show almost any type of relationship with just data and edges. This is why graphs have become so widely used by companies like LinkedIn, Google, and Facebook. Just read this post by Facebook about why they made the transition back in 2007 from relational databases to graph databases.

从这些示例中可以看到，图形可以显示几乎任何类型的关系，而只有数据和边。 这就是为什么图已被LinkedIn，Google和Facebook等公司广泛使用的原因。 只需阅读Facebook的这篇文章，了解他们为何在2007年从关系数据库过渡到图形数据库。

Now that you have a basic understanding of what graphs are, let’s explore some examples.

现在，您已经对什么是图形有了基本的了解，让我们探索一些示例。

Example Use Cases:

用例示例：

• Representing a social network
  代表社交网络
• Representing maps
  代表地图
• Killing interview questions
  杀死面试问题

The last one there is up to you. If you’re getting ready for a coding interview, I’ve included some helpful additional resources at the end of this post.

最后一个取决于您。 如果您准备进行编码面试，那么本文结尾处将提供一些有用的其他资源。

In the mean time, let’s take a stab at social networks.

同时，让我们来看看社交网络。

使用图建立社交网络 (Building a social network using graphs)

Since Facebook kind of has a monopoly on this whole social network thing, how about we create a private social network for developers? DevBook! Of course, we could keep things simple and just create a Facebook group instead… But being grade A developers who love a good challenge, let’s take a prideful moment to throw “KISS” out the window.

由于Facebook在整个社交网络上都有垄断地位，我们如何为开发人员创建私有社交网络呢？ DevBook！ 当然，我们可以保持简单，而只需创建一个Facebook组即可。但是，作为热爱挑战的A级开发人员，让我们度过一个自豪的时刻，将“ KISS”扔出窗外。

First you create the storage for your graph. You realize there are probably multiple ways you can represent a graph data structure, but for now you decide upon a list that will store each unique developer as a key and all their connections as their associated values. Upon running a quick Google search, you realize that you’re making an adjacency list.

首先，为图形创建存储。 您意识到可能有多种方法可以表示图形数据结构，但是现在，您决定一个列表，该列表将每个唯一的开发人员存储为键，并将其所有连接存储为关联值。 在进行快速的Google搜索后，您会发现自己正在创建邻接表。

You prefer following a functional pattern, so you decide to go the route below:

您更喜欢遵循一种功能模式，因此决定采用以下路线：

let MakeGraph = () => {   // Function that will create our graphs  let graph = {};  return graph;}

let devBook = MakeGraph();  // Our graph representing our site

Now that you have the graph representation, you need to create a way to add developers to the graph when they sign up, and to store any future connections they might have.

现在，您已经有了图形表示形式，您需要创建一种方法，在开发人员注册时将其添加到图形中，并存储他们将来可能拥有的任何连接。

You decide to make the users keys on the object, and use an object with an edges property to keep a list of their connections.

您决定将用户键放在对象上，并使用具有edges属性的对象保留其连接列表。

let MakeGraph = () => {     let graph = {};

graph.addVertex = (node) => {       // add members as vertices here     //  store their connections as properties on an edges object        graph[node] = {edges:{}};  }

return graph;}

let devBook = MakeGraph();

devBook.addVertex('James Gosling');devBook.addVertex('Guido Rossum');devBook.addVertex('Linus Torvalds');devBook.addVertex('Michael Olorunnisola');

// Your graph will now look like this:

{ addVertex: [Function],  'James Gosling': { edges: {} },  'Guido Rossum': { edges: {} },  'Linus Torvalds': { edges: {} },  'Michael Olorunnisola': { edges: {} } }

Note that in practice, you would want to store records with unique user id’s instead of names that couldn’t be overwritten by other users with the same name, but I’ve used the names of famous programmers (plus myself) for flavor.

请注意，实际上，您将要存储具有唯一用户ID的记录，而不是不能被其他具有相同名称的用户覆盖的名称存储的记录，但是我使用了著名程序员(加上我自己)的名字来修饰。

Now you can build a contains method to check whether a user has already been stored on your graph, and prevent the overwriting of any of the relationships that are created as the site grows.

现在，您可以构建一个contains方法，以检查用户是否已经存储在图形上，并防止覆盖随着站点增长而创建的任何关系。

let MakeGraph = () => {   let graph = {};

graph.contains = (node)=> { // you can check whether a user exists    return !!graph[node];  }

graph.addVertex = (node) => {     if(!graph.contains(node)){ // call contains to prevent overwrite      graph[node] = {edges:{}};    }  }

return graph;}

Great! Now that you have a good set of unique users, you want to let them connect with each other by creating friendships with each other (edges). These edges won’t be directed, as you realize friendships don’t really work that way.

大！ 现在您已经拥有了很多独特的用户，您希望通过彼此之间的友谊(边缘)来使他们彼此联系。 这些优势将无处可寻，因为您意识到友谊并不是那样工作的。

let MakeGraph = () => {   let graph = {};

graph.contains = (node)=> {    return !!graph[node];  }

graph.addVertex = (node) => {      if(!graph.contains(node)){      graph[node] = {edges:{}};    }  }

graph.addEdge = (startNode, endNode) => {    // Only if both nodes exist    // Add each node to the others edge list

if(graph.contains(startNode) && graph.contains(endNode)){      graph[startNode].edges[endNode] = true;      graph[endNode].edges[startNode] = true;    }  }

return graph;}

let devBook = MakeGraph();  // Our graph representing our site

devBook.addVertex('James Gosling');devBook.addVertex('Guido Rossum');devBook.addVertex('Linus Torvalds');devBook.addVertex('Michael Olorunnisola');

// We'll add the edges here!

devBook.addEdge('James Gosling', 'Guido Rossum');devBook.addEdge('Linus Torvalds', 'Michael Olorunnisola');

// Now our devBook will look like this:

{ contains: [Function],  addVertex: [Function],  addEdge: [Function],  'James Gosling': { edges: { 'Guido Rossum': true } },  'Guido Rossum': { edges: { 'James Gosling': true } },  'Linus Torvalds': { edges: { 'Michael Olorunnisola': true } },  'Michael Olorunnisola': { edges: { 'Linus Torvalds': true } } }

This is absolutely fantastic, but at some point Linus reaches out to you and says, “I have no idea who the Michael guy is. I assumed he was Michael Tiemann, but I finally bothered trying to read his last name.”

这绝对是太棒了，但是在某些时候，Linus会向您伸出手，说：“我不知道谁是迈克尔。 我以为他是Michael Tiemann，但我终于不愿尝试读取他的姓氏。”

Right now you don’t have a way to remove a relationship, so you hop right into the code to whip together a removeEdge method to allow Linus to keep his friends list accurate.

现在，您还没有删除关系的方法，因此，您跳入了代码中，一起使用removeEdge方法来使Linus保持其好友列表的准确性。

let MakeGraph = () => {   let graph = {};

graph.contains = (node)=> {    return !!graph[node];  }

graph.addVertex = (node) => {      if(!graph.contains(node)){      graph[node] = {edges:{}};    }  }

graph.addEdge = (startNode, endNode) => {    if(graph.contains(startNode) && graph.contains(endNode)){      graph[startNode].edges[endNode] = true;      graph[endNode].edges[startNode] = true;    }  }    graph.removeEdge = (startNode, endNode) => {    if(graph.contains(startNode) && graph.contains(endNode)){      delete graph[startNode].edges[endNode]      delete graph[endNode].edges[startNode]    }  }

return graph;}

devBook.removeEdge('Linus Torvalds', 'Michael Olorunnisola');

// Relationship removed!

{ contains: [Function],  addVertex: [Function],  addEdge: [Function],  removeEdge: [Function],  'James Gosling': { edges: { 'Guido Rossum': true } },  'Guido Rossum': { edges: { 'James Gosling': true } },  'Linus Torvalds': { edges: {} },  'Michael Olorunnisola': { edges: {} } }

Great! Unfortunately Linus says that he just wanted to try the site out, but that he’s way to0 hermitic to be on a site like this. He really wants to delete his account, but is currently unable to because you haven’t added a node removal method yet.

大！ 不幸的是，Linus说他只是想尝试该站点，但是他想让隐士进入这样的站点。 他确实想删除他的帐户，但是由于您还没有添加节点删除方法而当前无法删除。

let MakeGraph = () => {   let graph = {};

graph.contains = (node)=> {    return !!graph[node];  }

graph.addVertex = (node) => {      if(!graph.contains(node)){      graph[node] = {edges:{}};    }  }

graph.removeVertex = (node) => {    if(graph.contains(node)) {    // We need to remove any existing edges the node has      for(let connectedNode in graph[node].edges) {        graph.removeEdge(node, connectedNode);      }      delete graph[node];    }

}

graph.addEdge = (startNode, endNode) => {    if(graph.contains(startNode) && graph.contains(endNode)){      graph[startNode].edges[endNode] = true;      graph[endNode].edges[startNode] = true;    }  }    graph.removeEdge = (startNode, endNode) => {    if(graph.contains(startNode) && graph.contains(endNode)){      delete graph[startNode].edges[endNode]      delete graph[endNode].edges[startNode]    }  }

return graph;}

// Now we can remove users!

devBook.removeVertex('Linus Torvalds');

Great job! Although you lost a potentially valuable user, you’ve been able to implement a basic graph system to keep track of all of your users and their friendships.

很好！ 尽管您失去了一个潜在的有价值的用户，但是您已经能够实现一个基本的图形系统来跟踪所有用户及其友情。

If you notice, we didn’t implement the hasEdge method, but I think you have enough information to give it a shot! Feel free to include your implementation in the comments below ?.

如果您注意到，我们没有实现hasEdge方法，但是我认为您有足够的信息来尝试一下！ 可以在下面的评论中随意包含您的实现吗？

图方法作为邻接表的时间复杂度分析 (A time complexity analysis on the graph methods as an adjacency list)

Here’s our code again:

这又是我们的代码：

let MakeGraph = () => {   let graph = {};

graph.contains = (node)=> {    return !!graph[node];  }

graph.addVertex = (node) => {      if(!graph.contains(node)){      graph[node] = {edges:{}};    }  }

graph.removeVertex = (node) => {    if(graph.contains(node)) {      for(let connectedNode in graph[node].edges) {        graph.removeEdge(node, connectedNode);      }      delete graph[node];    }  }

graph.addEdge = (startNode, endNode) => {    if(graph.contains(startNode) && graph.contains(endNode)){      graph[startNode].edges[endNode] = true;      graph[endNode].edges[startNode] = true;    }  }    graph.removeEdge = (startNode, endNode) => {    if(graph.contains(startNode) && graph.contains(endNode)){      delete graph[startNode].edges[endNode]      delete graph[endNode].edges[startNode]    }  }

return graph;}

addNode is O(1): You’re just creating a property on an object so it’s constant time

addNode 是O(1)：您只是在对象上创建属性，因此时间恒定

addEdge is O(1): Since you’re using an object to represent your graph, it’s a constant time operation since your nodes and edges are represented as properties.

addEdge 是O(1)：由于您使用的是对象来表示图形，因此这是一项固定时间的操作，因为您的节点和边都表示为属性。

removeNode is O(n): If a node has edges, you’re going to have to iterate over all it’s existing edges to remove it’s existence as an edge on it’s connected nodes.

removeNode 是O(n)：如果节点具有边缘，则必须迭代所有现有边缘，以消除其作为已连接节点上边缘的存在。

removeEdge is O(1): Since your nodes are properties on your graph, you can access them in constant time and just delete the edges which are also accessible in constant time.

removeEdge 是O(1)：由于节点是图形上的属性，因此可以在恒定时间内访问它们，而只需删除在恒定时间内也可以访问的边。

contains is O(1): As a property on your graph, it’s a constant time lookup for a node.

contains 是O(1)：作为图上的一个属性，它是对节点的恒定时间查找。

hasEdge is O(1): Both nodes would be properties on your graph, so it would be a constant time lookup.

hasEdge 是O(1)：两个节点都是图上的属性，因此它将是固定时间的查找。

是时候快速回顾一下 (Time for a quick recap)

Graphs:

图表：

1. are just a combination of vertices and edges representing data and relationships
   只是表示数据和关系的顶点和边的组合

2. have addNode, addEdge, removeNode, and removeEdge methods to manage their contents

   具有addNode ， addEdge ， removeNode和removeEdge方法来管理其内容

3. have a contains and a hasEdge method to help you track the state of their state

   有一个contains和hasEdge方法可以帮助您跟踪其状态

进一步阅读 (Further Reading)

To say that there is a lot more to the graph data structure would be a huge understatement.

要说图形数据结构还有很多其他内容，这是一个很大的轻描淡写。

You could have represented the edges as an array instead of objects, or the entire graph as a 2-d array (adjacency matrix). You could have even represented the graph solely by their edges in an array (edge list).

您可以将边缘表示为数组而不是对象，或者将整个图形表示为2维数组( 邻接矩阵 )。 您甚至可以仅通过数组中的边缘来表示图形( edge list )。

As with anything in programming, there are trade-offs associated with each representation and it’s definitely worthwhile learning what they are.

与编程中的任何内容一样，每种表示形式都需要权衡取舍，绝对值得学习它们的含义。

Graphs are by far my favorite data structure and also one of the most versatile, but that’s just my humble opinion. (Those of you who love trees really are just graph lovers in disguise ?).

到目前为止，图是我最喜欢的数据结构，也是最通用的数据结构之一，但这只是我的拙见。 ( 你们当中那些爱树的人真的只是变相的图形爱好者 ？)。

Maybe I can sway you to love them as much as I do, so here are a few additional resources for you to read up on them:

也许我可以像我一样去爱你，所以这里有一些其他资源供您阅读：

• This Wikipedia Article does a great job not only covering the different representation of a graph, but also introducing you to some of the algorithms often associated with graphs.

  这篇Wikipedia文章做得很好，不仅涵盖了图形的不同表示形式，还向您介绍了一些通常与图形相关的算法。

• For those of you who are using Python here’s a graph implementation from the Python team!

  对于那些正在使用Python的人，这里有Python团队提供的图形实现 ！

• TutorialsPoint does a really good job of diving into how to implement two of the algorithms: Depth First Search and Breadth First Search. You might be confronted with these graph algorithms in interviews.

  TutorialsPoint在深入研究如何实现两种算法方面做得非常好，即深度优先搜索和广度优先搜索 。 您可能在采访中遇到这些图算法。

• Keith Woods does a great job of walking through how to implement a recommendation engine with a graph data structure here. Definitely worth a read, as it implements a lot of the concepts we didn’t get to here.

  基思·伍兹确实通过如何实现与图形数据结构的推荐引擎行走了伟大的工作在这里 。 绝对值得一读，因为它实现了许多我们以前未曾了解的概念。

• For those of you who are familiar with relational databases like MySQL — there’s a Graph database Neo4j, which I absolutely love, that not only uses SQL-like syntax, but has an awesome graphical user interface.

  对于那些熟悉像MySQL这样的关系数据库的人来说，我绝对喜欢一个Graph数据库Neo4j ，它不仅使用类似SQL的语法，而且还具有出色的图形用户界面 。

翻译自: https://www.freecodecamp.org/news/a-gentle-introduction-to-data-structures-how-graphs-work-a223d9ef8837/