Каждая матрица соответствует графу концептуально?

Question

Я понимаю, что есть 3 распространенных способа представления графиков:

1. Матрица смежности
2. Список смежности
3. Список краев

Тем не менее, проблемы, которые я решил с помощью LeetCode, часто используют матрицы, а для решения требуется DFS или BFS. Например, учитывая приведенную ниже матрицу, найдите, существует ли целевая строка при go влево, вправо, вверх и вниз (но не по диагонали).

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

Для этого требуется подход DFS. Это потому, что эта матрица представляет граф или DFS и BFS применимы и к матрицам, а не только к деревьям и графам?

Всегда ли / в основном DFS и BFS используются против матриц (двумерных массивов) в реализации или есть случаи, когда они используются против класса Graph?

Answer 1

Алгоритмы графов часто используются для решения проблем в структурах данных, которые не представляют явно граф, как ваша матрица. График не в данных. Это в вашей голове, когда вы решаете проблему. Например, «Если я думаю об этом как о графике, я могу решить проблему с DFS или BFS». Затем вы пишете алгоритм BFS или DFS, сопоставляя операции обхода с тем, что эквивалентно в структуре данных, которую вы делаете .

Это называется работой с "неявным графом": https://en.wikipedia.org/wiki/Implicit_graph

Если вы на самом деле сделали структуру графических данных из ваших данных - явный граф - тогда вы могли бы написать BFS или DFS для этого напрямую, но это часто не нужно и фактически расточительно.