为什么使用邻接矩阵或邻接列表? [英] Why Use Adjacency Matrices or Adjacency Lists?

问题描述

我刚刚开始学习图，而令我感到困惑的是为什么我们需要使用外部数据结构(如矩阵或列表)来存储图的哪些顶点与其他顶点连接顶点.

I've just started learning about graphs, and something that's confusing me is why we need to use external data structures (like matrices or lists) to store which vertexes of the graph are connected to other vertices.

为什么每个顶点都不能像其在决策树中那样，仅保留对其所连接的顶点的引用?在我看来，这似乎更直观.

Why can't each vertex just hold references to the vertices its connected to, like the way nodes do in a decision tree? That, to me, seems more intuitive.

谢谢！

推荐答案

好吧，这来自设计哲学.每当您有多对多关系时，您都会介绍一个经纪人来保持这种关系.这打破了关系，使管理代码和编写数据结构变得更加容易.

Well, this comes from a design philosophy. Whenever you have a many to many relationships, you introduce a broker to hold the relationship. This breaks the relationship and makes it easier to manage code and write a data structure.

例如，如果我们将所有顶点(称为列表B)的信息保留在连接到List B的顶点(称为A)上，则列表B的任何顶点的任何变化都需要传播到答:如果我们删除一些边缘，我们需要在A中进行更新.这会变得非常混乱.这也违反了单一责任原则.现在，可以从2个轴上修改我的顶点-如果它是自己修改的，或者它的任何连接都可以修改.

For example, if we keep all the vertices (call it List B) information to a vertex (call it A) that is connected to List B, any changes in any of the vertices of List B needs to be propagated to A. If we remove some edge, we need to update that in A. This can become very messy. This also violates the Single Responsibility Principle. Now my vertex can be modified from 2 axes - if it modifies on its own or any of its connections get modified.

但是，如果我们对数据结构进行建模，以使每个顶点可以独立更改，并且顶点中的任何更改都不需要对其他顶点进行突变，则可以简化我们的生活.我们可以使用manager或broker来管理每个顶点之间的关系，而不是管理每个顶点之间的关系.此关系管理器是邻接表/邻接矩阵.

However, if we model our data structure such that each vertex can change independently and any change in a vertex doesn't require other vertices to be mutated, that makes our life simpler. We can have a manager or broker that manages the relationship between each vertex instead of each vertices managing that. This relationship manager is the adjacency list / adjacency matrix.

这篇关于为什么使用邻接矩阵或邻接列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！