Does every matrix correspond to a graph conceptually?

0
votes

I understand there are 3 common ways to represent graphs:

  1. Adjacency Matrix
  2. Adjacency List
  3. Edge list

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’]
]

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?

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?

1
matrixgraphtreedepth-first-searchbreadth-first-search

1 Answers

1
votes

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.

This is called operating on the "implicit graph": https://en.wikipedia.org/wiki/Implicit_graph

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.