问题描述
我了解有3种常见的图形表示方式:
I understand there are 3 common ways to represent graphs:
- 邻接矩阵
- 邻接表
- 边缘列表
也就是说，我在LeetCode上解决的问题经常使用矩阵，而解决方案则需要DFS或BFS.例如，给定下面的矩阵，则当您向左，向右，向上和向下移动(而不是对角线)时，查找目标字符串是否存在.
That said, problems I’ve solved on LeetCode often use matrices and the solution requires DFS or BFS. For example, given the matrix below, find if a target string exists when you go left, right, up, and down (but not diagonal).
[
[‘a’,‘p’,’p’],
[‘e’,’a’,’l’],
[‘r’,’t’,’e’]
]
这需要DFS方法.这是因为此矩阵代表图形还是DFS和BFS是否也适用于矩阵，而不仅是树和图形?
This required a DFS approach. Is this because this matrix represents a graph or does DFS and BFS apply to matrices too and not just trees and graphs?
在实现中，DFS和BFS是否总是/主要用于矩阵(2D数组)，或者在某些情况下将其用于Graph类?
Are DFS and BFS always/mostly used against matrices (2D arrays) in implementation or are there cases where it’s used against a Graph class?
推荐答案
图形算法通常用于解决未明确表示图形(例如矩阵)的数据结构上的问题.该图不在数据中.解决问题就在您的脑海中.例如，如果我将其视为图形，则可以解决DFS或BFS的问题".然后编写BFS或DFS算法，将遍历操作映射到要做具有的数据结构中等效的任何内容.
Graph algorithms are often used to solve problems on data structures that do not explicitly represent a graph, like your matrix. The graph is not in the data. It's in your head when you solve the problem. For example, "If I think of this as a graph, the I can solve the problem with DFS or BFS". Then you write a BFS or DFS algorithm, mapping the traversal operations to whatever is equivalent in the data structure you do have.
这被称为对隐式图"进行操作: https://en.wikipedia.org/wiki/Implicit_graph
This is called operating on the "implicit graph": https://en.wikipedia.org/wiki/Implicit_graph
如果您实际上是根据数据创建 图数据结构(即 explicit 图)，则可以直接在其上编写BFS或DFS，但这是通常是不必要的，实际上是浪费的.
If you actually made a graph data structure out of your data -- an explicit graph -- then you could write a BFS or DFS on that directly, but it's often unnecessary and in fact wasteful.
这篇关于每个矩阵在概念上都对应图吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！