使用链表和链表的图形表示矩阵
我知道如何使用链表或矩阵来实现图形。但我想知道什么时候使用链表和链表何时使用矩阵来表示图形？
I know how to implement graph using linked list or Matrix. But i want to know when to use Linked List & when to use matrix for graph representation?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
V = 图中的顶点数
有利于矩阵的点：
1. 给定其结束顶点，您可以在恒定时间内访问一条边（找出两个顶点之间是否存在边），而使用邻接表则需要 O(deg(vertex)) 时间。
2. 如果你的图很稠密，那么矩阵就很好。否则会浪费空间，因为它使用 O(V*V) 空间。
有利于邻接表的点：
1. 迭代获取顶点的邻居需要 O(V) 时间，而如果使用邻接列表则需要 O( Degree(Vertex)) 。
2.邻接表不占用大量空间。
V = number of vertices in graph
Points favouring Matrix:
1. You can access an edge (find out whether an edge exists between two vertices) given its end vertices in constant time whereas it takes O(degree(vertex)) time while using adjacency list.
2. Matrix is good if your graph is dense. Otherwise it wastes space because it uses O(V*V) space.
Points favouring adjacency list:
1. You need O(V) time to iterate get the neighbours of a vertex whereas it takes O(degree(Vertex)) if you use adjacency list.
2. Adjacency list does not take a lot of space.
通常，当您的图表密集时。使用矩阵是一个好主意，因为未使用的内存和不需要的读取的“损失”被忽略。
当您想快速知道是否存在边，或者想在图上执行矩阵运算时，通常也会使用矩阵[例如页面排名] (*)
如果您要在读取每个顶点时使用所有边（例如：在 BFS 上），则通常首选链表。
(*)请注意，页面排名在幕后通常使用链表，因为图非常稀疏，但我们将其视为“稀疏矩阵”...
Usually, when your graph is dense. It is a good idea to use matrix , since the 'loss' of unused memory and not needed reads is neglected.
You usually also use a matrix when you want to know fast if an edge exist, or you want to preform matrix ops on the graph [such as Page Rank] (*)
A linked list is usually prefered if you are going to use all edges for each vertex, when reading it [for example: on BFS].
(*)Note that page rank behind the scenes is usually using a linked list since the graph is very sparsed, but we regard it as a "sparsed matrix"...
这两种实现在内存消耗和复杂性方面存在两个根本区别。
插入和删除元素的时间，但（通常）它消耗
更多空间。
访问元素和邻居可能需要线性时间。
There is two fundamental differences between those two implementations in terms of memory consumption and complexity.
time insertion and removal of elements but (in general) it consume
more space.
access to element and neighbours can take linear time.
这取决于您的问题和需求。当您需要速度并且具有大存储空间时（如果您的矩阵很大），请使用矩阵；如果您需要节省空间且需要稍微减慢速度，则使用链表。
It depends on your problem and needs. Use matrix when you need speed and have big storage (in case your matrix is big), use linked list if you need to save space with the trade off having a little slow down.
你总是使用矩阵。
有多种技术可用于在内存中表示矩阵，包括使用链表表示稀疏矩阵的各种方法。任何一本关于矩阵计算的好书都会有很多表示和指南，告诉您什么时候适合使用它们；根据您的图表，可能不太常见的表示之一是合适的。
You always use a matrix.
There are various techniques for representation of matrices in memory, including various ways of using linked lists to represent sparse matrices. Any good book on matrix computation will have many representations and guidelines for when it is good to use them; depending on your graph it may be that one of the less common representations is appropriate.