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

Question

我知道有三种常用的方法来表示图：

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算法，将遍历操作映射到所拥有的数据结构中的任何等效操作。

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

如果你真的用你的数据制作了一个图数据结构——一个显式图——那么你可以直接在上面写一个BFS或DFS，但这通常是不必要的，而且实际上是浪费的。