How can I build a graph from a 2D array?

Question

I am trying to learn graph structures and algorithms. Conceptually I understand DFS, BFS, and I can implement them provided a graph, but how are graphs traditionally composed?

Typically I see them as list of nodes with edges as pointers, a list of edges with the nodes they connect, or a 2d matrix where the intersection of both arr[node_a][node_b] is the weight of the edge.

When it comes to actually building it out of input, I don't know where to start.

As an example, how you would you build a graph when provided a 2d grid like (an online pacman problem) where P is the source node and -'s are nodes in the tree.

%%%%%%%%%%%%%%%%%%%%
%--------------%---%
%-%%-%%-%%-%%-%%-%-%
%--------P-------%-%
%%%%%%%%%%%%%%%%%%-%
%.-----------------%
%%%%%%%%%%%%%%%%%%%%

Or, how would you build it when provided with an adjacency list?

I understand this is probably a big question, as the subject is rather complicated. Links to documentation are appreciated! I've been having trouble finding any from an introductory level.

Answer 1

for this purpose I wrote this javascript, it converts a matrix (array of array) in a unweight graph. It starts to navigate in the 4 directions (up/down/right/left) without walking where it already goes.

Then, it will use DFS to find the shortest path.

const wall = 0
const flat = 1
const target = 9

// no diagonals
const possibleMoves = [
  [-1, 0], // nord
  [0, +1],
  [+1, 0], // sud
  [0, -1],
]

function pathFinder(map) {
  const gridW = map[0].length
  const gridH = map.length
  const start = buildNode([0, 0], map)
  const tree = buildTreeMap(start, map, [start])
  const path = navigateTree(tree)
  console.log(path.map(_ => _.point));
  return path.length


  // Depth-first search (DFS)
  function navigateTree(node) {
    const dfp = (acc, _) => {
      if (_.value === target) {
        acc.push(_)
        return acc
      }
      const targetInMyChildren = _.children.reduce(dfp, [])
      if (targetInMyChildren.length > 0) {
        targetInMyChildren.unshift(_)
        return targetInMyChildren
      }
      return acc
    }

    return node.children.reduce(dfp, [])
  }

  function buildTreeMap(node, map2d, visited) {
    const [x, y] = node.point
    node.children = possibleMoves
      .map((([incx, incy]) => [x + incx, y + incy]))
      .filter(([nx, ny]) => {
    /**
     * REMOVE
     * + out of grid
     * + walls
     * + already visited points
     */
        if (nx < 0 || nx >= gridW
          || ny < 0 || ny >= gridH
          || map2d[ny][nx] === wall) {
          return false
        }

        return visited.findIndex(vis => vis.point[0] === nx && vis.point[1] === ny) === -1
      })
      .map(_ => {
        const newNode = buildNode(_, map2d)
        visited.push(newNode)
        return newNode
      })
    node.children.forEach(_ => buildTreeMap(_, map2d, visited))
    return node
  }

}

function buildNode(point, map) {
  const value = map[point[1]][point[0]]
  return {
    point,
    value,
    children: []
  }
}



const stepsCount = pathFinder([
  [1, 1, 1, 1],
  [0, 1, 1, 0],
  [0, 1, 1, 0],
  [0, 1, 0, 0],
  [0, 1, 1, 1],
  [0, 1, 1, 1],
  [9, 0, 1, 1],
  [1, 1, 1, 1],
  [1, 0, 1, 0],
  [1, 1, 1, 1]
])
console.log(stepsCount);

Answer 2

Graphs are typically stored using one of two data structures:

1. Adjacency List (http://en.wikipedia.org/wiki/Adjacency_list)

2. Adjacency Matrix (http://en.wikipedia.org/wiki/Adjacency_matrix)

Each has its own space and time advantages.

You would have to convert whatever input you want to represent as a graph (e.g., parse it), into one of the above data structures.