每个矩阵在概念上对应于图吗？

Question

我了解代表图表的3种常见方式：

1. 邻接矩阵
2. 邻接表
3. 边缘列表

就是说，我在LeetCode上解决的问题经常使用矩阵，而解决方案则需要DFS或BFS。例如，给定下面的矩阵，查找当您左，右，上和下（而不是对角线）时是否存在目标字符串。

[
  [‘a’,‘p’,’p’],
  [‘e’,’a’,’l’],
  [‘r’,’t’,’e’]
]

这需要DFS方法。这是因为此矩阵代表图形还是DFS和BFS是否也适用于矩阵，而不仅仅是树和图形？

在实现中DFS和BFS是否总是/主要用于矩阵（2D数组），或者是否有针对Graph类的使用？

Answer 1

图形算法通常用于解决未明确表示图形的数据结构（如矩阵）的问题。该图不在数据中。解决问题就在您的脑海中。例如，“如果我将其视为图形，则可以解决DFS或BFS的问题”。然后编写BFS或DFS算法，将遍历操作映射到

do具有的数据结构中等效的任何内容。

这被称为对“隐式图”进行操作：https://en.wikipedia.org/wiki/Implicit_graph

如果您实际上是根据数据中的图形数据结构创建的-[[explicit

图形-那么您可以直接在其上编写BFS或DFS，但通常是不必要的，而且实际上是浪费的”。